This shortest path function returns a string, describing the result: 1.) No path is found. The string is a human readable message to indicate this. 2.) The shortest path is found. The string is in the form `v1(->v2->v3->...->vn)`, where v1 is the source vertex an
(self, target_vertex: str)
| 47 | queue.append(adjacent_vertex) |
| 48 | |
| 49 | def shortest_path(self, target_vertex: str) -> str: |
| 50 | """ |
| 51 | This shortest path function returns a string, describing the result: |
| 52 | 1.) No path is found. The string is a human readable message to indicate this. |
| 53 | 2.) The shortest path is found. The string is in the form |
| 54 | `v1(->v2->v3->...->vn)`, where v1 is the source vertex and vn is the target |
| 55 | vertex, if it exists separately. |
| 56 | |
| 57 | >>> g = Graph(graph, "G") |
| 58 | >>> g.breath_first_search() |
| 59 | |
| 60 | Case 1 - No path is found. |
| 61 | >>> g.shortest_path("Foo") |
| 62 | Traceback (most recent call last): |
| 63 | ... |
| 64 | ValueError: No path from vertex: G to vertex: Foo |
| 65 | |
| 66 | Case 2 - The path is found. |
| 67 | >>> g.shortest_path("D") |
| 68 | 'G->C->A->B->D' |
| 69 | >>> g.shortest_path("G") |
| 70 | 'G' |
| 71 | """ |
| 72 | if target_vertex == self.source_vertex: |
| 73 | return self.source_vertex |
| 74 | |
| 75 | target_vertex_parent = self.parent.get(target_vertex) |
| 76 | if target_vertex_parent is None: |
| 77 | msg = ( |
| 78 | f"No path from vertex: {self.source_vertex} to vertex: {target_vertex}" |
| 79 | ) |
| 80 | raise ValueError(msg) |
| 81 | |
| 82 | return self.shortest_path(target_vertex_parent) + f"->{target_vertex}" |
| 83 | |
| 84 | |
| 85 | if __name__ == "__main__": |
no test coverage detected