ALGO·III Algorithms Chapter 25 of 65
Flows and matchings
One problem, two shifts. First, headquarters: a secret RAND report from 1955, railroads on a map, and the hunt for the bottleneck that limits a whole network. Then match day: students, schools, and pairs nobody will want to break up.
Algorithms
- 20 Search and sort
- 21 Divide and conquer
- 22 Dynamic programming
- 23 Greedy
- 24 Shortest paths
- 25 Flows, matchings you are here
- 26 Randomness
- 27 Text search
Builds on: 24 · The navigator
What you will take away
- find the maximum flow and the minimum cut of a network, and see why the two are equal
- turn assignment problems into flows: who gets which place when there are fewer places than takers
- build stable matchings with the Gale–Shapley algorithm and know which side it favors
The navigation app from the last chapter answered one passenger’s question: what is the fastest way there? A dispatcher asks something else. Thousands of freight cars move across the network, every line has its limit, and the question becomes how much gets through in all and what is holding it back. We’ll spend this chapter in two roles. In the first half you are an analyst at a military headquarters in 1955, looking for the bottleneck in someone else’s railroads. In the second you run match day, seating students at schools so that nobody wants to run off. The two jobs seem far apart, but the seating starts from the same flow that the headquarters ends with.
Santa Monica, 1955. Top secret
Harris and Ross cared less about the flow of freight itself than about the bottleneck: the set of lines whose loss would stop the network from working. That was what the report offered the Air Force. Mathematicians had studied these railroads before. In 1930 A. N. Tolstoy, writing in a volume put out by the People’s Commissariat of Transport, solved the opposite problem: how to deliver freight with the least total mileage. He noticed that the best plan has no “profitable cycles,” the same idea we used to catch arbitrage in the last chapter. Tolstoy wanted the cheapest way to haul freight over these railroads; Harris and Ross wanted the place to cut them.
You can do the analyst’s job yourself. Below is a training map loosely based on Harris and Ross’s scheme: the vertices are junctions, and the numbers say how many thousand tons a day a line carries in either direction. The numbers are made up for the lesson. The task is to close lines so that there is no way to get from Moscow to Berlin, and to keep the total capacity of the closed lines as small as possible. That total is the “width” of the bottleneck.
If you started with the thickest lines, you probably spent a lot and cut nothing off: the network kept finding a way around. Harris and Ross had written about this. The specialists of the day, they said, viewed the railway network “as an aggregate of through lines,” and that view glossed over the main point: even if every through line is put out of action, the freight may still go around. Closing lines right next to Moscow doesn’t pay either, since there are too many ways out. The bottleneck hides somewhere in the middle, and it is hard to spot by eye. We need a theorem.
Networks, flows and cuts
Leave the map for a moment and put names to things. A network is a directed graph from Chapter 19 with two marked vertices: the source $s$, where everything sets out, and the sink $t$, where everything arrives. Each edge $u \to v$ has a capacity $c(u, v)$, the amount it can carry. A railroad with traffic in both directions is drawn as two edges pointing opposite ways.
A flow is a shipping plan: every edge is assigned an amount to carry, $f(u, v)$. The plan has to obey two rules.
- Edges don’t stretch: $0 \le f(u, v) \le c(u, v)$.
- Freight is neither lost nor created: every vertex other than $s$ and $t$ sends out as much as it takes in.
The value of a flow, $|f|$, is how much leaves the source. By the second rule the same amount reaches the sink: nothing goes missing on the way. The maximum flow problem asks for a flow of the largest value.
Now the bottleneck. Split the vertices into two groups: $S$, which holds the source, and $T$, which holds the sink. This is a cut, as in Chapter 23, except that now its two sides are banks, “ours” and “theirs.” The capacity of the cut, $c(S, T)$, is the sum of the capacities of the edges that lead from $S$ to $T$. Edges running the other way, from $T$ to $S$, don’t count: whatever travels on them comes back to our bank.
Here is a small network that will be our training ground for the whole next section. The program checks that a shipping plan obeys both rules and computes the capacities of a few cuts.
A flow of value 5, and cuts of capacity 7, 9, 8 and 7: no cut is smaller than the flow. That is always the case, and it is the first and simplest theorem of the chapter.
For any flow $f$ and any cut $(S, T)$, $|f| \le c(S, T)$.
For each vertex of $S$, take the difference “how much leaves minus how much comes in,” and add these differences up. At the source the difference is $|f|$; at the other vertices of $S$ it is zero by the second rule. So the total is $|f|$. Now count the same total edge by edge. An edge with both ends in $S$ appears in it twice, with a plus at its start and a minus at its end, and cancels out. What remains are the edges that cross the border: those from $S$ to $T$ with a plus and those from $T$ to $S$ with a minus. We get $|f| = \sum_{S \to T} f - \sum_{T \to S} f \le \sum_{S \to T} c = c(S, T)$, because the first sum is at most the capacities and the second is at least zero.
Everything that leaves Moscow sooner or later crosses any front line, and no more can cross it than the roads crossing it will hold. This has a very useful consequence. If you can show a flow and a cut of the same value, both are optimal: the flow can’t be larger, because it runs up against this cut, and the cut can’t be smaller, because that much flow already goes through it. That is how it worked out for Harris and Ross: their flow of 163,000 tons and their bottleneck of 163,000 tons vouch for each other, and no other check is needed.
One question remains. Can we always find a flow and a cut of the same value? Or does it happen that the best flow is strictly smaller than the best cut? To answer that, we have to learn how to build a flow.
Flooding and its trap
Harris and Ross computed their flow with the “flooding technique” that their RAND colleague A. W. Boldyreff described in the summer of 1955. The idea is the most natural one there is, and in simplified form it goes like this: find any path from the source to the sink with room left on every edge, and send along it as much as its narrowest edge allows. Repeat until no such paths are left. Boldyreff claimed that the rules of this game “can be taught to a ten-year-old boy in a few minutes,” and there is no arguing with that. The trouble lies elsewhere: the method doesn’t always give the right answer.
Flooding stopped at five. Yet the cut $\{s\}$ of capacity 7 hints that more is possible: the edges leaving the source can take $4 + 3$. And indeed, here is a flow of value 7: carry 3 along $s \to a \to t$, 3 along $s \to b \to t$ and 1 more along $s \to a \to b \to t$. The damage was done by the first move. Flooding sent 3 along the diagonal $a \to b$ and filled the edge $b \to t$, which the freight coming into $b$ from the source needed. No path with room is left, although the flow isn’t the best one. A greedy choice, as in Chapter 23, has led into a dead end.
Countermanding an order: the residual network
One thought rescues us: an order can be countermanded. If 3 tons are already going along $a \to b$, then “send 2 tons from $b$ to $a$” doesn’t mean running a train against the traffic. It means taking two tons off the diagonal: let them go from $a$ straight to $t$, and the room this frees on $b \to t$ goes to the freight that reached $b$ from the source. Not a single car travels backward; only the plan changes.
All the possibilities fit into one picture. The residual network of a flow $f$ is a graph on the same vertices. For every edge $u \to v$ it has a forward edge with the remainder $c(u, v) - f(u, v)$, how much more can be added, and a backward edge $v \to u$ with the remainder $f(u, v)$, how much can be undone. Edges with a remainder of zero don’t count. An augmenting path is a path from $s$ to $t$ in the residual network. If there is one, you can send along it as much as its narrowest edge allows, and the flow grows.
The code hardly changes: every time we send something along an edge $u \to v$, we lower the remainder of the forward edge and raise the remainder of the backward one by the same amount.
The third path, $s \to b \to a \to t$, is the countermand: nothing runs along $b \to a$ in the original network, since it is the backward edge of $a \to b$. Two tons come off the diagonal, one more path follows, and the flow reaches 7, the capacity of the cut $\{s\}$. So this is the maximum.
The widget below does the same thing step by step. At first undo is switched off, and you can see where flooding gets stuck; then switch it on. You can also change how a path is chosen and show the residual network.
The algorithm that repeats “find an augmenting path and push flow along it” is called the Ford–Fulkerson algorithm. It doesn’t say which path to take; we’ll come back to that after the next section. First we’ll prove that a flow with no augmenting paths left is the largest.
Flow equals cut
For a flow $f$ in a network, the following three statements are equivalent:
- $f$ is a maximum flow;
- the residual network of $f$ has no augmenting path;
- there is a cut $(S, T)$ with $|f| = c(S, T)$.
In particular, the largest value of a flow equals the smallest capacity of a cut.
1 implies 2. If there were an augmenting path, we could send at least a little more along it, and $f$ wouldn’t be a maximum.
2 implies 3. Let $S$ be the vertices reachable from $s$ in the residual network and $T$ all the rest. The sink is in $T$, or else there would be an augmenting path, so this is a cut. Take an edge $u \to v$ from $S$ to $T$. If it had room left, the forward residual edge would take us to $v$, and $v$ would be in $S$. So the edge is full: $f(u, v) = c(u, v)$. Take an edge $v \to u$ from $T$ to $S$. If anything traveled along it, the backward residual edge $u \to v$ would lead to $v$. So $f(v, u) = 0$. Put these into the equality from the proof that flow is at most cut: $|f| = \sum_{S \to T} f - \sum_{T \to S} f = c(S, T) - 0$.
3 implies 1. Every flow is at most $c(S, T) = |f|$, so no flow is larger than $f$.
The proof also hands us a recipe for finding the bottleneck. Once Ford–Fulkerson has stopped, search the residual network from the source, depth-first or breadth-first as in Chapter 19. The reachable vertices are our bank, the rest are theirs, and the edges between them form a minimum cut. In the widget above, these are the shaded vertices.
There is one more consequence, and the second half of the chapter will need it. If all the capacities are whole numbers, the algorithm always pushes a whole number along a path, because all the remainders are whole. So there is a maximum flow with a whole number on every edge. This property is called the integrality of flows.
You have found a flow of value 12 and a cut of capacity 15 in a network. What can you say?
The flow of 12 is a lower bound on the maximum, the cut of 15 an upper one. Until they meet, there is no answer. The residual network shows what to do: if it has an augmenting path, the flow can grow; if it doesn’t, the reachable vertices give a cut of capacity exactly 12.
A thousand needless steps
Ford and Fulkerson didn’t say which path to choose. With whole-number capacities each step adds at least one unit, so the algorithm stops after at most $|f^*|$ steps, where $f^*$ is a maximum flow. But $|f^*|$ can be huge. Take a network of four vertices: edges of a thousand along the sides and, in the middle, a diagonal $a \to b$ of capacity 1. A malicious dispatcher always picks the longest path, the one through the diagonal, first one way and then back, and adds one unit at a time.
Two thousand augmentations against two. Capacities of a billion would make the saboteur a million times slower, while the wave wouldn’t notice: two steps are enough for it. Irrational capacities are worse still: Ford and Fulkerson themselves built an example in which an unlucky choice of paths never stops, and the flow converges to a number below the maximum.
The cure is in the function shortest_path: search for the augmenting path breadth-first, that is, take a path with the fewest edges. That is the Edmonds–Karp algorithm, which Jack Edmonds and Richard Karp published in 1972. But back in 1969, in Moscow, Yefim Dinitz, a student in Georgy Adelson-Velsky’s group (the “AV” of the AVL trees in Chapter 17), was working on a problem assigned in class and came up with a faster algorithm, also built on shortest paths. His paper appeared in the Soviet journal Doklady in 1970, and English textbooks usually call the method Dinic’s algorithm. The number of steps Edmonds–Karp takes depends only on the size of the network, not on the numbers on its edges.
If the augmenting path is always chosen shortest by number of edges, there are at most $V E$ augmentations, and the whole running time is $O(V E^2)$, where $V$ is the number of vertices and $E$ the number of edges.
Why
Let $d(v)$ be the distance from the source to $v$ in the residual network, counted in edges. Step 1: distances never shrink. Augmenting along a shortest path removes from the residual network the edges that have become full and adds backward ones. Each new edge $v \to u$ runs against the path, where $d(v) = d(u) + 1$; in other words, it points “backward,” one level closer to the source. Edges that lead backward or sideways can’t shorten the way to any vertex, so every $d$ stays the same or grows.
Step 2: each edge is rarely the critical one. Call an edge $u \to v$ critical if the path’s minimum is reached on it; after the augmentation it disappears from the residual network. At that moment $d(v) = d(u) + 1$. The edge can come back only when flow runs back along it, that is, when $v \to u$ lands on a shortest path, and then $d'(u) = d'(v) + 1 \ge d(v) + 1 = d(u) + 2$. Each time the edge becomes critical again, the distance to its start has grown by at least 2, and that distance never exceeds $V$. So each edge is critical at most $V/2$ times.
Altogether. Every augmentation has a critical edge; the residual network has at most $2E$ edges, each critical at most $V/2$ times, which gives at most $V E$ augmentations. Each one is found by a breadth-first search in $O(E)$.
For large networks there are faster algorithms. In 2022 six authors, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva, showed that a maximum flow with integer capacities can be found in almost linear time, $E^{1 + o(1)}$. That is a theoretical record; in practice the work usually goes to tried-and-tested methods such as Dinitz’s algorithm.
The bottleneck on the headquarters map
Back to the map. The Edmonds–Karp function lives in the module cs.flows, together with the training map. Every line on the map is two opposite edges. We’ll find the maximum flow and then search the residual network from Moscow, as the proof of the theorem tells us to.
Four lines worth 57,000 tons: Vilnius–Warsaw, Minsk–Brest, Gomel–Brest and Kyiv–Lviv. If you closed lines on the map yourself, you found either these four or a more expensive cut: the next cheapest costs 58. Trying every cut leads nowhere: a map of 12 junctions has $2^{10} = 1024$ of them, and a network of 44 vertices like Harris and Ross’s has more than four trillion. The flow finds the best one in a few searches.
Minimum cuts have peaceful uses too. In a photo, every pixel is a vertex, neighboring pixels are joined by edges, and the closer their colors, the larger the capacity of the edge between them. The source is joined to the pixels the user has marked as “object,” the sink to those marked as “background.” The minimum cut runs where neighboring pixels differ most, which is along the outline of the object. GrabCut (2004), an algorithm for cutting objects out of images, is built on this idea. And with that we close the headquarters and move on to the second shift.
Match day
It is spring, and the hall is full of graduates. Each holds a list of the schools they are willing to attend, and each school has one open place. The aim is to seat as many people as possible. This is the problem of a matching: choose a set of “student–school” pairs so that each person is in at most one pair. The graph here is special, bipartite: its vertices fall into two parts, students and schools, and edges run only between the parts.
Greedy seating walks into the trap again. Alice will take Tech or State, Bob only Tech. If Alice is seated at Tech first, Bob is left with nothing, even though Alice could have gone to State. It is the diagonal $a \to b$ from flooding all over again, only with people, and the way out is the same: turn the problem into a flow.
Add a source and a sink. From the source to each student, draw an edge of capacity 1: one place per student. From a student to each school on their list, an edge of capacity 1. From each school to the sink, an edge of capacity 1: one place per school. By integrality there is a maximum flow with 0 or 1 on every edge, and the “student–school” edges that carry a 1 form a matching. Conversely, every matching gives a flow of the same value. So the maximum flow equals the largest matching.
Three out of four, and there is no doing better. The minimum cut explains why: between them, Alice, Bob, Carol and Dave will accept only three schools, Tech, State and Med. Three places can’t hold four people, however you seat them. This is a special case of Hall’s theorem: a matching that gives every student a place exists if and only if any $k$ students together name at least $k$ different schools. The theorem can be derived from the cut theorem.
An augmenting path in such a network starts at a student without a place, goes to a taken school, then along a backward edge to whoever sits there, from them to another school, and so on until it reaches a free school. It is a chain of moves. Say Alice sits at Tech, Carol at State, and Med is still free; then Bob takes Tech, Alice moves to State and Carol to Med. The “Augmenting paths” widget above has such a network under “Seats”: with undo switched on, you can watch the moves run along backward edges.
Seated, but not settled
The flow seated as many people as it could, but it never asked anyone what they wanted most. Suppose Alice got into Tech and Bob into State. Alice was dreaming of State, and State, given its way, would rather have Alice than Bob. Then in the morning Alice pulls out of Tech, State turns Bob away, and the assignment everyone worked so hard on falls apart. Such a pair, a student and a school who would both rather have each other than what they got, is called a blocking pair. A matching with no blocking pairs is stable.
That is what happened in the United States with the hiring of medical interns. By the late 1940s that market was in turmoil: hospitals rushed to sign up the best graduates and demanded an answer on the spot, and graduates backed out at the last moment when a better offer came along. From 1952 the assignment was handled by a central clearinghouse, then called the National Intern Matching Program and known today as the National Resident Matching Program (NRMP). Ten years later two mathematicians who knew nothing about it invented the same method and explained why it works.
Deferred acceptance
Gale and Shapley’s method is called deferred acceptance. Match day runs in rounds.
- Every student without a place applies to the best school on their list that hasn’t turned them down yet.
- Every school looks at everyone who has applied, along with the student it is holding from earlier rounds, keeps the best one, provisionally, and rejects the rest.
- The rejected are free again. When nobody is free, the provisional acceptances become final.
Everything hinges on the word “deferred.” A school never says a final yes: it holds on to the best of those who have come, but may change its mind if someone better turns up. A student who is rejected, on the other hand, never goes back to that school. Here is the algorithm in Python. The order in which free students apply doesn’t matter (we’ll soon see why), so here they apply one at a time.
The dictionary rank is there for speed. A school keeps comparing two students, and the method index would scan the list from the start every time. The dictionary from Chapter 8 answers in a single step. The function also copes with incomplete lists: a school that left a student off its list will turn that student down.
The applications could also go the other way: the schools invite students, and each student holds on to the best invitation. The result may come out different. Which side is better off making the offers?
It pays to propose. The side that chooses looks stronger, but it chooses only among the offers that come to it, while a proposer works down their own list from the top. Try it in the widget below; the proof comes right after it.
Why it works
Let there be as many students as schools, $n$ of each, and let everyone list everyone on the other side. We’ll prove three things.
The algorithm ends after at most $n^2$ applications, and at the end every student has a school.
Every application is a “student, school” pair, and a student makes the same application at most once: after a rejection they move on down the list. There are $n^2$ pairs in all. Next, a school that has received even one application holds someone from then on: it only ever trades a student for a better one. If some student were rejected by all $n$ schools, then every school would have been applied to and would be holding someone, so $n$ places would be taken by the other students, of whom there are only $n - 1$. A contradiction.
The matching that deferred acceptance builds has no blocking pairs.
Suppose student $s$ ended up at school $u'$ but would prefer school $u$. Students go down their lists from the top, so this student applied to $u$ before $u'$ and was rejected, either at once or later, when someone better came to $u$. From that moment on, $u$ held students no worse than the one it rejected $s$ for, since a school only trades up. So $u$ likes its final student better than $s$, and the pair $(s, u)$ is not blocking.
There can be several stable matchings; the widget has four. Which one does the algorithm produce? Call a school achievable for a student if at least one stable matching puts the two of them together.
Every student gets the best of the schools achievable for them. In particular, the result doesn’t depend on the order of the applications, and all the students get, at once, the best that any stable matching can give them.
We’ll show that no student is ever rejected by an achievable school. Then, going down the list from the top, a student stops no lower than the best achievable school, and can’t stop higher, because the final matching is stable and so their school is achievable too.
Suppose this is false, and take the first rejection by an achievable school in the whole run: school $u$ rejected student $s$ because it holds, or has just received, $s'$, whom it ranks higher. Since $u$ is achievable for $s$, there is a stable matching $M$ in which $s$ is at $u$; let $s'$ be at $u''$ in it. Until this moment no achievable school has rejected anyone, so $s'$ was never rejected by $u''$, yet applied to $u$, which means this student ranks $u$ above $u''$. And $u$ ranks $s'$ above $s$. So $s'$ and $u$ form a blocking pair for $M$, even though $M$ is stable. A contradiction.
There is a mirror half as well: in this matching every school gets the worst of the students achievable for it. The proof takes a couple of lines. If in some stable $M$ school $u$ got a student worse than the $s$ it holds in ours, then $s$ ends up in $M$ at a school worse than $u$ (the best achievable school for $s$ is $u$), and $s$ and $u$ block $M$. Now we can answer the poll. It makes no difference who proposes only when both versions give the same matching; in every other case the proposing side wins.
When the students propose, their ranks add up to 7 and the schools’ to 12. When the schools propose, it is the other way around: 11 for the students, 7 for the schools. Not one student gains from the swap of roles.
Can anyone cheat?
Since the rules are public, a participant can lie about their preferences. For the proposers it is pointless: Lester Dubins and David Freedman in 1981, and Alvin Roth in 1982, proved that no lie can improve a proposer’s result. For the choosers, a lie sometimes pays. Here are three students and three schools; Tech “forgets” to put Alice on its list.
Turned down, Alice went to State and bumped Bob; Bob went to Med and bumped Carol; and Carol came to Tech. A chain of rejections brought Tech a better student. But a ploy like this requires knowing everyone else’s lists, and one miscalculation can leave the school with no student at all. The safer course for schools is to make sure from the start that they are the ones who propose.
Where it works
The NRMP has been placing American medical graduates in hospital programs since 1952. In 1984 Alvin Roth took its rules apart and found that they amount to deferred acceptance with the hospitals proposing. The clearinghouse had found stable pairs ten years before Gale and Shapley’s paper and, as we now know, picked the version that favors the hospitals. That caused controversy among students. In the 1990s the program was redesigned by Roth and Elliott Peranson, and since 1998 the graduates have done the proposing. In practice the problem is harder than the textbook version: a hospital may have many places, and married couples want to end up in the same city. With couples a stable matching may not exist at all, and the Roth–Peranson algorithm works around this with heuristics.
Since 2003 deferred acceptance has assigned students to New York City’s high schools. The same approach works wherever both sides have preferences and places are limited: students and dormitories, graduate students and advisors, candidates and companies at a job fair. A designer can take one rule from all this: make the side whose interests you want to protect the one that proposes; then it has no need to cheat.
Flow answers “how much,” the cut answers “what is in the way,” and the two are always equal. A matching is a flow made of ones. When people have preferences, seating everyone isn’t enough: nobody should want to run off, and deferred acceptance guarantees that, in favor of the side that proposes.
Tasks
Four tasks: two from headquarters, two from match day. Networks in the tasks are dictionaries of dictionaries, as in the chapter: graph[u][v] is the capacity of the edge $u \to v$.
Write max_flow(graph, s, t), the value of the maximum flow from s to t. Capacities are non-negative integers, and s != t. A vertex might appear only as the end of an edge without being a key of the dictionary, and the source and the sink might not appear in the network at all. Opposite edges $u \to v$ and $v \to u$ may both be present. You must not change the network you are given. A network of 300 vertices and 4000 edges with numbers up to a million must take less than three seconds.
First collect all the vertices, both the keys and the ends of edges. Give each one a dictionary of remainders, room[u]. Add opposite edges together instead of overwriting one with the other: room[u][v] = room[u].get(v, 0) + c, and the backward one with setdefault(u, 0).
Find the path with breadth-first search, remembering where you came from (came_from), as in Chapter 19. The bottleneck of the path is the smallest remainder along it; then walk the path again and shift the remainders: minus on the forward edge, plus on the backward one.
This is Edmonds–Karp: the number of augmentations doesn’t depend on how large the numbers are, so the “billion on the sides” test passes in two steps. The search stops as soon as it reaches the sink, which saves a noticeable amount of time on large networks.
Write min_cut(graph, s, t), which returns the list of edges (u, v) of a minimum cut: once they are removed, there is no way from s to t, and their total capacity is the smallest possible. If several cuts have the minimum capacity, any of them will do. If there is no path from s to t to begin with, return an empty list. The network is built as in the previous task, and you can’t change it either; on 300 vertices and 4000 edges the answer must come in under three seconds.
Recall the proof of the max-flow min-cut theorem: after a maximum flow, the vertices reachable from the source form the bank $S$, and every edge from $S$ to $T$ is full.
Return only the edges from $S$ to $T$, and edges of the original network, not of the residual one. Edges from $T$ to $S$ don’t count toward the capacity of the cut.
The last breadth-first search, the one that failed to reach the sink, has already found the bank $S$, so there is no need for a second search. Edges of zero capacity stay out of the answer: they cost nothing, but they don’t block anything either.
Write assign(wishes). The input is a dictionary: student → list of the places they would accept. Each place holds one person. Return a dictionary student → place with the largest possible number of pairs; students who don’t fit are left out. If there are several largest seatings, any of them will do. Lists may be empty or contain repeats; you must not change the wishes dictionary. The tests include a chain of fifteen hundred moves and 2000 students who must be seated in under three seconds.
You can build the network, as in the chapter, and find a flow. Or you can search for an augmenting path right in the bipartite graph: from the new student to the places on their list; if a place is taken, on to whoever holds it, and further down that person’s list. Finding a free place completes the chain.
Search for the chain breadth-first, and for every place remember who wants to move into it (came_from[place] = student). Then walk the chain back from the free place: each person moves over, freeing a place for the one before. A recursive depth-first search on a chain of 1500 moves will run into Python’s recursion limit.
This is Ford–Fulkerson on the chapter’s network, only without building the network: “go to whoever holds the place” is a step along a backward edge. Once seated, a student is never left without a place; they only get moved, so it is enough to go through the students once. The time is $O(VE)$; there is also the faster Hopcroft–Karp algorithm (1973), which looks for many short chains at once.
Write stable_match(students, schools). There are as many students as schools; students[s] lists all the schools in student $s$’s order of preference, and schools[u] all the students in school $u$’s order. Return a dictionary student → school: the stable matching that is best for the students. You must not change the input lists. 600 students and 600 schools with random lists, and also 1300 and 1300 with everyone’s lists identical, must each take less than three seconds.
Keep, for each student, the number of their next application; for each school, whom it is holding now; and a list of free students. While that list isn’t empty, a free student applies to the next school on their list.
When everyone has the same list, there will be about $n^2/2$ applications, some 845,000 for 1300 people. If you look a student up in the school’s list with index every time, each comparison costs hundreds of extra steps. Build the dictionaries rank[u][s] in advance.
By the theorem in the chapter, the order in which free students apply doesn’t affect the result, so a stack works as well as a queue. The rank dictionaries take $O(n^2)$ to build, the same as the size of the lists themselves, and after that each application is handled in $O(1)$.
What next
We looked for the bottleneck between two cities. But what if there are no “ours” and “theirs,” and we want the weakest spot of the whole network: the smallest set of lines whose loss splits it into two parts, any two at all? We could go through every pair of cities and find a flow for each. Or we could do something quite strange: pick a random line, merge its two cities into one, and repeat until only two “supercities” remain. The lines between them form a cut. It may be a poor one, but repeat the experiment enough times and the minimum will almost certainly turn up. David Karger came up with this algorithm in 1993, and it is a good deal simpler than the ones built on flows. Sometimes flipping a coin is faster than thinking. How randomness becomes a tool is the subject of the next chapter.