Create your own graph structure class and its drawing in python

Create your own graph structure class and its drawing with python

I couldn't solve the graph problem that was asked in D of ABC160 of AtCoder, so after studying python, I tried drawing a graph structure class and it with maatplotlib.

(Reflect on participating in AtCoder) Code I wish I had remembered when I first participated in AtCoder (Reflection 1 for the next time)

There seems to be *** NetworkX *** in the library that expresses the graph structure, but I will not use it this time. (Can't it be used with AtCoder in the first place?)

There are many smart ways to express it, Since it is an implementation within the range that an amateur can roughly think about, please forgive me for not being able to make it.

Graph structure class

Concept

The class has a dictionary with a node as a key and the tip of the edge as a value as a member variable. Prepare the following methods. ① Add a node ② Add an edge ③ Display the node ④ Return the node as a list ⑤ Return the node connected to the specified node

Class definition

#Creating a graph structure
class cglaph():
  def __init__(self):
    #Node initialization
    self.nodes={}

  def addnode(self,num):#① Add a node
    for i in self.nodes.keys():
      if i==num:
        return(False)
    else:
      self.nodes[num]=list()
      return(True)

  def addedge(self,ag1,ag2):#② Add an edge
    node1=min(ag1,ag2)
    node2=max(ag1,ag2)
    addok=False

    for i in self.nodes.keys():
      if i==node1:
        for j in self.nodes.keys():
          if j==node2:
            addok=True

    if addok:
      self.nodes[node1].append(node2)
      self.nodes[node2].append(node1)

  def printnodes(self):    #③ Display the node
    print("■Glaph:")
    print("vertice:neighbors")
    for k,v in self.nodes.items():
      print(k,":",v)


  def getnodes(self):#④ Returns a list of nodes
    keylist=list()

    for i in self.nodes.keys():
      keylist.append(i)
    return keylist

  def getedge(self, node):#⑤ Returns the edge (connected node) of the specified node.
    return self.nodes[node]

Let's actually make an undirected graph that connects 5 nodes appropriately

G=cglaph()
G.addnode(1)#Add node
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#Add edge
G.addedge(1,4)
G.addedge(5,3)

G.printnodes()#List of nodes

nodelist=G.getnodes()#Get node list
print ("NODE LIST:",nodelist)

G.getedge(1)#Node connected to node 1

cap1.PNG

Visualization of the created graph structure

After studying matplotlib, let's visualize the graph we made. I didn't know what to do with the drawing position of the node, so We decided to place the nodes at random positions. I would like to think of a way to place it in a nice position in the future.

import matplotlib.pyplot as plt
import random
random.seed(0)

#Random because I don't know what to do with the node position
N=len(nodelist)
x=[random.randint(0, 100) for i in range(N)]
y=[random.randint(0, 100) for i in range(N)]
print("x:",x)
print("y:",y)

#Graph creation
plt.figure(1)

#Node drawing
plt.scatter(x,y)

#Give the node name to the node position
ax=plt.axes()
for i in range(N):
  ax.annotate(nodelist[i],(x[i],y[i]),size=20)

#Draw an edge This is not smart
for i in range(N):
  edges=G.getedge(i+1)
  for j in edges:
    plt.plot((x[i],x[j-1]),(y[i],y[j-1]), color='red')

plt.xlim(0, 100)
plt.ylim(0, 100)

cap2.PNG

Finally

I will finally start studying breadth-first search!

reference

[Matplotlib] Annotations and Arrows

<Python, matplotlib> Add text to each element of the scatter plot.

Let's analyze and visualize the network with Python! Required procedure summary

How to retrieve an element with a for loop of Python dictionary (dict)

Recommended Posts

Create your own graph structure class and its drawing in python
Create your own Linux commands in Python
Specify your own class in class argument and return type annotation in Python
Graph drawing in python
Create your own Big Data in Python for validation
Create your own Random Dot Stereogram (RDS) in Python.
[Road to intermediate Python] Define in in your own class
[Python] logging in your own module
Create and read messagepacks in Python
Easily use your own functions in Python
[Python] Package and distribute your own modules
Easily graph data in shell and Python
Get your own IP address in Python
[Python] Implement your own list-like class using collections.UserList
Create a standard normal distribution graph in Python
[python] Difference between variables and self. Variables in class
From file to graph drawing in Python. Elementary elementary
Automatically create word and excel reports in python
I wrote a class in Python3 and Java
Import your own modules in Grasshopper's Python development
python: Use your own class for numpy ndarray
Create your own exception
Memo to create your own Box with Pepper's Python
case class in python
Try to improve your own intro quiz in Python
Create SpatiaLite in Python
Until drawing a 3D graph in Python on windows10
[Blender × Python] Create your own function & summary so far
Use the CASA Toolkit in your own Python environment
Find the Hermitian matrix and its eigenvalues in Python
C-like structure in Python
Create your first GDSII file in Python using gdspy
Get your current location and user agent in Python
Get stock prices and create candlestick charts in Python
Draw graph in python
Class notation in Python
Sample of getting module name and class name in Python
[Python] When you want to import and use your own package in the upper directory
How to use pyenv and pyenv-virtualenv in your own way
Reference order of class variables and instance variables in "self. Class variables" in Python
Create code that outputs "A and pretending B" in python
I created a class in Python and tried duck typing
Graph time series data in Python using pandas and matplotlib
Reinforcement learning 23 Create and use your own module with Colaboratory
Graph the Poisson distribution and the Poisson cumulative distribution in Python and Java, respectively.
Python: Class and instance variables
Create a function in Python
Create a dictionary in Python
Create gif video in Python
Python class variables and instance variables
Stack and Queue in Python
Create your own Django middleware
Unittest and CI in Python
Create an instance of a predefined class from a string in Python
Try docker: Create your own container image for your Python web app
Throw something to Kinesis with python and make sure it's in
Create your own IoT platform using raspberry pi and ESP32 (Part 1)
Create a CGH for branching a laser in Python (laser and SLM required)
I was addicted to confusing class variables and instance variables in Python
[Python] Make your own LINE bot
MIDI packages in Python midi and pretty_midi