Language = Python Hi, could you please fill in the 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}}}' # ------------------------------------------------------------------ # # self.adj_list = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['B', 'A'], 'D': ['B']} 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 """ def remove_edge(self, v: str, u: str) -> None: """ Remove edge from the graph """ def remove_vertex(self, v: str) -> None: """ Remove vertex and all connected edges """ def get_vertices(self) -> []: """ Return list of vertices in the graph (any order) """ def get_edges(self) -> []: """ Return list of edges in the graph (any order) """ def is_valid_path(self, path: []) -> bool: """ Return true if provided path is valid, False otherwise """ def dfs(self, v_start, v_end=None) -> []: """ Return list of vertices visited during DFS search Vertices are picked in alphabetical order """ def bfs(self, v_start, v_end=None) -> []: """ Return list of vertices visited during BFS search Vertices are picked in alphabetical order """ def count_connected_components(self): """ Return number of connected componets in the graph """ def has_cycle(self): """ Return True if graph contains a cycle, False otherwise """ 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())