# Python辅导 | Graph with nodes and edges

Graph with nodes and edges

Consider the following directed graph with 6 nodes and 12 edges.

Figure 1. A directed graph with 6 nodes and 12 directed edges (a bidirectional edge is regarded as two directed edges in this question, so there are 12 directed edges in total).

• The graph can be represented with node and edge, and both node and edge are global variables implemented using the dictionary.

node={}

edge={}

• node is a global variable with key as node ID (an int), value as name of the node (a string).
• edge is a global variable with key as node ID (an int), value as a collection (a set) of neighbour node ID(s). (with ‘b is neighbor node of a’, we mean that there exists an edge a→b)
• We would like to implement a program main.py that supports four commands, namely InsertNode, InsertEdge, CommonNeighbor and ShortestPath:

The program source code is shown below.

node={}

edge={}

def main():

command=input().split()

while(command!=”END”):

if (command==”InsertNode”):

InsertNode(int(command),command)

elif (command==”InsertEdge”):

InsertEdge(int(command),int(command))

elif (command==”CommonNeighbor”):

CommonNeighbor(int(command),int(command))

elif (command==”ShortestPath”):

ShortestPath(int(command),int(command))

command=input().split()

return

main()

1. InsertNode x y – Insert the node with id as x and name as y in a graph. For example, we issue the following commands to insert 6 nodes in the graph in Figure 1.

InsertNode 0 Library_Building
InsertNode 1 Hui_Oi_Chow_Science_Building
InsertNode 2 University_Street
InsertNode 4 Haking_Wong_Building
InsertNode 5 Chow_Yei_Ching_Building

• You can assume that the name of the nodes will not contain any space.
• The id of the nodes may not start from 0 and may not be in ascending order.
• If the id of the node already exists, please output “ID exists.
• Before you proceed to the next part, you may implement InsertNode() and try to validate the correctness of your program.

Testcases.pdf

1. InsertEdge x y – Insert an edge x→y in the graph. Where x and y are the id of nodes.
For example, we issue the following commands to insert the 12 edges in the graph in Figure 1.

InsertEdge 0 1
InsertEdge 1 0
InsertEdge 1 2
InsertEdge 2 1
InsertEdge 0 3
InsertEdge 3 0
InsertEdge 2 4
InsertEdge 4 2
InsertEdge 3 4
InsertEdge 4 3
InsertEdge 4 5
InsertEdge 5 4

• If there are no Nodes in the Graph with id equal to x or y, output “No such node.” on screen.
• If the edge already exists, output “Edge exists.”.
1. CommonNeighbor x y – Returns the common neighbor of nodes x and y.

CommonNeighbor 1 3
0 Library_Building
CommonNeighbor 1 5
No common neighbor.
CommonNeighbor 1 0
No common neighbor.

• If there are no common neighbor, output “No common neighbor.”.
• If any of the two nodes does not exist, output “No such node.”
• If there are more than one common neighbors, output them in ascending order of the node ID, line by line.
1. ShortestPath x y – Returns the shortest path from node x to node y.

ShortestPath 0 4
0 Library_Building
4 Haking_Wong_Building
ShortestPath 1 5
1 Hui_Oi_Chow_Science_Building
2 University_Street
4 Haking_Wong_Building
5 Chow_Yei_Ching_Building

• If there are more than one shortest paths, you can output any one of those.
• If node x cannot reach node y, output “No path found.”.

How to find the shortest path? We may use the breadth-first search technique as follow:

Step 1. Initialization.

• We define 3 variables that help the searching process.
1. q = [] – For remembering the node to search.
2. visited = {} – For remembering if a node is visited or not.
3. previous = {} – For remembering the previous node in a path.
• Append source in q by q.append(source)
• For each node x in the graph, initialize visited[x] to False.
• Set the source node as “visited” by setting visited[source]=True.

Figure 2a. Initialization of the searching process.

Step 2. Start searching.

• While the destination node is not reached and the queue q is not empty, we keep on searching.

while (visited[des]==False and #len of q is not 0):

Step 1. Pop the first node from q, and store the node in current.

current = q.pop(0)

Step 2. For each neighbor node n of the current node

• If that node n is not visited before ( i.e., visited[n] is False)
• Append n to q.
• Step 3. Set node n as visited by setting visited[n]=True.
• Step 4. Set previous of n as current by setting previous[n]=current.

Step 5. Repeat Step 1. if the destination node is not reached and q is not empty.

• Figure 2b-2d give a step-by-step illustration to help you better understand the searching process.

Figure 2b. The instance after exploring the neighbor of node 0 (the source node).

Figure 2c. The instance after exploring the neighbor of node 1.

Figure 2d. The instance after exploring the neighbor of node 3, since the destination node is reached, we can break the while loop. The shortest path information is now stored in previous.

node={} #Global variable with key as node ID (an integer), value as name of the node.

edge={} #Global variable with key as the node ID (an integer), value as a set of neighbor node ID(s)

def InsertNode(id,name):

#Empty function, to be implemented by you

return

def InsertEdge(id1,id2):

#Empty function, to be implemented by you

return

def CommonNeighbor(id1,id2):

#Empty function, to be implemented by you

return

def ShortestPath(src,des):

#Empty function, to be implemented by you

return

def main():

command=input().split()

while(command!=”END”):

if (command==”InsertNode”):

InsertNode(int(command),command)

elif (command==”InsertEdge”):

InsertEdge(int(command),int(command))

elif (command==”CommonNeighbor”):

CommonNeighbor(int(command),int(command))

elif (command==”ShortestPath”):

ShortestPath(int(command),int(command))

command=input().split()

return

main() E-mail: vipdue@outlook.com  微信号:vipnxx 