首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp

- 代写data留学生作业、R编程语言作业调试、代做r课程设计作业帮做c/C++ 2019-12-04
- 代写mat2040留学生作业、代做linear Algebra作业、Pyth 2019-12-04
- 代写framework留学生作业、代做r编程语言作业、代写r课程设计作业、D 2019-12-04
- Plid50留学生作业代做、代写java，C++程序设计作业、代做pytho 2019-12-04
- 代写strategy Game作业、Java程序语言作业调试、Java课程设 2019-12-04
- Fs19 Stt481作业代做、代写dataset课程作业、C/C++，Py 2019-12-04
- Data留学生作业代写、代做java，Python编程设计作业、代写c/C+ 2019-12-04
- Data Frames作业代写、代做r编程语言作业、代写r课程设计作业、Uc 2019-12-04
- 代写es3c5留学生作业、Systems课程作业代做、Matlab程序语言作 2019-12-04
- Cs 1160留学生作业代做、代写programming课程作业、代做c/C 2019-12-04
- 代做comp 250作业、Math 240作业代写、Java编程语言作业调试 2019-12-04
- 代写elec5681m作业、Programming课程作业代做、代写c++实 2019-12-04
- Cs 201留学生作业代做、代写dynamic Analysis作业、代写j 2019-12-04
- 代写cs2313留学生作业、代做programming作业、C++程序语言作 2019-12-04
- Data Frame作业代写、代做r编程设计作业、代做r课程设计作业、Mas 2019-12-03
- Cs 116留学生作业代做、代写program课程作业、Python程序设计 2019-12-03
- 代写fdm留学生作业、代做c++课程设计作业、C++程序语言作业调试、Alg 2019-12-03
- 代写database课程作业、代做python/Java编程语言作业、代写p 2019-12-03
- 代做ie 6200作业、代写r编程设计作业、Data留学生作业代做、R实验作 2019-12-03
- 5Cosc001w作业代做、代写programming课程作业、代写java 2019-12-03