首页 >
> 详细

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
- 微信：codinghelp2

- Program课程作业代做、Python语言作业代写、Python编程作业调 2020-06-01
- 代做stats762作业、代写r编程设计作业、R课程设计作业代做、代写dat 2020-06-01
- Cosc 2666作业代写、C++程序设计作业调试、Programming作 2020-06-01
- Stats 731作业代写、代做c+,Java程序语言作业、代写python 2020-06-01
- Etf5952课程作业代写、Risk Analysis作业代做、Python 2020-06-01
- 41889留学生作业代做、代写ios Application作业、Java， 2020-06-01
- Sta2202作业代做、代写data课程作业、R程序语言作业调试、代写r课程 2020-06-01
- You Have Implemented A Simple Web Serv... 2020-05-31
- Stat 5511 Homework 4 2020-05-31
- Lab 7 2020-05-31
- 代写cosc 363作业、代做computer Graphics作业、代写c 2020-05-31
- Eie111课程作业代写、C++程序设计作业调试、代做c/C++语言作业、代 2020-05-31
- Math502作业代做、Mathematics课程作业代做、Java，Pyt 2020-05-31
- 代写sit114课程作业、代做data留学生作业、代写r编程设计作业、代做r 2020-05-31
- Envx3002作业代写、R程序语言作业调试、R课程设计作业代做、代写dat 2020-05-31
- Ee6435 Programming Homework 2020-05-30
- Computer Architecture Homework 3 2020-05-30
- Infs7450作业代做、Media Analytics作业代写、Pytho 2020-05-29
- 代写stats 782作业、代做r编程设计作业、代写data留学生作业、R课 2020-05-29
- 代写math223作业、R课程设计作业代做、代写data课程作业、R程序语言 2020-05-28