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.
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
#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]
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
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)
I will finally start studying breadth-first search!
[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