A residual network records how much capacity remains on each directed edge and how much existing flow can be undone.
Python maximum flow: residual edges permit earlier choices to be revised
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
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
5Costs 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.
