Max Flow (Ford–Fulkerson)

The problem

A flow network is a directed graph in which every edge u → v has a capacity c(u, v): the most it can carry, like a pipe’s water per second or a link’s bandwidth. One node is the source s and one the sink t. A flow assigns an amount f(u, v) to every edge so that

1. capacity: 0 ≤ f(u, v) ≤ c(u, v), and
2. conservation: at every node except s and t, what flows in equals what flows out.

The value of the flow is what leaves s (which equals what reaches t). The maximum flow problem asks for the largest possible value. It models road and network traffic, airline scheduling, image segmentation, and, through reductions, matching problems such as assigning students to projects.

The Ford–Fulkerson method

flow ← 0 on every edge
while there is an augmenting path from s to t in the residual graph:
    bottleneck ← the smallest residual capacity on the path
    push the bottleneck along the path
return the flow

The residual graph

The residual graph says where more flow could go. An edge u → v with capacity c and flow f gives two residual edges:

An augmenting path is any path from s to t in the residual graph whose edges all have room > 0.

Why backward edges matter

Take the Diamond network (every capacity 1) and find paths with DFS. The first path DFS finds is s → a → b → t. Now s → a, a → b and b → t are full, and s → b → t is blocked at b → t. Without backward edges the algorithm would stop at flow 1, but the answer is 2.

The residual graph has a backward edge b → a with room 1 (the flow on a → b can be cancelled). So the second path is s → b → a → t: it pushes 1 unit “backwards” over a → b, which removes that flow. The result: s → a → t and s → b → t each carry 1, a → b carries 0, and the flow is 2. Backward edges let the algorithm correct its earlier greedy choices.

The textbook network

Edmonds–Karp (BFS) always takes a path with the fewest edges:

Ford–Fulkerson with DFS finds four paths: s → v1 → v3 → v2 → v4 → t (4), s → v1 → v3 → t (8), s → v2 → v4 → v3 → t (7) and s → v2 → v3 → t (4). The last one goes backwards over v3 → v2, cancelling the 4 units the first path had sent that way. Both reach the same maximum, 23.

Max-flow min-cut theorem

A cut (S, T) splits the nodes into a part S containing s and a part T containing t. Its capacity is the sum of the capacities of the edges from S to T. Every unit of flow has to cross from S to T, so no flow can be larger than any cut.

When Ford–Fulkerson stops, let S be the nodes that s can still reach in the residual graph. Every edge from S to T is full (otherwise its target would be reachable), and every edge from T to S carries no flow (otherwise its backward edge would make its source reachable). So the flow across this cut equals its capacity:

max flow = min cut.

In the textbook network, S = {s, v1, v2, v4} and the cut edges are v1 → v3 (12), v4 → v3 (7) and v4 → t (4): 12 + 7 + 4 = 23. The green nodes in the final frame are S, and the cut edges glow.

Running time

• With integer capacities each augmentation raises the flow by at least 1, so plain Ford–Fulkerson makes at most f* augmentations: *O(E · f)**. That can be terrible. In a network with two paths of capacity 1000 and a middle edge of capacity 1, an unlucky choice of paths alternates over the middle edge and needs 2000 augmentations instead of 2. With irrational capacities it may not even terminate.
• Edmonds–Karp uses BFS, so path lengths never decrease and each edge can be a bottleneck only O(V) times: O(V · E²), whatever the capacities.
• Dinic’s and push–relabel algorithms are faster still in practice.

Code

from collections import deque

CLRS = {('s', 'v1'): 16, ('s', 'v2'): 13, ('v1', 'v3'): 12, ('v2', 'v1'): 4, ('v2', 'v4'): 14,
        ('v3', 'v2'): 9, ('v3', 't'): 20, ('v4', 'v3'): 7, ('v4', 't'): 4}
DIAMOND = {('s', 'a'): 1, ('s', 'b'): 1, ('a', 'b'): 1, ('a', 't'): 1, ('b', 't'): 1}

def find_path(residual, s, t, use_bfs):
    """An s-t path in the residual graph (only edges with room left), as a parent map."""
    parent = {s: None}
    if use_bfs:                                          # Edmonds-Karp: fewest edges first
        queue = deque([s])
        while queue and t not in parent:
            u = queue.popleft()
            for v, room in residual[u].items():
                if room > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
    else:                                                # plain depth-first search
        def dfs(u):
            for v, room in residual[u].items():
                if room > 0 and v not in parent:
                    parent[v] = u
                    if v == t or dfs(v):
                        return True
            return False
        dfs(s)
    return parent if t in parent else None

def max_flow(capacity, s, t, use_bfs=True):
    residual = {}
    for (u, v), c in capacity.items():
        residual.setdefault(u, {})[v] = c
        residual.setdefault(v, {}).setdefault(u, 0)      # the reverse edge starts with no room
    flow, steps = 0, []
    while (parent := find_path(residual, s, t, use_bfs)):
        path, v = [], t
        while v != s:
            path.append((parent[v], v))
            v = parent[v]
        path.reverse()
        push = min(residual[u][v] for u, v in path)       # the bottleneck
        for u, v in path:
            residual[u][v] -= push
            residual[v][u] += push                        # room to undo this flow later
        flow += push
        steps.append((' '.join([s] + [v for _, v in path]), push))
    reach, queue = {s}, deque([s])                       # min cut: everything s can still reach
    while queue:
        u = queue.popleft()
        for v, room in residual[u].items():
            if room > 0 and v not in reach:
                reach.add(v)
                queue.append(v)
    cut = [e for e in capacity if e[0] in reach and e[1] not in reach]
    return flow, steps, cut

for name, net in (('CLRS', CLRS), ('diamond', DIAMOND)):
    for bfs in (True, False):
        flow, steps, cut = max_flow(net, 's', 't', bfs)
        print(name, 'BFS' if bfs else 'DFS', 'flow', flow, steps, 'cut', cut)
# CLRS BFS flow 23 [('s v1 v3 t', 12), ('s v2 v4 t', 4), ('s v2 v4 v3 t', 7)] cut [('v1', 'v3'), ('v4', 'v3'), ('v4', 't')]
# CLRS DFS flow 23 [('s v1 v3 v2 v4 t', 4), ('s v1 v3 t', 8), ('s v2 v4 v3 t', 7), ('s v2 v3 t', 4)] cut [('v1', 'v3'), ('v4', 'v3'), ('v4', 't')]
# diamond BFS flow 2 [('s a t', 1), ('s b t', 1)] cut [('s', 'a'), ('s', 'b')]
# diamond DFS flow 2 [('s a b t', 1), ('s b a t', 1)] cut [('s', 'a'), ('s', 'b')]

networkx.maximum_flow_value and networkx.minimum_cut give the same 23 for the textbook network.

Common mistakes

• Forgetting the backward edges. Without them the greedy method can get stuck below the maximum.
• Taking the largest capacity on a path. The amount you can push is the smallest residual capacity, the bottleneck.
• Computing the cut capacity with edges in both directions. Only edges from S to T count; edges from T to S are not added (and carry no flow at the end).
• Thinking Ford–Fulkerson is always fast. The choice of paths matters. Use BFS (Edmonds–Karp) for a guaranteed polynomial bound.
• Confusing the minimum cut with the edges of minimum capacity. A cut must separate s from t completely.