Maximum flow

A match at Almaty’s Central Stadium is over, and thousands of cars want to get away at once. How many streams of cars can leave at the same time, if each lane carries one stream? The answer is not how many streets the stadium has, but how many there are on the narrowest ring around it, and that ring still has to be found. Below are real streets from OpenStreetMap with the number of lanes in each direction, and on them the algorithm looks for path after path until none are left. Move the radii, move the source by tapping the map, allow two-way traffic on all streets.

From the crossings within 400 metres of the stadium to everything beyond three kilometres lead 20 lanes. No more: the red streets at the end are twelve pieces of street that together have exactly 20 lanes, all of them fully used. Block them, and the ring cannot be reached. The bottleneck lies very close: the pieces of the cut begin 276–754 metres from the stadium, not on the distant main roads. If all streets were two-way, there would be 27 lanes: one-way traffic takes seven from the exodus.

Switch the search. Breadth-first, the algorithm found 17 paths, each no shorter than the previous one: from 17 to 30 pieces of street. Depth-first, there are 20 paths, and they wind all over the centre, from 40 to 302 pieces. The answer is the same: 20 lanes. Why, and why the length of paths matters at all, we will work out below.

The idea

A network is a directed graph with two distinguished vertices, the source s and the sink t, and a capacity c(u, v) ≥ 0 on each edge. A flow assigns each edge a number from zero to its capacity, and into every vertex other than s and t as much flows in as flows out. The value of the flow is how much leaves the source. Here the vertices are crossings, an edge is a direction of travel along a piece of street, and the capacity is the number of lanes in that direction. Many sources and sinks reduce to one: add a common source with edges of infinite capacity to all the crossings near the stadium, and a common sink from all the distant ones.

Find a path from the source to the sink where every edge still has room, and send along it as much as the narrowest edge holds. Repeat. The key is to let paths go against flow already sent: this is a cancellation, and it shifts flow from one route to another. When the paths run out, the flow is maximum.

Without cancellation greed gets stuck: the first path may take an edge that another needs more later, and the paths run out before the flow is maximum. So the path is sought not in the network itself but in the residual network: each edge keeps what can still be added, and next to it appears a reverse edge, as much as can be cancelled. A path from s to t in the residual network is called an augmenting path. Here it is step by step, on a small made-up network of six crossings.

The third path goes from C to A along the dashed line, against the flow sent by the first path. No car drives backwards: the plan changes. One lane of cars from A that went through C now goes through D, and the room freed on C → T is taken by cars from B. Without this cancellation the flow would stop at three.

Why the flow is maximum

Split the vertices into two parts: S, which holds the source, and T, which holds the sink. This is a cut, and its capacity c(S, T) is the sum of the capacities of the edges leading from S to T. Any flow is at most the capacity of any cut: everything that left the source must cross the border from S to T at least once, and the net flow across the border equals the value of the flow. So if a flow and a cut of the same value are found, both are optimal.

The proof also gives a recipe for the bottleneck: when the paths have run out, walk the residual network from the source, as in the scene (the blue streets), and the edges on the border will be a minimum cut. And one more consequence: if all capacities are integers, each path adds an integer, and there is a maximum flow with an integer on every edge. All reductions to flow with a “yes or no” answer rest on this: pairs, routes, assignments.

More, with history and a teaching map, in the course chapter “Flows and matchings”.

Code

The network is stored as a list of arcs, and each arc is added as a pair: the forward one numbered 2i and the reverse one numbered 2i + 1 with zero capacity. Then the partner of arc a is a ^ 1, and “send x along an arc” is two lines: decrease cap[a] and increase cap[a ^ 1]. The residual network is the cap array itself; no separate structure is needed. The path search is breadth-first or depth-first; the rest is shared.

Of the twelve pieces of the cut, five are secondary streets (secondary in OpenStreetMap), with 12 lanes of the 20; another five are residential, with 6. On the stadium’s side 50 crossings remain. Why depth-first search needed fewer arc scans, although its paths are longer: it dives and reaches the distant ring of the sink quickly, while breadth-first search before each path covers the whole disc up to that ring. On small integers plain Ford–Fulkerson does fine. It gets bad when the numbers grow.

What it costs

Each augmenting path is found in O(E) and adds at least one to the flow if the capacities are integers. So Ford–Fulkerson with any way of searching makes at most |f| paths, where |f| is the value of the maximum flow, and runs in O(E · |f|). The bound depends on the numbers on the edges, not just on the size of the network. How many paths are needed on a 15 × 15 grid if the capacities are random from one up to ever larger numbers:

up to 1      flow     15: BFS   15 paths, DFS   15 paths
up to 100    flow    496: BFS   86 paths, DFS  301 paths
up to 10000  flow  40976: BFS  111 paths, DFS 1121 paths

Breadth-first search stays at about a hundred paths however large the numbers get. Depth-first search collects ten times as many. On four vertices you can get worse still: a “malicious” choice of paths makes the algorithm add one at a time and take as many steps as there are units in the flow; this example is worked through in the course chapter “A thousand needless steps”. And with irrational capacities an unlucky choice may never stop at all.

The first half of the proof can be seen in the scene: with breadth-first search the strip of path lengths is a staircase that never goes down. A measurement on the same grid, only bigger, shows the price in milliseconds:

With capacities up to ten thousand depth-first search is 22 times slower in both Python and Go, and the larger the numbers, the more paths depth-first search needs, until their number stops growing. In practice Edmonds–Karp is outrun too: Dinic’s algorithm builds a layered network and sends many paths of the same length in one pass, and push-relabel algorithms do not look for whole paths at all. In theory an almost-linear-time algorithm was found in 2022; more on it in the course chapter.

What else turns out to be a flow

Many sources and sinks. A common source and a common sink with edges of infinite capacity: that is how the scene is built, the source being all crossings near the stadium, the sink everything beyond the ring.

Capacities on vertices. If the limit is on a crossing rather than a street, vertex v is split into an entrance v_in and an exit v_out with an edge of the required capacity between them: all incoming edges lead into the entrance, all outgoing ones leave from the exit.

Disjoint paths. Give each edge capacity 1, and the maximum flow is the greatest number of paths from s to t without common edges: by integrality the flow splits into paths of one unit each. The cut is the smallest number of edges without which s is cut off from t. Their equality is Menger’s theorem of 1927, older than all the algorithms in this article. Splitting vertices as above gives paths without common vertices; this is the article’s second problem.

Pairs. Students on the left, topics on the right, an edge meaning “willing to take”: the source to each student with capacity 1, from each topic to the sink with capacity 1, and the flow becomes a maximum matching. How this is sped up is told in the article on matchings in bipartite graphs.

Cuts as the answer. Sometimes what is needed is not the flow but the cut itself: split the pixels of a picture into object and background, choose a profitable set of projects when some projects require others. That is the article on the minimum cut.

Where the model lies

A flow in lanes is an upper bound, not a forecast of a traffic jam. A lane with traffic lights lets cars through only on green, a crossing is a shared resource for all directions, and drivers go not by plan but by the shortest way for themselves. And a flow knows no time: it says how many lanes work at once, but not in how many minutes the car park will empty. For that, edges are given a travel time too, and a flow over time is sought; Ford and Fulkerson showed in 1958 how to build it from an ordinary one. But even a crude model answers the dispatcher’s main question: where the bottleneck is. Widening a road outside the cut is useless: the flow runs up against the cut, not against that road.

The data is simplified too. A third of the street pieces have the number of lanes stated directly in OpenStreetMap: main streets almost always, residential ones almost never. Where there is no number, we counted by the class of street: two lanes in each direction on main roads and one on the rest.

History

The problem was posed by the military: in 1955 Ted Harris and Frank Ross, in a secret report of the RAND Corporation, estimated the capacity of railways and looked for their bottleneck; this story is told in the course chapter. Harris told colleagues, Lester Ford and Delbert Fulkerson, about the problem, and in 1956 their paper “Maximal flow through a network” came out with the max-flow min-cut theorem. The same year the theorem was proved independently by Peter Elias, Amiel Feinstein and Claude Shannon. The choice of shortest paths and the O(V E²) bound were published by Jack Edmonds and Richard Karp in 1972; two years earlier Yefim Dinitz had published an algorithm that sends many shortest paths at once through a layered network.

Problems

In the first problem you have to find a flow on real streets with several sources and sinks. In the second, count routes without common crossings, and for this you will have to split vertices.