| 29 | |
| 30 | |
| 31 | class GraphAdjacencyMatrix[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.directed = directed |
| 45 | self.vertex_to_index: dict[T, int] = {} |
| 46 | self.adj_matrix: list[list[int]] = [] |
| 47 | |
| 48 | # Falsey checks |
| 49 | edges = edges or [] |
| 50 | vertices = vertices or [] |
| 51 | |
| 52 | for vertex in vertices: |
| 53 | self.add_vertex(vertex) |
| 54 | |
| 55 | for edge in edges: |
| 56 | if len(edge) != 2: |
| 57 | msg = f"Invalid input: {edge} must have length 2." |
| 58 | raise ValueError(msg) |
| 59 | self.add_edge(edge[0], edge[1]) |
| 60 | |
| 61 | def add_edge(self, source_vertex: T, destination_vertex: T) -> None: |
| 62 | """ |
| 63 | Creates an edge from source vertex to destination vertex. If any |
| 64 | given vertex doesn't exist or the edge already exists, a ValueError |
| 65 | will be thrown. |
| 66 | """ |
| 67 | if not ( |
| 68 | self.contains_vertex(source_vertex) |
| 69 | and self.contains_vertex(destination_vertex) |
| 70 | ): |
| 71 | msg = ( |
| 72 | f"Incorrect input: Either {source_vertex} or " |
| 73 | f"{destination_vertex} does not exist" |
| 74 | ) |
| 75 | raise ValueError(msg) |
| 76 | if self.contains_edge(source_vertex, destination_vertex): |
| 77 | msg = ( |
| 78 | "Incorrect input: The edge already exists between " |
| 79 | f"{source_vertex} and {destination_vertex}" |
| 80 | ) |
| 81 | raise ValueError(msg) |
| 82 | |
| 83 | # Get the indices of the corresponding vertices and set their edge value to 1. |
| 84 | u: int = self.vertex_to_index[source_vertex] |
| 85 | v: int = self.vertex_to_index[destination_vertex] |
| 86 | self.adj_matrix[u][v] = 1 |
| 87 | if not self.directed: |
| 88 | self.adj_matrix[v][u] = 1 |
no outgoing calls