| 29 | |
| 30 | |
| 31 | class GraphAdjacencyList[T]: |
| 32 | def __init__( |
| 33 | self, vertices: list[T], edges: list[list[T]], directed: bool = True |
| 34 | ) -> None: |
| 35 | """ |
| 36 | Parameters: |
| 37 | - vertices: (list[T]) The list of vertex names the client wants to |
| 38 | pass in. Default is empty. |
| 39 | - edges: (list[list[T]]) The list of edges the client wants to |
| 40 | pass in. Each edge is a 2-element list. Default is empty. |
| 41 | - directed: (bool) Indicates if graph is directed or undirected. |
| 42 | Default is True. |
| 43 | """ |
| 44 | self.adj_list: dict[T, list[T]] = {} # dictionary of lists of T |
| 45 | self.directed = directed |
| 46 | |
| 47 | # Falsey checks |
| 48 | edges = edges or [] |
| 49 | vertices = vertices or [] |
| 50 | |
| 51 | for vertex in vertices: |
| 52 | self.add_vertex(vertex) |
| 53 | |
| 54 | for edge in edges: |
| 55 | if len(edge) != 2: |
| 56 | msg = f"Invalid input: {edge} is the wrong length." |
| 57 | raise ValueError(msg) |
| 58 | self.add_edge(edge[0], edge[1]) |
| 59 | |
| 60 | def add_vertex(self, vertex: T) -> None: |
| 61 | """ |
| 62 | Adds a vertex to the graph. If the given vertex already exists, |
| 63 | a ValueError will be thrown. |
| 64 | |
| 65 | >>> g = GraphAdjacencyList(vertices=[], edges=[], directed=False) |
| 66 | >>> g.add_vertex("A") |
| 67 | >>> g.adj_list |
| 68 | {'A': []} |
| 69 | >>> g.add_vertex("A") |
| 70 | Traceback (most recent call last): |
| 71 | ... |
| 72 | ValueError: Incorrect input: A is already in the graph. |
| 73 | """ |
| 74 | if self.contains_vertex(vertex): |
| 75 | msg = f"Incorrect input: {vertex} is already in the graph." |
| 76 | raise ValueError(msg) |
| 77 | self.adj_list[vertex] = [] |
| 78 | |
| 79 | def add_edge(self, source_vertex: T, destination_vertex: T) -> None: |
| 80 | """ |
| 81 | Creates an edge from source vertex to destination vertex. If any |
| 82 | given vertex doesn't exist or the edge already exists, a ValueError |
| 83 | will be thrown. |
| 84 | """ |
| 85 | if not ( |
| 86 | self.contains_vertex(source_vertex) |
| 87 | and self.contains_vertex(destination_vertex) |
| 88 | ): |
no outgoing calls