代写nodes and edges、代做Java程序语言、代写Python/C++设计

日期：2019-11-15 05:04

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.