Problem 1 [60 pts] Write code to visualize the different strongly connected components of a graph....

Transcribed Image Text:

Problem 1 [60 pts] Write code to visualize the different strongly connected components of a graph. Your code should be implemented in a file called visualize-scc.py. The function should be called by the same name. The function should take the name of a file. This file will contain the definition of a directed graph. The definition will be specified as follows. The first line will contain the total number of vertices n and the vertex names will be 1,2,...,n. The next few lines will contain edges specified by start vertex and end vertex. So, here is an example file: 3 4 4 5 5 1 The graph above has 5 vertices and is really a cycle graph, with the edges (1, 2), (2, 3), (3, 4), (4, 5), (5, 1). So I can store this file as input.txt for example and call your code as visualize-scc ('input.txt') in the interactive python interpreter. What should it do? It should first compute all the strongly connected components. Then, it should color each scc differently, i.e., vertices in the same scc get the same color - vertices in different scc's get different colors. If the number of scc's is more than say 6 (i.e., you run out of the usual colors), you can color the first few in one color and all the rest in one color. The final output is on the terminal, where you list out the scc's as "SCC1 : x y z .." and also draw the graph using (possibly suitable modifications of the) visualization functions uploaded earlier as python code. Problem 1 [60 pts] Write code to visualize the different strongly connected components of a graph. Your code should be implemented in a file called visualize-scc.py. The function should be called by the same name. The function should take the name of a file. This file will contain the definition of a directed graph. The definition will be specified as follows. The first line will contain the total number of vertices n and the vertex names will be 1,2,...,n. The next few lines will contain edges specified by start vertex and end vertex. So, here is an example file: 3 4 4 5 5 1 The graph above has 5 vertices and is really a cycle graph, with the edges (1, 2), (2, 3), (3, 4), (4, 5), (5, 1). So I can store this file as input.txt for example and call your code as visualize-scc ('input.txt') in the interactive python interpreter. What should it do? It should first compute all the strongly connected components. Then, it should color each scc differently, i.e., vertices in the same scc get the same color - vertices in different scc's get different colors. If the number of scc's is more than say 6 (i.e., you run out of the usual colors), you can color the first few in one color and all the rest in one color. The final output is on the terminal, where you list out the scc's as "SCC1 : x y z .." and also draw the graph using (possibly suitable modifications of the) visualization functions uploaded earlier as python code.