Graph with nodes and edges
Consider the following directed graph with 6 nodes and 12 edges.D
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[0]!="END"):
if (command[0]=="InsertNode"):
InsertNode(int(command[1]),command[2])
elif (command[0]=="InsertEdge"):
InsertEdge(int(command[1]),int(command[2]))
elif (command[0]=="CommonNeighbor"):
CommonNeighbor(int(command[1]),int(command[2]))
elif (command[0]=="ShortestPath"):
ShortestPath(int(command[1]),int(command[2]))
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 3 Kadoorie_Biological_Sciences_Building
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.
• Please download the testcases we prepared for you to help you check
the correctness of your program.
2. 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.”.
3. 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.
4. ShortestPath x y – Returns the shortest path from node x to node y.
ShortestPath 0 4
0 Library_Building
3 Kadoorie_Biological_Sciences_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)
o Append n to q.
o Step 3. Set node n as visited by setting visited[n]=True.
o 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.