Maximum flow, minimum cut and bipartite matching

Maximum flow asks how much can travel from a source s to a sink t through a network whose edges have capacities, when every other node passes on exactly what it receives. Ford and Fulkerson proved in 1956 that the answer equals the capacity of a minimum cut, the cheapest set of edges whose removal separates s from t. Their method keeps sending more along an augmenting path of the residual graph, in which every edge also has a reverse edge that can take flow back, until no such path is left. Edmonds and Karp showed in 1972 that choosing each time a path with the fewest edges, found by breadth-first search, needs O(VE) augmentations and O(VE²) time, whatever the capacities. Bipartite matching, pairing people with tasks they accept, is a maximum flow in which every capacity is 1.

Flow networks and residual graphs

A flow network is a directed graph with a capacity c(u, v) ≥ 0 on each edge. A flow gives each edge an amount f(u, v) between 0 and c(u, v), and at every node except s and t the total coming in equals the total going out; the value of the flow is what leaves s. Given a flow, the residual graph has two edges for each pipe: a forward edge with the room left, c − f, and a reverse edge with capacity f, which takes flow back. An augmenting path is a path from s to t in the residual graph. Its smallest residual capacity, the bottleneck, can be added along the whole path: forward edges carry more, reverse edges carry less. Storing each pipe next to its reverse, at positions 2k and 2k + 1, makes the partner of edge e simply e XOR 1.

Edmonds-Karp on a water network

1. Find an augmenting path with the fewest edges, by breadth-first search over residual edges whose capacity is above 0.
2. If there is none, stop: the flow is maximum.
3. Otherwise take the path’s bottleneck b, subtract b from every edge on the path and add b to each partner edge.

Here is a made-up network from a reservoir R through pumping stations A to D to a town’s tank T, with capacities in litres per second:

# Edmonds-Karp on a made-up water network: a reservoir R, four pumping stations A to D and the town's tank T, with the
# capacity of every pipe in litres per second. Each augmenting path is printed with its bottleneck; a step backwards
# along a pipe takes back water already sent through it. At the end, the towns the last search could still reach
# give a minimum cut.
from collections import deque

PIPES = [("R", "A", 70), ("R", "D", 60), ("A", "B", 60), ("A", "C", 40),
         ("B", "T", 60), ("C", "D", 80), ("C", "T", 50), ("D", "B", 40)]
NODES = ["R", "A", "B", "C", "D", "T"]

# Edges in pairs: edge i is a pipe and edge i ^ 1 its reverse, which starts with capacity 0.
head = {v: [] for v in NODES}
to, cap = [], []
for u, v, c in PIPES:
    head[u].append(len(to)); to.append(v); cap.append(c)
    head[v].append(len(to)); to.append(u); cap.append(0)


def bfs(s, t):
    """Shortest augmenting path by number of pipes: parent edge of every node reached, or None if t is not."""
    parent = {s: None}
    queue = deque([s])
    while queue:
        u = queue.popleft()
        for e in head[u]:
            if cap[e] > 0 and to[e] not in parent:
                parent[to[e]] = e
                queue.append(to[e])
    return parent


flow = 0
while True:
    parent = bfs("R", "T")
    if "T" not in parent:
        break
    path, v = [], "T"
    while parent[v] is not None:
        path.append(parent[v])
        v = to[parent[v] ^ 1]
    path.reverse()
    bottleneck = min(cap[e] for e in path)
    for e in path:
        cap[e] -= bottleneck
        cap[e ^ 1] += bottleneck
    flow += bottleneck
    stops = ", ".join(["R"] + [to[e] for e in path])
    back = [f"{to[e ^ 1]} to {to[e]} against the pipe {to[e]}->{to[e ^ 1]}" for e in path if e % 2]
    note = f" ({'; '.join(back)})" if back else ""
    print(f"path {stops}{note}: {bottleneck} L/s more, {flow} L/s in all")

print(f"maximum flow: {flow} L/s")
for i, (u, v, c) in enumerate(PIPES):
    print(f"  {u}->{v}: {cap[2 * i + 1]:>2} of {c}")
reached = bfs("R", "T")
side = [v for v in NODES if v in reached]
cut = [(u, v, c) for u, v, c in PIPES if u in reached and v not in reached]
print(f"the last search reached {', '.join(side)}; the pipes leaving that side form a minimum cut:")
print("  " + " + ".join(f"{u}->{v} {c}" for u, v, c in cut) + f" = {sum(c for _, _, c in cut)} L/s")

path R, A, B, T: 60 L/s more, 60 L/s in all
path R, A, C, T: 10 L/s more, 70 L/s in all
path R, D, B, A, C, T (B to A against the pipe A->B): 30 L/s more, 100 L/s in all
maximum flow: 100 L/s
  R->A: 70 of 70
  R->D: 30 of 60
  A->B: 30 of 60
  A->C: 40 of 40
  B->T: 60 of 60
  C->D:  0 of 80
  C->T: 40 of 50
  D->B: 30 of 40
the last search reached R, A, B, D; the pipes leaving that side form a minimum cut:
  A->C 40 + B->T 60 = 100 L/s

The first two paths fill the pipe from B to the tank and send 10 L/s through C. The third is the instructive one: it runs from R through D to B, then from B to A against the pipe A–B, and on through C to the tank. Taking 30 L/s back along A–B sends that much of A’s water to C instead, while water from D replaces it at B. Without reverse edges the search would have been stuck at 70 L/s: no forward path was left. When no path remains, the last search has reached R, A, B and D, and the two pipes leaving that set, A–C and B–T, are full and add up to 100 L/s, the flow itself.

Maximum flow equals minimum cut

Every cut bounds every flow: each litre from s to t crosses from s’s side to t’s side, so no flow can exceed the capacity of the pipes that leave s’s side. When the algorithm stops, the side it last reached has only full pipes leaving it and only empty pipes entering it, so for that cut the bound is met exactly. The flow is therefore maximum and the cut minimum, which is the max-flow min-cut theorem, and the certificate comes free with the last search.

Bipartite matching as a flow

A bipartite graph has two groups, here interns and projects, with edges only between the groups, and a matching pairs some of them with each vertex used at most once. To find a largest matching, add a source with an edge of capacity 1 to every intern, an edge of capacity 1 from every project to a sink, and capacity 1 on every pair an intern accepts. Each augmenting path then adds one pair, and its reverse edges can move interns who are already placed:

# Bipartite matching as a maximum flow: six made-up interns, each with the projects they would accept, and five
# projects that take one intern each. Source -> intern and project -> sink edges have capacity 1, and so does every
# intern -> project edge, so each augmenting path adds one pair, possibly moving an intern to another project.
from collections import deque

ACCEPTS = {
    "Asha": ["Maps", "Search"],
    "Bilal": ["Maps"],
    "Chen": ["Search", "Payments", "Chat"],
    "Dara": ["Maps"],
    "Emil": ["Chat", "Fraud"],
    "Farah": ["Payments"],
}
PROJECTS = ["Maps", "Search", "Payments", "Chat", "Fraud"]
NODES = ["source", *ACCEPTS, *PROJECTS, "sink"]

head = {v: [] for v in NODES}
to, cap = [], []


def add(u, v):
    head[u].append(len(to)); to.append(v); cap.append(1)
    head[v].append(len(to)); to.append(u); cap.append(0)


for intern in ACCEPTS:
    add("source", intern)
for intern, projects in ACCEPTS.items():
    for project in projects:
        add(intern, project)
for project in PROJECTS:
    add(project, "sink")

pairs = 0
while True:
    parent, queue = {"source": None}, deque(["source"])
    while queue and "sink" not in parent:
        u = queue.popleft()
        for e in head[u]:
            if cap[e] > 0 and to[e] not in parent:
                parent[to[e]] = e
                queue.append(to[e])
    if "sink" not in parent:
        break
    path, v = [], "sink"
    while parent[v] is not None:
        path.append(parent[v])
        v = to[parent[v] ^ 1]
    for e in path:
        cap[e] -= 1
        cap[e ^ 1] += 1
    pairs += 1
    inner = [to[e] for e in reversed(path)][:-1]  # the interns and projects on the path, without the sink
    moves = [f"{to[e]} gives up {to[e ^ 1]}" for e in reversed(path) if e % 2]
    print(f"path {pairs}: {' - '.join(inner)}" + (f" ({'; '.join(moves)})" if moves else ""))

print(f"maximum matching: {pairs} pairs")
for intern, projects in ACCEPTS.items():
    got = [to[e] for e in head[intern] if to[e] in PROJECTS and e % 2 == 0 and cap[e] == 0]
    print(f"  {intern:<6}{got[0] if got else '(no project)'}")

path 1: Asha - Maps
path 2: Chen - Search
path 3: Emil - Chat
path 4: Farah - Payments
path 5: Bilal - Maps - Asha - Search - Chen - Chat - Emil - Fraud (Asha gives up Maps; Chen gives up Search; Emil gives up Chat)
maximum matching: 5 pairs
  Asha  Search
  Bilal Maps
  Chen  Chat
  Dara  (no project)
  Emil  Fraud
  Farah Payments

The fifth path places Bilal on Maps by moving Asha to Search, Chen to Chat and Emil to Fraud, all in one augmentation. Dara stays without a project, and no matching does better: Bilal and Dara accept only Maps, so one of them has to miss out. Hopcroft and Karp’s algorithm of 1973 augments along many shortest paths per phase and runs in O(E√V). Disjoint routes, capacities on nodes and the smallest cover of a bipartite graph reduce to the same algorithm.

Exercise and self-check

Write Edmonds-Karp for any list of one-way pipes, then check it against a brute force that tries every cut of 300 small networks.

def max_flow(n, pipes, s, t):
    """n nodes 0 .. n - 1; pipes: [(u, v, capacity)], one way each. The maximum flow from s to t."""
    raise NotImplementedError("write max_flow")

import random
from itertools import product

from flow import max_flow

WATER = [  # the lesson's network: R, A, B, C, D and T numbered 0 to 5
    (0, 1, 70), (0, 4, 60), (1, 2, 60), (1, 3, 40), (2, 5, 60), (3, 4, 80), (3, 5, 50), (4, 2, 40),
]


def smallest_cut(n, pipes, s, t):
    """the smallest total capacity of the pipes leaving a side that holds s but not t"""
    others = [v for v in range(n) if v not in (s, t)]
    best = None
    for picks in product((False, True), repeat=len(others)):
        side = {s, *(v for v, p in zip(others, picks) if p)}
        cut = sum(c for u, v, c in pipes if u in side and v not in side)
        best = cut if best is None else min(best, cut)
    return best


def test_water_network():
    """the lesson's water network carries 100 litres a second"""
    assert max_flow(6, WATER, 0, 5) == 100


def test_no_route():
    """no route from s to t: nothing flows"""
    assert max_flow(4, [(0, 1, 5), (2, 3, 7), (3, 1, 2)], 0, 3) == 0


def test_repeated_and_opposite_pipes():
    """two pipes between the same nodes add up, and a pipe back towards s does not help"""
    assert max_flow(2, [(0, 1, 3), (0, 1, 4)], 0, 1) == 7
    assert max_flow(3, [(0, 1, 5), (1, 0, 5), (1, 2, 4), (2, 1, 9)], 0, 2) == 4


def test_random_networks():
    """300 random networks of 2 to 7 nodes: the flow equals the smallest cut"""
    rng = random.Random(56)
    for _ in range(300):
        n = rng.randint(2, 7)
        pipes = [(rng.randrange(n), rng.randrange(n), rng.randint(1, 9)) for _ in range(rng.randint(0, 14))]
        pipes = [(u, v, c) for u, v, c in pipes if u != v]
        assert max_flow(n, pipes, 0, n - 1) == smallest_cut(n, pipes, 0, n - 1), (n, pipes)


def test_large_capacities():
    """200 nodes and 2,000 pipes with capacities up to 10^9: the maximum flow is 2,338,927,616"""
    state = 97

    def below(k):
        nonlocal state
        state = state * 48271 % 2147483647
        return state % k

    n, pipes = 200, []
    while len(pipes) < 2000:
        u, v = below(n), below(n)
        if u != v:
            pipes.append((u, v, 1 + below(10**9)))
    assert max_flow(n, pipes, 0, n - 1) == 2338927616

/** n nodes 0 .. n - 1; pipes: [[u, v, capacity]], one way each. The maximum flow from s to t. */
export function maxFlow(n, pipes, s, t) {
  throw new Error('write maxFlow');
}

import { test, assert } from 'mysmartcopilot:test';
import { maxFlow } from './flow.mjs';

const WATER = [ // the lesson's network: R, A, B, C, D and T numbered 0 to 5
  [0, 1, 70], [0, 4, 60], [1, 2, 60], [1, 3, 40], [2, 5, 60], [3, 4, 80], [3, 5, 50], [4, 2, 40],
];

function smallestCut(n, pipes, s, t) {
  const others = [];
  for (let v = 0; v < n; v++) if (v !== s && v !== t) others.push(v);
  let best = null;
  for (let mask = 0; mask < 1 << others.length; mask++) {
    const side = new Set([s]);
    others.forEach((v, i) => { if (mask & (1 << i)) side.add(v); });
    let cut = 0;
    for (const [u, v, c] of pipes) if (side.has(u) && !side.has(v)) cut += c;
    best = best === null ? cut : Math.min(best, cut);
  }
  return best;
}

function lcg(seed) {
  let state = seed;
  return (k) => {
    state = (state * 48271) % 2147483647;
    return state % k;
  };
}

test("the lesson's water network carries 100 litres a second", () => {
  assert.equal(maxFlow(6, WATER, 0, 5), 100);
});

test('no route from s to t: nothing flows', () => {
  assert.equal(maxFlow(4, [[0, 1, 5], [2, 3, 7], [3, 1, 2]], 0, 3), 0);
});

test('two pipes between the same nodes add up, and a pipe back towards s does not help', () => {
  assert.equal(maxFlow(2, [[0, 1, 3], [0, 1, 4]], 0, 1), 7);
  assert.equal(maxFlow(3, [[0, 1, 5], [1, 0, 5], [1, 2, 4], [2, 1, 9]], 0, 2), 4);
});

test('300 random networks of 2 to 7 nodes: the flow equals the smallest cut', () => {
  const below = lcg(56);
  for (let k = 0; k < 300; k++) {
    const n = 2 + below(6);
    const pipes = [];
    for (let i = below(15); i > 0; i--) {
      const u = below(n), v = below(n), c = 1 + below(9);
      if (u !== v) pipes.push([u, v, c]);
    }
    assert.equal(maxFlow(n, pipes, 0, n - 1), smallestCut(n, pipes, 0, n - 1), JSON.stringify([n, pipes]));
  }
});

test('200 nodes and 2,000 pipes with capacities up to 10^9: the maximum flow is 2,338,927,616', () => {
  const below = lcg(97);
  const n = 200, pipes = [];
  while (pipes.length < 2000) {
    const u = below(n), v = below(n);
    if (u !== v) pipes.push([u, v, 1 + below(10 ** 9)]);
  }
  assert.equal(maxFlow(n, pipes, 0, n - 1), 2338927616);
});

Why the flow equals the cut, and why shortest paths stop the search soon Pro: opens with a Pro, Premium or Ultimate pass

Edmonds-Karp on 5,000 pipes in five languages, with run records Pro: opens with a Pro, Premium or Ultimate pass

Modelling with flows: covers, disjoint routes and Hopcroft-Karp Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A maximum flow sends as much as possible from s to t within the capacities, and its value equals the capacity of a minimum cut.
• The residual graph pairs every edge with a reverse edge, so later augmenting paths can take back earlier choices.
• Edmonds-Karp takes shortest augmenting paths by breadth-first search: O(VE) augmentations, whatever the capacities.
• Bipartite matching is a maximum flow with capacities of 1; of the six interns it placed five, each on a project they accept.