Language = Python Hi, could you please corrent in following methods to complete this undirected graph class? The test cases are included. Thanks. import heapq from collections import deque class UndirectedGraph: """ Class to implement undirected graph - duplicate edges not allowed - loops not allowed - no edge weights - vertex names are strings """ def __init__(self, start_edges=None): """ Store graph info as adjacency list DO NOT CHANGE THIS METHOD IN ANY WAY """ self.adj_list = dict() # populate graph with initial vertices and edges (if provided) # before using, implement add_vertex() and add_edge() methods if start_edges is not None: for u, v in start_edges: self.add_edge(u, v) def __str__(self): """ Return content of the graph in human-readable form DO NOT CHANGE THIS METHOD IN ANY WAY """ out = [f'{v}: {self.adj_list[v]}' for v in self.adj_list] out = ' '.join(out) if len(out) < 70: out = out.replace(' ', ', ') return f'GRAPH: {{{out}}}' return f'GRAPH: {{ {out}}}' # ------------------------------------------------------------------ # 

def add_vertex(self, v: str) -> None: """ Add new vertex to the graph or nothing if vertex exists. """ if v not in self.adj_list: self.adj_list[v] = []

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def add_edge(self, u: str, v: str) -> None: """ Add edge to the graph """ if u not in self.adj_list.keys(): self.add_vertex(u) if v not in self.adj_list.keys(): self.add_vertex(v) if v not in self.adj_list[u]: self.adj_list[u].append(v) if u not in self.adj_list[v]: self.adj_list[v].append(u)

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def remove_edge(self, v: str, u: str) -> None: """ Remove edge from the graph """ if u not in self.get_vertices() or v not in self.get_vertices(): return if v in self.adj_list[u]: self.adj_list[u].remove(v) if u in self.adj_list[v]: self.adj_list[v].remove(u)

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def remove_vertex(self, v: str) -> None: """ Remove vertex and all connected edges """ if v in self.adj_list.keys(): self.adj_list.pop(v)

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def get_vertices(self) -> []: """ Return list of vertices in the graph (any order) """ return list(self.adj_list.keys())

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def get_edges(self) -> []: """ Return list of edges in the graph (any order) """ e = [] for i in self.adj_list.keys(): for j in self.adj_list[i]: e.append(i+j) return e

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def is_valid_path(self, path: []) -> bool: """ Return true if provided path is valid, False otherwise """ if len(path) <= 1: return True current_node = path[0] for i in range(1, len(path)): if path[i] in self.adj_list[current_node]: current_node = path[i] else: return False return True

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def dfsu(self, v_start, vis, path): a.add(v_start) path.append(v_start) for u in self.adj_list[v_start]: if u in a: continue self.dfsu(u,a,path) def dfs(self, v_start, v_end=None) -> []: """ Return list of vertices visited during DFS search Vertices are picked in alphabetical order """ a = set() path = [] self.dfsu(v_start, vis, path) return path

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def bfs(self, v_start, v_end=None) -> []: """ Return list of vertices visited during BFS search Vertices are picked in alphabetical order """ path = [] vs=[v_start] a=set() while len(vs) > 0: node = vs.pop(0) if node in a: continue a.add(node) path.append(node) for u in self.adj_list[node]: vs.append(u) return path

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def count_connected_components(self): """ Return number of connected componets in the graph """ a=set() count = 0 for i in self.adj_list.keys(): if i not in a: count += 1 self.count_connected_components_util(i,a) return count

#--------------------------------------------------------------------------------------------------------------------------------------------------------

def has_cycle(self): """ Return True if graph contains a cycle, False otherwise """ a=set() for i in self.adj_list.keys(): if i not in a: hasCycle = self.has_cycle_util(i,None,a) if hasCycle: return True return False 

TEST CASES (METHODS MUST PASS ALL OF THESE)

if __name__ == '__main__': print(" PDF - method add_vertex() / add_edge example 1") print("----------------------------------------------") g = UndirectedGraph() print(g) for v in 'ABCDE': g.add_vertex(v) print(g) g.add_vertex('A') print(g) for u, v in ['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', ('B', 'C')]: g.add_edge(u, v) print(g) print(" PDF - method remove_edge() / remove_vertex example 1") print("----------------------------------------------------") g = UndirectedGraph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE']) g.remove_vertex('DOES NOT EXIST') g.remove_edge('A', 'B') g.remove_edge('X', 'B') print(g) g.remove_vertex('D') print(g) print(" PDF - method get_vertices() / get_edges() example 1") print("---------------------------------------------------") g = UndirectedGraph() print(g.get_edges(), g.get_vertices(), sep=' ') g = UndirectedGraph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE']) print(g.get_edges(), g.get_vertices(), sep=' ') print(" PDF - method is_valid_path() example 1") print("--------------------------------------") g = UndirectedGraph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE']) test_cases = ['ABC', 'ADE', 'ECABDCBE', 'ACDECB', '', 'D', 'Z'] for path in test_cases: print(list(path), g.is_valid_path(list(path))) print(" PDF - method dfs() and bfs() example 1") print("--------------------------------------") edges = ['AE', 'AC', 'BE', 'CE', 'CD', 'CB', 'BD', 'ED', 'BH', 'QG', 'FG'] g = UndirectedGraph(edges) test_cases = 'ABCDEGH' for case in test_cases: print(f'{case} DFS:{g.dfs(case)} BFS:{g.bfs(case)}') print('-----') for i in range(1, len(test_cases)): v1, v2 = test_cases[i], test_cases[-1 - i] print(f'{v1}-{v2} DFS:{g.dfs(v1, v2)} BFS:{g.bfs(v1, v2)}') print(" PDF - method count_connected_components() example 1") print("---------------------------------------------------") edges = ['AE', 'AC', 'BE', 'CE', 'CD', 'CB', 'BD', 'ED', 'BH', 'QG', 'FG'] g = UndirectedGraph(edges) test_cases = ( 'add QH', 'remove FG', 'remove GQ', 'remove HQ', 'remove AE', 'remove CA', 'remove EB', 'remove CE', 'remove DE', 'remove BC', 'add EA', 'add EF', 'add GQ', 'add AC', 'add DQ', 'add EG', 'add QH', 'remove CD', 'remove BD', 'remove QG') for case in test_cases: command, edge = case.split() u, v = edge g.add_edge(u, v) if command == 'add' else g.remove_edge(u, v) print(g.count_connected_components(), end=' ') print() print(" PDF - method has_cycle() example 1") print("----------------------------------") edges = ['AE', 'AC', 'BE', 'CE', 'CD', 'CB', 'BD', 'ED', 'BH', 'QG', 'FG'] g = UndirectedGraph(edges) test_cases = ( 'add QH', 'remove FG', 'remove GQ', 'remove HQ', 'remove AE', 'remove CA', 'remove EB', 'remove CE', 'remove DE', 'remove BC', 'add EA', 'add EF', 'add GQ', 'add AC', 'add DQ', 'add EG', 'add QH', 'remove CD', 'remove BD', 'remove QG', 'add FG', 'remove GE') for case in test_cases: command, edge = case.split() u, v = edge g.add_edge(u, v) if command == 'add' else g.remove_edge(u, v) print('{:<10}'.format(case), g.has_cycle())