| 24 | |
| 25 | |
| 26 | class MaxFlow: |
| 27 | def __init__(self, graph: Graph, src: int, dst: int) -> None: |
| 28 | assert ( |
| 29 | graph.node_count > src >= 0 |
| 30 | ), "src node out of range, expected [0, {}), got {}".format( |
| 31 | graph.node_count, src |
| 32 | ) |
| 33 | assert ( |
| 34 | graph.node_count > dst >= 0 |
| 35 | ), "dst node out of range, expected [0, {}), got {}".format( |
| 36 | graph.node_count, dst |
| 37 | ) |
| 38 | |
| 39 | self.src = src |
| 40 | self.dst = dst |
| 41 | self.graph = graph |
| 42 | self.adjacent_edges: List[List[Edge]] = [[] for _ in range(graph.node_count)] |
| 43 | self.edges_dict: Dict[Tuple[int, int], Edge] = {} |
| 44 | |
| 45 | for source, target, weight in self.graph.iterate_edges(): |
| 46 | if (source, target) in self.edges_dict: |
| 47 | self.edges_dict[(source, target)].capacity += weight |
| 48 | else: |
| 49 | self.edges_dict[(source, target)] = Edge( |
| 50 | from_node=source, to_node=target, capacity=weight |
| 51 | ) |
| 52 | self.edges_dict[(target, source)] = Edge( |
| 53 | from_node=target, to_node=source, capacity=0 |
| 54 | ) |
| 55 | self.adjacent_edges[source].append(self.edges_dict[(source, target)]) |
| 56 | self.adjacent_edges[target].append(self.edges_dict[(target, source)]) |
| 57 | |
| 58 | self.max_flow = self.compute_max_flow() |
| 59 | |
| 60 | def compute_max_flow(self) -> int: |
| 61 | max_flow = 0 |
| 62 | while True: |
| 63 | augmenting_path = self.find_augmenting_path() |
| 64 | if not augmenting_path: |
| 65 | break |
| 66 | bottleneck = min([edge.capacity - edge.flow for edge in augmenting_path]) |
| 67 | for edge in augmenting_path: |
| 68 | edge.flow += bottleneck |
| 69 | self.edges_dict[(edge.to_node, edge.from_node)].flow -= bottleneck |
| 70 | max_flow += bottleneck |
| 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 |
no outgoing calls
no test coverage detected