Removes the given vertex from the graph and deletes all incoming and outgoing edges from the given vertex as well. If the given vertex does not exist, a ValueError will be thrown.
(self, vertex: T)
| 133 | self.vertex_to_index[vertex] = len(self.adj_matrix) - 1 |
| 134 | |
| 135 | def remove_vertex(self, vertex: T) -> None: |
| 136 | """ |
| 137 | Removes the given vertex from the graph and deletes all incoming and |
| 138 | outgoing edges from the given vertex as well. If the given vertex |
| 139 | does not exist, a ValueError will be thrown. |
| 140 | """ |
| 141 | if not self.contains_vertex(vertex): |
| 142 | msg = f"Incorrect input: {vertex} does not exist in this graph." |
| 143 | raise ValueError(msg) |
| 144 | |
| 145 | # first slide up the rows by deleting the row corresponding to |
| 146 | # the vertex being deleted. |
| 147 | start_index = self.vertex_to_index[vertex] |
| 148 | self.adj_matrix.pop(start_index) |
| 149 | |
| 150 | # next, slide the columns to the left by deleting the values in |
| 151 | # the column corresponding to the vertex being deleted |
| 152 | for lst in self.adj_matrix: |
| 153 | lst.pop(start_index) |
| 154 | |
| 155 | # final clean up |
| 156 | self.vertex_to_index.pop(vertex) |
| 157 | |
| 158 | # decrement indices for vertices shifted by the deleted vertex in the adj matrix |
| 159 | for inner_vertex in self.vertex_to_index: |
| 160 | if self.vertex_to_index[inner_vertex] >= start_index: |
| 161 | self.vertex_to_index[inner_vertex] = ( |
| 162 | self.vertex_to_index[inner_vertex] - 1 |
| 163 | ) |
| 164 | |
| 165 | def contains_vertex(self, vertex: T) -> bool: |
| 166 | """ |