Skip to content
AITroveRead. Build. Understand.
Make this comfortable

Python maximum flow: residual edges permit earlier choices to be revised

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A residual network records how much capacity remains on each directed edge and how much existing flow can be undone.

Download Python source kit

Operation contract

The small source-to-sink network has capacity five across its outgoing cut. A breadth-first augmenting-path search repeatedly finds available routes, subtracts bottleneck capacity on forward residual edges and adds it on reverse edges. The returned flow is five. Reverse edges matter when an early route uses capacity needed by a later route; a greedy search that never permits rerouting can stop too early.

Failure and ownership boundary

Capacities are nonnegative bounded integers. This model does not represent cost, fairness or lower bounds, and it does not return the edge-flow decomposition. Python bipartite matching: augment an assignment instead of taking the first free slot can be reduced to flow; Python graph BFS: mark a vertex when it enters the queue explains the path search.

Working program

python
from collections import deque

def maximum_flow(vertex_count, edges, source, sink):
    if type(vertex_count) is not int or not 2 <= vertex_count <= 8 or type(source) is not int or type(sink) is not int or not 0 <= source < vertex_count or not 0 <= sink < vertex_count or source == sink or type(edges) is not list or len(edges) > 40:
        raise ValueError("network bounds")
    residual = [[0] * vertex_count for _ in range(vertex_count)]
    for edge in edges:
        if type(edge) is not tuple or len(edge) != 3 or any(type(value) is not int for value in edge):
            raise ValueError("integer edge")
        start, end, capacity = edge
        if not 0 <= start < vertex_count or not 0 <= end < vertex_count or not 0 <= capacity <= 1000 or start == end:
            raise ValueError("edge fields")
        residual[start][end] += capacity
    total = 0
    while True:
        parent = {source: None}
        pending = deque([source])
        while pending and sink not in parent:
            current = pending.popleft()
            for neighbor, capacity in enumerate(residual[current]):
                if capacity > 0 and neighbor not in parent:
                    parent[neighbor] = current
                    pending.append(neighbor)
        if sink not in parent:
            return total
        bottleneck = float("inf")
        node = sink
        while node != source:
            previous = parent[node]
            bottleneck = min(bottleneck, residual[previous][node])
            node = previous
        node = sink
        while node != source:
            previous = parent[node]
            residual[previous][node] -= bottleneck
            residual[node][previous] += bottleneck
            node = previous
        total += bottleneck

network = [(0, 1, 3), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 3)]
print(maximum_flow(4, network, 0, 3))

Output

Output
5

Costs and limits

This adjacency-matrix version scans O(V^2) entries per BFS. With O(VE) augmentations, the conservative bound is O(V^3 E) time and O(V^2) storage; sparse adjacency lists can reduce per-search cost. The eight-vertex/40-edge gate keeps the fixture small.

Common Mistakes

  • Forward-only residual updates can miss a rerouting path.
  • Maximum flow alone does not supply a minimum-cost or fair allocation.

Connected lessons

Python bipartite matching: augment an assignment instead of taking the first free slot, Python graph BFS: mark a vertex when it enters the queue, Python union-find: connected groups with path compression.

python
max-flow-residual
Storage details