(self, graph: Graph, src: int, dst: int)
| 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 |
nothing calls this directly
no test coverage detected