Max Flow

in reviewThis lesson is complete and being validated before release - details may still change.

Max flow

Loading interactive demo…

One-way pipes from a source to a sink, each labelled with the flow it carries of its capacity. Every round a breadth-first search walks only arcs with room: pipes below capacity, and dashed reverse arcs that offer to cancel flow already placed. The path it finds carries its bottleneck, the least room along it; when no path remains, the nodes the search reached are the source side of a cut whose capacity equals the flow.Take the tour, or press and explore. Legend:

The panel beside the stage is the real MaxFlow class from the published library executing in your browser, with the current line highlighted.

The source; once the last search fails, every node on its side of the cut.
The sink, and a pipe filled to its capacity.
A pipe carrying some flow, as thick as its share of capacity.
Nodes the current round's search has reached, hollow.
The augmenting path and the arc being pushed along.
Dashed reverse arcs: the room to undo flow a pipe carries.
The cut: the pipes leaving the source side, all full.

flow sums every bottleneck pushed, paths counts the rounds that reached the sink, bottleneck is the least room on the path just found, cut the capacity across the cut once a search fails. The strips list the paths in order and read the tapped node's flow in and out. The narration numbers nodes in network order; the stage shows their names.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The problem. A flow network is a directed graph with a capacity $c(u, v) \ge 0$ on every edge, a source $s$ and a sink $t$ . A flow $f$ assigns every edge an amount with $0 \le f(u, v) \le c(u, v)$ , and conserves at every node but $s$ and $t$ : what enters equals what leaves. Its value is the net amount leaving $s$ . The question is the largest value any flow can have.

The residual graph. Given a flow, each edge offers two arcs: a forward arc with room $c(u, v) - f(u, v)$ , and a reverse arc from $v$ back to $u$ with room $f(u, v)$ , the amount that could be cancelled. A path from $s$ to $t$ along arcs with room is an augmenting path, and pushing its bottleneck, the least room along it, along every arc gives a flow that is larger by the bottleneck and still feasible: forward arcs stay within capacity by construction, reverse arcs never go below zero, and conservation holds because every inner node of the path gains and loses the same amount. The reverse arcs are what make this greedy method safe: a poor early path can be partly undone later, as the matching network shows when its third path cancels two pairings.

Cuts. An $s$ - $t$ cut splits the nodes into $S \ni s$ and $T \ni t$ ; its capacity is the sum of $c(u, v)$ over edges from $S$ to $T$ . Any flow must cross any cut, so the value of every flow is at most the capacity of every cut. When a search from $s$ fails to reach $t$ , let $S$ be the nodes it reached. No arc with room leaves $S$ , so every edge from $S$ to $T$ is saturated and every edge from $T$ to $S$ is empty, and the flow across the cut equals its capacity. A flow that equals a cut is a maximum flow and the cut is a minimum cut: the max-flow min-cut theorem, and the termination proof in one.

Why breadth first. Ford and Fulkerson's method works with any augmenting path. With integer capacities each round adds at least one unit, so it stops, but after up to as many rounds as the maximum flow; with irrational capacities it need not stop at all. Edmonds and Karp choose the path with the fewest arcs each round. The distance from $s$ to every node in the residual graph then never decreases, and each edge can be the bottleneck at most $V/2$ times, so there are at most $O(VE)$ rounds of an $O(E)$ search: $O(V E^2)$ in all, independent of the capacities. Dinitz's phases, push-relabel, and later methods are faster still; the invariant is the same.

Integrality. With integer capacities every bottleneck is an integer and so is every flow, which is why unit capacities turn a matching into a flow and back: no half-matched pairs can appear.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Every edge owns two arcs, 2e forward and 2e + 1 reverse, in one adjacency structure; the residual of a forward arc is capacity minus flow, of a reverse arc the flow itself, so one push moves both at once.
Adjacency is in edge order, forward arcs at the tail, reverse at the head, and the queue is first in first out, so the paths shown are the ones the fixture pins and the same run repeats exactly.
The search stops the moment the sink is reached, not when the queue empties: everything still queued is left unexplored, which is why the ringed set at a path event is smaller than at a cut.
The bottleneck is measured before any push, by walking the parent arcs back and taking the least residual, so every arc of the path receives the same amount.
The cut is read from the last, failed search: the nodes it reached are the source side, and the original edges leaving that set are filtered from the edge list, never recomputed from the flows.
run resets the network first, so the same network can be solved again from empty and the result is the same.

The problem came out of the Cold War. In 1955 T. E. Harris and F. S. Ross wrote a secret RAND report on the rail network carrying freight from the Soviet Union into Eastern Europe, 44 regions and 105 links with tonnage capacities, asking how much could move and which links to cut to stop it. Lester Ford and Delbert Fulkerson, also at RAND, abstracted it into flow through a network, proved that the most that can flow equals the least that must be cut, and gave the augmenting path method. Choosing the paths breadth first, as run here, came from Dinitz and from Edmonds and Karp independently.

1955T. E. Harris and F. S. Ross - Write the secret RAND report 'Fundamentals of a Method for Evaluating Rail Net Capacities' on the Soviet and satellite railway network, the source Ford and Fulkerson cite for the problem.source
1956L. R. Ford Jr. and D. R. Fulkerson - Publish 'Maximal flow through a network' in the Canadian Journal of Mathematics: the augmenting path method and the max-flow min-cut theorem.source
1970Yefim Dinitz - Publishes a polynomial-time algorithm that augments along shortest paths in phases, the first to bound the number of augmentations; the Edmonds-Karp idea is a special case.source
1972Jack Edmonds and Richard Karp - Show in the Journal of the ACM that choosing each augmenting path by breadth-first search bounds the rounds by V times E, so the method runs in O(V E squared).source
1999The Harris and Ross report is declassified, and its drawing of the rail network with the bottleneck marked becomes the opening figure of the problem's history.source

Used today

Bipartite matching - Unit pipes from a source through two sides to a sink: the maximum flow is the largest matching, and reverse arcs are what let a later pairing displace an earlier one.
Image segmentation - Pixels as nodes, neighbouring similarity as capacities, foreground and background as source and sink: the minimum cut is the object's outline.
Scheduling and assignment - Jobs to machines, shifts to workers, projects to budgets: a feasible assignment exists exactly when the flow saturates the demands.
Baseball elimination - Whether a team can still finish first is a single max flow over the games left, a question first answered that way in the 1960s.

Did you know

The report that started it modelled the Soviet rail network as 44 vertices and 105 edges, found a maximum flow of 163,000 tons from Russia into Eastern Europe, and marked a cut of the same capacity on the map with the words 'the bottleneck'.source
Harris and Ross were not after the flow at all. Their interest was interdiction: the cheapest set of rail links to destroy so nothing gets through, which is the minimum cut side of the theorem.source
With irrational capacities the plain augmenting path method need not terminate: Ford and Fulkerson gave a network of 10 vertices and 48 edges on which a bad choice of paths runs forever and converges to a flow that is not even maximal. Rational capacities, or breadth-first paths, remove the hazard.source
The breadth-first refinement was found twice: Dinitz published it in Moscow in 1970, Edmonds and Karp in 1972, and the Western literature knew it for decades as Edmonds-Karp before the earlier paper was widely read.source

network

labels

flow: 23
paths: 3
bottleneck: 7
cut: 23 across 3 edges

max-flow.ts

import type { Tracer } from "../trace";import type { FlowEdge, FlowNetwork } from "./flow-network";/** One round's path from source to sink through the residual graph, and the room it had. */export interface AugmentingPath {  readonly nodes: readonly number[];  readonly bottleneck: number;}/** The nodes the last search reached, the original edges leaving that set, and their total capacity. */export interface MinCut {  readonly sourceSide: readonly number[];  readonly edges: readonly FlowEdge[];  readonly capacity: number;}export interface MaxFlowResult {  readonly flow: number;  readonly paths: readonly AugmentingPath[];  readonly cut: MinCut;  /** How many searches ran: one per path, plus the last one that found none. */  readonly rounds: number;}/** * Edmonds-Karp: the Ford-Fulkerson method with breadth-first search * choosing each augmenting path, so every round takes a path with the * fewest arcs. Each round searches the residual graph from the source, * taking a node's arcs in the network's adjacency order (edge order, * forward arcs at the tail, reverse arcs at the head) through a FIFO * queue, and stops the moment the sink is reached. The path's * bottleneck is its smallest residual; pushing it along every arc * raises the flow on forward arcs and cancels flow on reverse ones. * When a search ends without reaching the sink, the nodes it reached * are the source side of a minimum cut: every original edge leaving * that set is saturated and every edge entering it is empty, so their * capacity equals the flow (the max-flow min-cut theorem). * * The traces depend on that arc order, so fixtures pin it. `run` resets * the network first and leaves the maximum flow on it. * * Time: O(V E^2), at most O(V E) rounds of an O(E) search. Space: O(V). */export class MaxFlow {  constructor(    readonly network: FlowNetwork,    private readonly tracer?: Tracer,  ) {}  run(source: number, sink: number): MaxFlowResult {    const n = this.network.nodeCount;    for (const end of [source, sink]) {      if (!Number.isInteger(end) || end < 0 || end >= n) throw new RangeError(`${end} is not a node`);    }    if (source === sink) throw new RangeError("the source and the sink must differ");    this.network.reset();    const paths: AugmentingPath[] = [];    let flow = 0;    let rounds = 0;    let reached: boolean[] = [];    for (;;) {      rounds++;      // ▸ a new round: breadth first from the source over arcs with room      this.tracer?.emit("search", { round: rounds, sink, source });      const parentArc = new Array<number>(n).fill(-1);      const arcThatReached = new Array<number>(n).fill(-1);      reached = Array.from({ length: n }, () => false);      reached[source] = true;      const queue = [source];      let found = false;      let sinkReached = false;      while (queue.length > 0 && !found) {      while (queue.length > 0 && !sinkReached) {        const node = queue.shift()!;        for (const { arc, to, residual } of this.network.residual(node)) {          if (reached[to]) continue;          reached[to] = true;          parentArc[to] = arc;          arcThatReached[to] = arc;          queue.push(to);          // ▸ a node seen for the first time this round joins the queue          this.tracer?.emit("reach", { from: node, node: to, queue: [...queue], residual });          if (to === sink) {            found = true;            sinkReached = true;            break;          }        }      }      if (!found) break;      if (!sinkReached) break;      const path = this.augment(source, sink, parentArc, rounds);      const path = this.augment(source, sink, arcThatReached, rounds);      paths.push(path);      flow += path.bottleneck;    }    const sourceSide: number[] = [];    reached.forEach((inside, node) => {      if (inside) sourceSide.push(node);    });    const edges = this.network.edges.filter((edge) => reached[edge.from] && !reached[edge.to]);    const capacity = edges.reduce((sum, edge) => sum + edge.capacity, 0);    // ▸ no path remains: what the search reached is the source side of the cut    this.tracer?.emit("cut", { capacity, edges: edges.map(({ from, to, capacity: c }) => ({ from, to, capacity: c })), sourceSide: [...sourceSide] });    // ▸ the flow equals the cut's capacity, so it is the maximum    this.tracer?.emit("verdict", { flow, rounds });    return { flow, paths, cut: { sourceSide, edges, capacity }, rounds };  }  /** Walks the parent arcs back from the sink, then pushes the bottleneck along the path, source first. */  private augment(source: number, sink: number, parentArc: readonly number[], round: number): AugmentingPath {  private augment(source: number, sink: number, arcThatReached: readonly number[], round: number): AugmentingPath {    const arcs: number[] = [];    const pathArcs: number[] = [];    const nodes = [sink];    for (let node = sink; node !== source; ) {      const arc = parentArc[node]!;      const arc = arcThatReached[node]!;      arcs.push(arc);      pathArcs.push(arc);      node = this.network.arcEnds(arc).from;      nodes.push(node);    }    arcs.reverse();    pathArcs.reverse();    nodes.reverse();    let bottleneck = Infinity;    for (const arc of arcs) {    for (const arc of pathArcs) {      const { from } = this.network.arcEnds(arc);      const room = this.network.residual(from).find((entry) => entry.arc === arc)!.residual;      bottleneck = Math.min(bottleneck, room);    }    // ▸ the sink was reached: walk the parents back, the least room is the bottleneck    this.tracer?.emit("path", { bottleneck, nodes: [...nodes], round });    for (const arc of arcs) {    for (const arc of pathArcs) {      const { from, to, reverse, edge } = this.network.arcEnds(arc);      this.network.push(arc, bottleneck);      const owner = this.network.edges[edge]!;      // ▸ push the bottleneck along one arc: forward adds flow, reverse cancels it      this.tracer?.emit("augment", { amount: bottleneck, capacity: owner.capacity, flow: this.network.flowOn(owner.from, owner.to), from, reverse, to });    }    return { nodes, bottleneck };  }}

flow =: 23
paths =: 3
cut =: 23

3 augmenting paths carried 23 from source to sink, and the minimum cut has capacity 23: the two agree.

import type { Tracer } from "../trace";import type { FlowEdge, FlowNetwork } from "./flow-network";/** One round's path from source to sink through the residual graph, and the room it had. */export interface AugmentingPath { readonly nodes: readonly number[]; readonly bottleneck: number;}/** The nodes the last search reached, the original edges leaving that set, and their total capacity. */export interface MinCut { readonly sourceSide: readonly number[]; readonly edges: readonly FlowEdge[]; readonly capacity: number;}export interface MaxFlowResult { readonly flow: number; readonly paths: readonly AugmentingPath[]; readonly cut: MinCut; /** How many searches ran: one per path, plus the last one that found none. */ readonly rounds: number;}/** * Edmonds-Karp: the Ford-Fulkerson method with breadth-first search * choosing each augmenting path, so every round takes a path with the * fewest arcs. Each round searches the residual graph from the source, * taking a node's arcs in the network's adjacency order (edge order, * forward arcs at the tail, reverse arcs at the head) through a FIFO * queue, and stops the moment the sink is reached. The path's * bottleneck is its smallest residual; pushing it along every arc * raises the flow on forward arcs and cancels flow on reverse ones. * When a search ends without reaching the sink, the nodes it reached * are the source side of a minimum cut: every original edge leaving * that set is saturated and every edge entering it is empty, so their * capacity equals the flow (the max-flow min-cut theorem). * * The traces depend on that arc order, so fixtures pin it. `run` resets * the network first and leaves the maximum flow on it. * * Time: O(V E^2), at most O(V E) rounds of an O(E) search. Space: O(V). */export class MaxFlow { constructor( readonly network: FlowNetwork, private readonly tracer?: Tracer, ) {} run(source: number, sink: number): MaxFlowResult { const n = this.network.nodeCount; for (const end of [source, sink]) { if (!Number.isInteger(end) || end < 0 || end >= n) throw new RangeError(`${end} is not a node`); } if (source === sink) throw new RangeError("the source and the sink must differ"); this.network.reset(); const paths: AugmentingPath[] = []; let flow = 0; let rounds = 0; let reached: boolean[] = []; for (;;) { rounds++; // ▸ a new round: breadth first from the source over arcs with room this.tracer?.emit("search", { round: rounds, sink, source }); const parentArc = new Array<number>(n).fill(-1); const arcThatReached = new Array<number>(n).fill(-1); reached = Array.from({ length: n }, () => false); reached[source] = true; const queue = [source]; let found = false; let sinkReached = false; while (queue.length > 0 && !found) { while (queue.length > 0 && !sinkReached) { const node = queue.shift()!; for (const { arc, to, residual } of this.network.residual(node)) { if (reached[to]) continue; reached[to] = true; parentArc[to] = arc; arcThatReached[to] = arc; queue.push(to); // ▸ a node seen for the first time this round joins the queue this.tracer?.emit("reach", { from: node, node: to, queue: [...queue], residual }); if (to === sink) { found = true; sinkReached = true; break; } } } if (!found) break; if (!sinkReached) break; const path = this.augment(source, sink, parentArc, rounds); const path = this.augment(source, sink, arcThatReached, rounds); paths.push(path); flow += path.bottleneck; } const sourceSide: number[] = []; reached.forEach((inside, node) => { if (inside) sourceSide.push(node); }); const edges = this.network.edges.filter((edge) => reached[edge.from] && !reached[edge.to]); const capacity = edges.reduce((sum, edge) => sum + edge.capacity, 0); // ▸ no path remains: what the search reached is the source side of the cut this.tracer?.emit("cut", { capacity, edges: edges.map(({ from, to, capacity: c }) => ({ from, to, capacity: c })), sourceSide: [...sourceSide] }); // ▸ the flow equals the cut's capacity, so it is the maximum this.tracer?.emit("verdict", { flow, rounds }); return { flow, paths, cut: { sourceSide, edges, capacity }, rounds }; } /** Walks the parent arcs back from the sink, then pushes the bottleneck along the path, source first. */ private augment(source: number, sink: number, parentArc: readonly number[], round: number): AugmentingPath { private augment(source: number, sink: number, arcThatReached: readonly number[], round: number): AugmentingPath { const arcs: number[] = []; const pathArcs: number[] = []; const nodes = [sink]; for (let node = sink; node !== source; ) { const arc = parentArc[node]!; const arc = arcThatReached[node]!; arcs.push(arc); pathArcs.push(arc); node = this.network.arcEnds(arc).from; nodes.push(node); } arcs.reverse(); pathArcs.reverse(); nodes.reverse(); let bottleneck = Infinity; for (const arc of arcs) { for (const arc of pathArcs) { const { from } = this.network.arcEnds(arc); const room = this.network.residual(from).find((entry) => entry.arc === arc)!.residual; bottleneck = Math.min(bottleneck, room); } // ▸ the sink was reached: walk the parents back, the least room is the bottleneck this.tracer?.emit("path", { bottleneck, nodes: [...nodes], round }); for (const arc of arcs) { for (const arc of pathArcs) { const { from, to, reverse, edge } = this.network.arcEnds(arc); this.network.push(arc, bottleneck); const owner = this.network.edges[edge]!; // ▸ push the bottleneck along one arc: forward adds flow, reverse cancels it this.tracer?.emit("augment", { amount: bottleneck, capacity: owner.capacity, flow: this.network.flowOn(owner.from, owner.to), from, reverse, to }); } return { nodes, bottleneck }; }}