(Solved): Need to Implement Topological sort and Strongly Connected Components. Code from the Graph class, and ...

Need to Implement Topological sort and Strongly Connected Components. Code from the Graph class, and the DFS() , DFS_visit() functions needs to be used and it is attached in first 2-3 images. After that, the things to be implemented for Task 1 and Task 2 of this topological sort and Strongly connected Components are attached. The guidelines and the expected output are given in the images attached below. Kindly solve them in python. Thank you.

The class uses dict object self. adj to store all the adjacency lists. The key of self.adj is a vertex, and the corresponding value is a list of adjacent vertices. The add_edge() function takes two vertices (from_vertex, to_vertex) as inputs, and use them to initialize (key, value) in self.adj. Note that for a undirected graph, self.adj should be updated twice with two vertices flipped to (to_vertex, from_vertex). In [5] class Graph: def _init__(self, directed-False): self.directed directed self.adj = {} def print_graph (self): for i in self.adj: print (i," : ", "->".join([str(j) for j in self.adj[i]])) def add_edge (self, from_vertex, to_vertex): ### START YOUR CODE ### if from vertex in self.adj: if to vertex not in self.adj[from_vertex]: else: self.adj[from_vertex].append(to_vertex) pass pass self.adj[from_vertex] = [to_vertex] if to_vertex not in self.adj: self.adj[to_vertex] = [] pass # Also add to_vertex to self.adj, but its list should be empty if not self.directed: self.adj[to_vertex].append(from_vertex) pass #Flip from_vertex and to_vertex and add them to self. adj in a similar way as the block of code abov ### END YOUR CODE ### In [6]: # Do not change the test code here g Graph() g.add_edge('s', a add edgel's I 'r') '') Implement the enhanced version of DFS, which records the discovered and finished time for all vertices. The difference from textbook is that the time stamps are not stored as attributes of vertices, but instead in two dict objects that are passed along to the recursive function. Also, we do not use the white, grey, and black colors to indicate whether vertices are visited, but instead we use a dict object whose values are binary variables. In [24]: time = 0# Initialize the gloabl time. def DFS (graph): ### START YOUR CODE ### visited = {} for var in graph.adj: visited [var] = None # Hint: a dict whose keys are all the vertices in the graph, and values are initialized to discovered = {} for var in graph. adj: discovered [var] = None. #Hint: same keys as above, values initialized to None finished = {} for var in graph. adj: finished [var] = None. #Hint: same as above ### END YOUR CODE ### global time # Make sure to use the global variable time = 0 ### START YOUR CODE ### for u in graph.adj: # Specify loop range if visited [u] == None: DFS visit (graph, u, visited, discovered, finished) # Add necessary code ### END YOUR CODE ### return discovered, finished def DFS_visit (graph, vertex, visited, discovered, finished): ### START YOUR CODE ### global time time time + 1 I visited[vertex] = True discovered fuertor! - tino & Idd 251: for var in graph. adj: visited [var] = None Hint: a dict whose keys are all the vertices in the graph, and values are initialize discovered = {} for var in graph. adj: discovered [var] None. #Hint: same keys as above, values initialized to None finished = {} for var in graph. adj: finished [var] = None #Hint: same as above ### END YOUR CODE ### global time #Make sure to use the global variable time = 0 ### START YOUR CODE ### for u in graph.adj: # Specify loop range if visited [u] == None: DFS visit (graph, u, visited, discovered, finished) # Add necessary code ### END YOUR CODE ### return discovered, finished def DFS_visit (graph, vertex, visited, discovered, finished): ### START YOUR CODE ### global time time time 1 visited [vertex] = True discovered [vertex] = time # Add necessary code for v in graph.adj[vertex]: I if visited [v] == None: # Specify loop range DFS visit (graph, v, visited, discovered, finished)# Add necessary code time time 1 finished [vertex] = time# Add necessary code ###END YOUR CODE ### # Do not change the test godo horo CS460 Algorithms and Their Analysis Programming Assignment 6: Graph algorithms Connected Components Created by: Yang Xu, Assistant Professor of Computer Science, San Diego State University Total points: 10 In this assignment, you will implement the topological sort and strongly connected components algorithms. First, you need to copy the code from previous assignment for the Graph class, and the DFS (), DFS_visit() functions to the following cell. Note that the global variable time should also be included. In [2] # Copy the code for Graph class to here. class Graph: pass In [3]: # Copy the code for DFS (), DFS_visit() to here I time= 0# Initialize the gloabl time. def DFS (graph): pass -- Part 2, Topological Sort and Strongly def DFS visit (graph, vertex, visited, discovered, finished): pass Task 1. Topological sort Points: 2 Task 1. Topological sort Points: 2 Implement the topological_sort() function. First, call DFS () on the graph and record the finished time for all vertices. Next, sort the keys of finished dict by its values. Note that the expected output is not fixed, i.e., there can be multiple valid results for topological sort. Hint: you can use the built-in sorted () function and specify the key parameter for sorting. In [ ] def topological_sort (graph): ### START YOUR CODE ### finished = None # Call DFS () sorted_vertices = None # Sort vertices based on their finished times ### END YOUR CODE ### return sorted_vertices Next, build the directed graph as shown in the figure (a) on page 613 in text book, and apply topological sort on it. In [ ] # Construct the graph and apply topological sort raph (directed=True) ### START YOUR CODE ### graph.add_edge ( 'undershorts', 'pants') # Example pass # Add all the edges ### END YOUR CODE ### #Do not change the code below. #Add watch manually graph.adj['watch'] = [] In [ ] Construct the graph and apply topological sort graph Graph (directed=True) ### START YOUR CODE ### graph.add_edge( 'undershorts', 'pants') # Example pass # Add all the edges ### END YOUR CODE ### #Do not change the code below # Add watch manually. graph.adj['watch'] = [] print('Original graph: ') graph.print_graph() print() print('Sorted vertices:') print (topological_sort (graph)) Expected output Original graph: undershorts: pants -> shoes pants belt -> shoes belt: jacket jacket: shirt: belt -> tie tie: jacket socks shoes shoes: watch: Sorted vertices: ['jacket', 'belt', 'shoes', 'pants', 'undershorts', 'tie', 'shirt', 'socks', 'watch'] Task 2. Strongly connected components Points: 8 Implement the algorithm for finding the strongly connected components of a directed graph. First, define the function to transpose a graph, that is, to copy all the vertices and reverse all the edges' direction, and return it as a new graph. (2 points for this part) In [ ] # Transpose a directed graph: 2 points def transpose_graph (graph): transposed Graph (directed=True) # Initialize a new graph } for vertex in graph. adj: ### START YOUR CODE ### pass # Initialize all adjacency lists to empty ### END YOUR CODE ### for vertex, adjacent_vertices in graph. adj. items(): ### START YOUR CODE ### pass # Use a loop to append edges to transposed ### END YOUR CODE ### return transposed In [ ] # Do not change the test code here graph2 Graph (directed=True) graph2.adj = { 'a': 'b'], 'b': ['c', 'e', 'f'], 'c': [ 'd', 'g'], 'd': ['c', 'h'], 'e': ['a', 'f'], 'f': ['g'), 'g': ['f', 'h'], 'h': ['h'] graph2_transposed = transpose_graph (graph2) graph2_transposed.print_graph() Expected output Expected output a: e b:a c: b-> d d: c e: b f: b->e->g g:c-> f h:d->g->h Next, define the function find_component(), which conducts an implicit depth-first search that returns all the vertices contained in a strongly connected component. Note that in this function vertex to a component (3 points for this part) we DO NOT use the previously defined DFS () function, but rather we use a recursive version of DFS that append each visited, list and returns it. In : def find_component (graph, v, visited): visited[v] = True component = [v] ### START YOUR CODE ### for u in None: # Iterate through all adjacent vertices of v if not visited [u]: component += None #Recursive call ### END YOUR CODE ### return component In [ ] Do not change the test code here visited (v: False for v in graph2.adj) return component In [ ] Do not change the test code here visited component print (component) (v: False for v in graph2.adj} find_component (graph2_transposed, 'a', visited) Expected output ['a', 'e', 'b'] Finally, integrate the above defined function into strongly_connected_components (), which finds all the strongly components of a graph, and return them as a list of components, where each component is a list of vertices. Within the function, we first call topological_sort () on the graph and return sorted_vertices, in which all vertices are sorted in the increase order of their finished time. So in the next step we need to call find_component() on each element in sorted_vertices in reversed order. (3 points for this part) In ]: def strongly connected_components (graph): visited (v: False for v in graph. adj} ### START YOUR CODE ### sorted_vertices None # Call topological sort graph_transposed = None # Transpose the graph ### END YOUR CODE ### SCCs = [] ### START YOUR CODE ### for v in None: # Specify the order of iteration through sorted_vertices if not visited [v]: comp = None # Call find_component() SCCs.append(comp) ### END YOUR CODE ### return SCCs Expected output ['a', 'e', 'b'] In [ ]: Finally, integrate the above defined function into strongly connected_components(), which finds all the strongly components of a graph, and return them as a list of components, where each component is a list of vertices. Within the function, we first call topological_sort() on the graph and return sorted_vertices, in which all vertices are sorted in the increase order of their finished time. So in the next step we need to call find_component() on each element in sorted_vertices in reversed order. (3 points for this part) In 1: def strongly connected_components (graph): visited {v: False for v in graph.adj} ### START YOUR CODE ### sorted_vertices = None # Call topological sort graph_transposed = None # Transpose the graph ### END YOUR CODE ### SCCs = [] ### START YOUR CODE ### for v in None: #Specify the order of iteration through sorted_vertices if not visited[v]: comp None #Call find component() SCCs.append(comp) ### END YOUR CODE ### return SCCs #Do not change the test code here SCCs print (SCCs) strongly_connected_components (graph2) Expected output [['a', 'e', 'b'], ['c', 'd'], ['g', 'f'], ['h']]