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}}}'

#UNIDRECTED GRAPH IMPLEMNTATION

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

"""

Testing

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)))