| 71 | return max_flow |
| 72 | |
| 73 | def find_augmenting_path(self) -> Optional[List[Edge]]: |
| 74 | # BFS |
| 75 | visited = [False] * self.graph.node_count |
| 76 | visited[self.src] = True |
| 77 | queue = [self.src] |
| 78 | prev: List[Union[None, Edge]] = [None] * self.graph.node_count |
| 79 | while queue: |
| 80 | node = queue.pop(0) |
| 81 | for edge in self.adjacent_edges[node]: |
| 82 | if not visited[edge.to_node] and edge.capacity > edge.flow: |
| 83 | visited[edge.to_node] = True |
| 84 | prev[edge.to_node] = edge |
| 85 | queue.append(edge.to_node) |
| 86 | if edge.to_node == self.dst: |
| 87 | break |
| 88 | if not visited[self.dst]: |
| 89 | return None |
| 90 | flow_path = [] |
| 91 | node = self.dst |
| 92 | while prev[node]: |
| 93 | flow_path.append(prev[node]) |
| 94 | node = prev[node].from_node |
| 95 | flow_path.reverse() |
| 96 | return flow_path |
| 97 | |
| 98 | |
| 99 | if __name__ == "__main__": |