Question

2. Reverse of a digraph 30 Marks For a given set of digraphs, write a program that prints out the reverse of each digraph Input format: described below under the heading "Digraph input format". Note that adjacency lists are sorted Output format: use the input format to output your result ensuring that the output adjacency lists are sorted. For the example input shown below, the output would be 2 C) 0 1 3 0 2 C) C)

Reverse of a digraph 30 Marks

For a given set of digraphs, write a program that prints out the reverse of each digraph. Input format: described below under the heading “Digraph input format”. Note that adjacency lists are sorted. Output format: use the input format to output your result ensuring that the output adjacency lists are sorted.

the input format:

4

1. 3

2. 3

0

3

1. 2

1

0

Answer 1

The reverse of a directed graph is a graph in which the edges are reversed in direction as compared to the original graph. That is if there is an edge (u, v) which represents an edge directed from u to v, then in the reverse of the directed graph, we would have an edge (v, u). The algorithm to find out the reverse of a directed graph is fairly simple. For every node, we traverse that nodes edge set and for every edge set member (u_{i ,} v_i) we reverse its direction to (v_{i ,} u_i). The algorithm is fairly simple in this problem but the way the input graph is provided is a bit tricky, but I will try to answer that too as well. I have used python to answer this question and if you have any problem understanding the code ask me in the comment section and I will definitely help you out. Please do remember to input the graph in the exact way the input is being specified in the problem, That is first input the size of the graph first, then followed by the N lines describing the edge set, which includes space separated numbers that indicate the nodes to which the ith node is connected to. Please remember to input an empty line to nodes from which there are no outgoing edges, the code heavily depends on the input section of the problem. I will provide you with the way the input is to be provided so that the desired output is obtained.

Input:-

4
1 3
2 3
0

3
1 2

1
0

Code (in python 2.7):-

while(1):
   n = input()
   if(n == 0):
       print (0)
       break
   print (n)
   ori_graph = []
   rev_graph = []
   for i in range(0, n):
       ori_graph.append([])
       rev_graph.append([])
   for i in range(0, n):
       ar = raw_input().split()
       for j in range(0, len(ar)):
           ori_graph[i].append(int(ar[j]))
   for i in range(0, n):
       for j in range(0, len(ori_graph[i])):
           rev_graph[ori_graph[i][j]].append(i)
   for i in range(0, n):
       rev_graph[i].sort()
       for j in range(0, len(rev_graph[i])):
           print rev_graph[i][j],
       print ('')

If you are having any kind of problem in understanding the code, related to the algorithm used to reverse the graph, or the input format used feel free to ask me in the comments. I am there to help you out here. Thank you.