5 Graph structure and decomposition
“That’s some catch, that Catch-22,” he observed.
“It’s the best there is,” Doc Daneeka agreed.
Joseph Heller, Catch-22 (1961), ch. 5
5.1 Is everyone in?
You turn eighteen on Friday, and this year nobody is organizing it for you. Every birthday before this one, someone else booked the table and counted the chairs, and you just turned up. This time you want everyone who matters at one table. Your friends from school have known you since you were eleven. The people from your weekend job know a version of you the school friends have never seen. The two groups have never been in one room, and you have been picturing that room for weeks.
You found Cassandra, a restaurant, a month ago, for the small private room at the back with one long table. The restaurant will hold the room until Thursday, and then it wants the number of guests, or the room goes to someone else. On Monday evening you ask in the group chat, “Who’s in?” Nobody answers there. One by one the replies come to you in private messages, the way people answer when an answer comes with conditions.
Kenji is in, no conditions. Sofia will say yes once Kenji has. Omar wants to see whether Amara is coming before he commits. Amara will confirm once Mateo has, and Mateo is waiting for Amara. By Wednesday you have two yeses and three people politely waiting for each other, and nobody is being difficult. Each of them has a reasonable rule. Together the rules have made a circle, and only you can see it, because each of them has seen only their own message.
This chapter is about seeing that kind of shape before it costs you a table. A list of who waits for whom is a graph, and most of what goes wrong with plans, builds and networks is a fact about its shape. Some people can answer right away, and answering frees others. Some are tied into a knot, where nobody can move first, and everyone waiting behind the knot is stuck too, through no rule of their own. One walk through the list finds every knot at once, even among the 353,271 packages of a whole software registry. Later in the week a different shape matters. Kenji’s cousin, who can get you the restaurant’s private room, is reachable only through friends, and if one particular phone dies, a whole circle of friends can no longer reach her. And at the dinner itself people who have never met are introduced. Links keep arriving all evening, and after each one someone asks whether two people are joined yet.
Each of those questions has its own picture: an order, a set of knots, the weak points of a network, and who is joined to whom so far. Each picture keeps some facts about the graph and drops the rest, and each comes with a promise you can check. First, though, there are three people waiting for each other, and a restaurant waiting for you.
5.2 Who can confirm first?
Topological order
Here is the chat. Kenji has confirmed. Sofia: “I won’t confirm until Kenji has.” Omar: “I won’t confirm until Amara has.” Amara: “I won’t confirm until Mateo has.” Mateo: “I won’t confirm until Amara has.” Write each person’s name once, and draw an arrow from each person to everyone who is waiting for them. Then write the order in which people can confirm.
Three minutes, on paper. You’re done when you can write that order, or say exactly who can never confirm and why.
Your drawing is a directed graph. Its vertices are the people, and an arrow in this chapter means “before” unless a passage says otherwise. The arrow from Kenji to Sofia says that Kenji confirms before Sofia, and read from the other end it says that Sofia waits for Kenji. Every figure draws it that way round.
Key idea: graphs
A graph is a set of vertices and a set of connections, each between two of them. The vertices can be any things. In a directed graph each connection is an arrow from one vertex to another, a one-way relation: a function calls another, a file imports another, a package depends on another. In an undirected graph each connection is a link that joins two vertices both ways: two people who can message each other, two computers on one cable. A graph is written \(G = (V, E)\), with \(V\) its vertices and \(E\) its arrows or links (\(E\) for edges, the usual word for both), and \(n\) and \(m\) count them.
Kenji can confirm, and then Sofia can. After that the drawing offers nothing. Amara waits for Mateo, Mateo waits for Amara, and Omar waits for Amara. In a real chat someone usually just goes first, but here going first settles nothing. Say Amara confirms now, so the order is Kenji, Sofia, Amara, Mateo, Omar. Check it one arrow at a time. The arrow from Mateo to Amara points backwards, since Amara now comes before Mateo, and that arrow is Amara’s own rule, not to go until Mateo has. By going first, she broke the rule she wrote herself. Amara and Mateo could still settle it by confirming together, but that changes their rule, and the plan is no longer the one they wrote.
An order is a list that passes the check every person once, every arrow forward. This plan has a circle, and a plan with a circle has no order. A plan without a circle may have many.
What did your method look for before it let each person confirm?
The order rests on invariant 1. The stuck set rests on invariants 2 and 3, because once the ready list runs dry they leave every unplaced vertex waiting for an unplaced one.
5.2.1 Taking whoever is ready
The box calls the order it makes a topological order⬢. Its method is Kahn’s [1], [2, Sec. 9.2]. Watch Kahn’s method on your chat before reading it as a rule. At every step it asks what your eyes asked. Who has nothing left to wait for?
Each vertex carries a waiting count, the number of vertices it still waits for (invariant 2). Graph books call it the vertex’s in-degree among the unplaced vertices. The vertices whose count is 0 sit on the ready list. It is kept as a queue, a line where whoever joined first is served first. Placing a vertex lowers the count of each vertex that waits for it, and each one whose count reaches 0 goes to the back of the queue (invariant 3).
| Step | Placed | Omar | Amara | Mateo | Kenji | Sofia | Queue |
|---|---|---|---|---|---|---|---|
| start | 1 | 1 | 1 | 0 | 1 | Kenji | |
| 1 | Kenji | 1 | 1 | 1 | 0 | 0 | Sofia |
| 2 | Sofia | 1 | 1 | 1 | 0 | 0 | (empty) |
The queue runs dry with three people left, so Kahn’s method stops there and reports Omar, Amara and Mateo as the stuck set. Every stuck person still waits for another stuck person: Amara for Mateo, Mateo for Amara, Omar for Amara. So a walk from any of them along “waits for” never leaves the set. The set is finite, so the walk must come back to someone it has already seen. A stuck set is evidence that a circle exists. The contracts chapter calls such evidence a certificate.
Now take Mateo’s message out of the chat, as if he had never sent it. Mateo waits for nobody, so the counts start at Omar 1, Amara 1, Mateo 0, Kenji 0, Sofia 1. Mateo and Kenji wait for nobody, and the queue takes them in the order the counts are listed, Mateo first. Placing Mateo frees Amara. Placing Kenji frees Sofia. Placing Amara frees Omar. The order comes out as Mateo, Kenji, Amara, Sofia, Omar, and every arrow points forward.
A count can also start above 1. Had Omar also waited for Sofia, his count would have started at 2. Placing Amara would only have lowered it to 1, and placing Sofia would have freed him. The order would come out the same.
Every method in this chapter keeps asking where it can go from the vertex it is at. Kahn’s method asks it each time it places someone, to find who was waiting for them. A grid with a row and a column for every vertex is an adjacency matrix. It answers a different question in one look, whether an arrow goes from one given vertex to another. But it keeps a cell for every pair of vertices, whether an arrow joins them or not [2, Sec. 9.1.1]. For a chat of a million people, that grid has a million million cells, and nearly all of them are empty. So the graph keeps only the arrows each vertex has, in its adjacency lists. Each vertex gets a row of the arrows leaving it, out, and a row of the arrows entering it, into. Each entry is the vertex at the other end and the arrow’s own number. Finding where to go from a vertex is then a read along one row, one step for each arrow that leaves it.
Here it is in code.
Each vertex joins the queue at most once and leaves it at most once. Each arrow lowers one count at most once. So the whole method is one look at every vertex and every arrow, as the box says.
5.2.2 Following the waits
Depth-first order and the named cycle
The stuck set says that a circle exists, but not which one. You can find it by hand. Start at anyone stuck, follow who they wait for, and keep going until you come back to someone you have seen. From Omar you go to Amara, from Amara to Mateo, and from Mateo back to Amara. The circle is Amara, Mateo, Amara.
Key idea: paths and cycles
A path is a list of vertices with an arrow from each one to the next. A path may pass a vertex more than once. A path that passes no vertex twice is simple. A cycle is a path of one or more arrows that comes back to where it started and passes no other vertex twice. One vertex reaches another when a path runs from the first to the second, and every vertex reaches itself.
A second method finds the cycle directly, by walking forwards instead of counting. A depth-first walk, or depth-first search (DFS), starts at a vertex, follows its first arrow, then that vertex’s first arrow, and so on, going as deep as it can. When a vertex has no arrows left to follow, it finishes, and the walk steps back to the vertex before it and tries that vertex’s next arrow. The vertices it has entered and not finished form a single path, from where the walk started to where it stands. If an arrow points back onto that path, the walk has found a cycle, and the path from that vertex to here, plus the arrow, is the cycle. If no arrow ever does, the reverse of the order in which the vertices finish is a topological order [3, Sec. 20.4]. It may differ from Kahn’s order, and both are right.
The walk has to remember, for each vertex on its path, how far along that vertex’s arrows it has got. The library keeps that in a frame per vertex, and the frames sit on a stack: a pile where the last thing put on is the first taken off, like a stack of plates. The walk is often written as a function that calls itself, which keeps the same frames on the program’s own call stack. That stack is small, and a long path of arrows overflows it. So the library keeps the frames itself, and a long path costs only memory.
On the chat, the library’s walk returns the cycle Amara, Mateo, Amara. Without Mateo’s message no arrow points back onto the path. Omar finishes first, then Amara, Mateo, Sofia and Kenji. Reversed, that is Kenji, Sofia, Mateo, Amara, Omar, and every arrow points forward.
A planner can show the waiting people either the stuck set or the one cycle. Which one to show is a design choice, and the design project at the end of the chapter makes you choose it and say why.
Ninja decides which build step to run next by keeping a queue of ready steps [4], and Python’s standard library ships Kahn’s method itself as graphlib [5]. On random plans of 100,000 tasks, Kahn’s method was over a thousand times as fast as scanning for a ready task after every placement.
The plans had 100,000 tasks with four prerequisites each on average. Kahn’s method took 2.12 ms, and the scan took several seconds. Even on a chat of six people, the scan was the slower of the two. It took 93 ns where Kahn’s method took 44 ns, so the scan lost on every plan measured.
5.2.3 What an order cannot tell you
An order says who goes when. When there is none, Kahn’s method says who is stuck, and the walk names one cycle. Neither says which of the stuck people hold everyone up and which are only waiting behind them, and that is the first thing you need before you ask anyone to move.
5.3 Nobody moves until somebody does
Strongly connected components
On Wednesday evening Priya messages you. “I won’t confirm until Amara has,” she writes, and later that evening Mateo, who once worked a summer with Priya, writes again: “And I won’t confirm until Priya has, too.” Now Amara waits for Mateo, Mateo waits for Amara and for Priya, and Priya waits for Amara. Omar still waits for Amara, and Kenji and Sofia are still fine.
Add Priya to your drawing, with her two arrows: from Amara to Priya, and from Priya to Mateo. The arrow from Amara to Mateo stays. Mark the people tied into one knot, where each of them waits for each of the rest, directly or through others. Then say who is only waiting behind them.
Two minutes. You’re done when you have outlined your knot and can say, for one person outside it, why they are outside.
Kahn’s method would call four people stuck: Amara, Priya, Mateo and Omar. But they are not stuck in the same way. One way to find the knot is to take every pair and ask whether each can reach the other along the arrows. That works, and it costs a search per person. What in your drawing told you that Omar was outside?
Amara, Priya and Mateo all reach each other, round the cycle Amara → Priya → Mateo → Amara. Omar is reached from Amara, but he reaches nobody else, so he cannot be in the same group as Amara. A strongly connected component is a largest group of vertices that all reach each other. It is a strong component for short. A strong component of two or more vertices, or of one vertex with an arrow to itself, has a cycle inside it, and this chapter calls it a knot. The chat has four strong components. One of them is a knot, made of Amara, Priya and Mateo. The other three are the one-person groups Omar, Kenji and Sofia. None is a knot.
The method that finds them is Tarjan and Zwick’s Algorithm T [6, Fig. 2], a single depth-first walk with no second pass. It refines the strong-component method Tarjan published in 1972 [6, p. 13]. At each vertex it finishes, it asks whether this vertex belongs to a group that started earlier on the walk, or whether a new group starts here. To answer that, the walk gives each vertex the next entry number on first meeting it. It also keeps a climb-back number for each vertex, the earliest entry number the vertex can get back to using arrows the walk has seen⬢.
When a vertex finishes and cannot climb back to a smaller entry number than its own, it leads a group. Vertices that finish and can climb back further wait on an open list until their leader takes them out, and the whole group comes out together. Once a group has come out, an arrow into it lowers no climb-back number.
The groups rest on the test in the Idea and the three invariants. Everything else in the promise follows from the groups alone, whichever method found them.
5.3.1 One walk finds every knot
Algorithm T
Look at your drawing again before the walk starts. If you had to pick one person to speak for the knot, the one the walk should treat as its leader, who would it be? Keep your guess.
The walk below runs on the library’s numbering of the chat: Omar, Amara, Priya, Mateo, Kenji, Sofia, in that order, so the walk starts at Omar. In code the chat is Digraph(6, [(4, 5), (3, 1), (1, 3), (1, 0), (1, 2), (2, 3)]). Each pair is an arrow from one person’s number to another’s. Follow the walk in stages in Figure 5.6, and watch only what changes. Each step there names what the walk does, and the stages below group those steps.
Entering, steps 1 and 2. Omar has no arrows, so he finishes at once. He cannot climb back past his own number, so he leads a group of his own. The group comes out, and Omar is marked out.
Looking at someone already out, steps 3 to 6. Amara’s arrow to Omar changes nothing, because Omar is out. The walk goes on to Priya and then Mateo.
Climbing back on a look, steps 7 and 8. Mateo’s arrow goes to Amara, who is met and not out, so Mateo can get back to her. His climb-back number falls to her 2.
Finishing without leading, and climbing back on the way, steps 9 to 12. Mateo can climb back past himself, so he does not lead and waits on the open list. As the walk comes back over Priya’s arrow to Mateo, she takes his climb-back number, 2, so she does not lead either and waits after him. Before reading on, say who comes out with Amara, and why exactly those.
Finishing as a leader, steps 13 to 15. Amara’s last arrow goes to Mateo, who has finished but is not out. So the look counts, but his 2 is no lower than hers. Amara cannot climb back past her own 2, so she leads. Everyone who joined the open list after she was met comes out with her. That is Mateo and Priya, so the knot comes out whole. Was your leader Amara? She leads only because she is the first of the three the walk meets. Had the walk started at Mateo, Mateo would have led.
The last walk. Kenji and Sofia are left, and the walk meets Kenji next. Before you step past 15, run their walk yourself. Write down each one’s entry number, who leads, and the order in which their groups come out. Steps 16 to 20 are your check.
The walk shows the box’s three invariants at work. Mateo and Priya have finished, but their group has not come out. They wait on the open list in finishing order (invariant 1). Mateo’s climb-back number came from a look at Amara, and Priya’s from the walk coming back over her arrow to Mateo. Each is an entry number that person can get back to inside the knot (invariant 2). Omar was out when Amara looked at him, so his entry number of 1 lowered nothing. Had it counted, Amara’s number would have fallen to 1, below her own 2. Then she would not lead, and her knot would never come out as a group of its own. An out person never lowers anyone’s number (invariants 2 and 3).
The groups came out Omar, the knot, Sofia, Kenji. That order is the reverse of a topological order of the groups, since each comes out only after those it points to. The library turns the numbering around, so the groups are numbered Kenji 0, Sofia 1, the knot 2, Omar 3, and every arrow between groups goes from a smaller number to a larger one.
Stopping when done. Once every vertex has been met, the walk can stop early, at the moment the climb-back number of the current vertex drops to that of the starting vertex [6, p. 12]. Everyone not yet out is then one group, whether they are on the open list or still on the path. On the chat this never happens, since nobody’s number drops after Sofia is met. Take the knot’s three on their own instead, joined only by the cycle Amara → Priya → Mateo → Amara. The walk starts at Amara with entry number 1, then enters Priya with 2 and Mateo with 3. Everyone has now been met. Mateo looks along his arrow to Amara, and his climb-back number drops from 3 to her 1. All three come out as one group, and the walk stops before anyone finishes.
A leader always takes out exactly its own group. No vertex of another group comes out with it, and no vertex of its own group is left behind.
The leader is a vertex that finishes and cannot climb back to a smaller entry number than its own. It takes out itself and the vertices on the open list met after it, which sit at the top of the list. The argument rests on the box’s three invariants, and Tarjan and Zwick prove invariants 2 and 3 as their Lemmas 3.8 and 3.9 [6, Sec. 3.2]. On Wednesday’s walk the leader is Amara, at step 15, with Mateo and Priya on the open list, met after her.
Everyone it takes out is in its group. Every vertex after the leader on the open list was met while the leader was on the walk’s path, so the leader reaches it. Pick any of them. It did not lead, so by invariant 2 it can get back to an earlier vertex of its own group. That vertex was not met before the leader, or its number would have travelled back up to the leader, and the leader would not lead. The vertex is not out either, since its group is not (invariant 3). So it is either the leader, which is the only vertex on the walk’s path not met before the leader, or a vertex after the leader on the open list (invariant 1). Repeat from there. The entry numbers fall each time, so the chain ends at the leader. Mateo gets back to Amara by his own arrow, and Priya through Mateo. The listing finds the same boundary by climb-back numbers. No vertex after the leader climbs back past the leader’s entry number, and every vertex below it was met earlier and has a smaller one.
Everyone in its group is taken out. Suppose a member of the leader’s group was met before the leader. Take a path from the leader to it. Every vertex on that path is in the group too, since the leader reaches each such vertex, and each reaches the leader through the member. The path starts at the leader and ends at a vertex met before the leader, so one of its arrows goes from the leader or a vertex met after it to a vertex met before. The walk looked along that arrow before the leader finished. The arrow’s far end is in the leader’s group, which has not come out, so the look counts: it gives a number below the leader’s, which the walk carries back up. Then the leader would not lead. So every member was met after the leader, while the leader was still on the walk’s path. None came out earlier, because a group comes out whole (invariant 3). So every member sits on the open list after the leader.
Stopping early. Once every vertex has been met, the walk may stop as soon as the current vertex climbs back as far as the starting vertex [6, p. 12]. That vertex reaches every vertex on the path. Each of them reaches the current vertex along the path, and the current vertex gets back to the starting vertex. So the path is one group. Every vertex on the open list belongs to a group whose leader has not finished. With every vertex met, that leader is on the path. Nothing is left to meet, so everything still open is one group.
In code, the open list is F, and each vertex keeps one number. It is 0 until the walk meets the vertex, and then it is the entry number, which climbing lowers. Once the vertex’s group is out, the number becomes a value larger than every entry number.
When a vertex has no arrow left to follow, it finishes, and the walk steps back.
Each vertex is entered once, each arrow is looked at once, and each vertex goes on and off the open list at most once, so the whole walk is one look at every vertex and arrow. The whole function is in scc.py.
5.3.2 Shrinking the knots
Condensation
Now shrink each group to a single vertex, and keep an arrow between two of them whenever some original arrow goes from a member of one group to a member of the other. The result is the graph of groups, or the condensation. A shrink like this is a contraction⬢. It replaces parts of a graph by single vertices and says exactly what it keeps.
What it keeps is exactly reachability between groups. One vertex reaches another exactly when its group reaches the other’s group. What it drops is everything inside a group, who waits for whom among Amara, Priya and Mateo. The graph of groups has no cycle. If it had one, every group on it would reach every other, so their members would all reach each other, and they would have been one group. So the graph of groups can always be ordered, and the walk has already numbered it in order.
5.3.3 Checking a grouping you did not compute
You paste the replies into a planning app, and it returns its own answer: “these people decide together”. Perhaps it ran Algorithm T, perhaps something else, perhaps it guessed. You did not compute its answer, and you should not have to trust it. What can you check without trusting anything the answer says about itself?
Three checks are enough, and each uses only the graph and the grouping. The contracts chapter checked a sorted list against its input in the same spirit.
- Every vertex is in exactly one group. Each person has one group number, and no group is empty.
- Each group is strongly connected. Pick one member. A search from it along the arrows, staying inside the group, must reach every member, and so must a search against the arrows. The second search uses the
intorows to follow the arrows entering each vertex. Any search that follows arrows will do: the depth-first walk, or breadth-first search, which visits first everything one arrow away, then everything two away, and so on. - The graph of groups has no cycle. Build it yourself, from the original arrows between different groups, and order it with Kahn’s method.
Here are two planted wrong answers. For each one, say which check catches it before reading on.
Check 3 is the one that is easy to get wrong. The app’s answer in Figure 5.8 splits a knot into two groups of one and supplies a graph of groups of its own, with no arrows. Checks 1 and 2 pass, since each of A and B reaches itself. If check 3 read the app’s graph, it would pass too. Built from the original arrows, the graph of groups has an arrow from A’s group to B’s and one back. That is a cycle, and the check fails.
The second planted answer joins two people who do not reach each other. Checks 1 and 3 pass, and only check 2 catches it. A search from A along the arrows reaches B, but the search against the arrows from A reaches nobody else. Both planted answers pass check 1. It catches the plainest lie, an answer that leaves Omar with no group number. So each check catches a lie the others let through.
All three checks together take a few looks at every vertex and arrow, the same order of cost as the walk that computed the answer. The whole function is in scc.py.
5.3.4 A rule per group
What to do with a knot depends on what the arrows mean, and in the chat it is for Amara, Priya and Mateo to decide. Three answers are common.
- Reject the knot. In a build, each file needs the files it imports compiled first, so an arrow means “must finish before”. There a knot can never be built, and the right answer is an error that names it. Repeating the build will not help.
- Run the group as one unit. Lean compiles a group of functions that call each other as one piece [7]. LLVM optimizes one such group at a time. Functions in one group call each other, so none of them can go first, and they are handled together. The groups are taken with the called ones first, so a function is already optimized by the time the inliner copies its body into each caller [8].
- Repeat inside the group until nothing changes. This is sure to stop when the values involved can only grow and can grow only finitely often. Then each repeat either adds something or changes nothing, and the additions run out.
The third answer has a small example in the chat. From here an arrow means “can pass a message to”. Amara and Mateo pass news to each other, and Amara passes it on to Omar. Amara hears that the table is at eight. Each person repeatedly takes in what everyone with an arrow into them has heard. Nobody forgets the news, and there is only one piece of it and three people to hear it, so the repeats stop. Run repeats in the order of the graph of groups. Amara and Mateo come first, and they repeat until nothing changes. Only then does Omar start, and one pass is enough for him.
The state where the repeats stop is called a monotone fixed point. It is monotone because news is only ever added. It is fixed because one more repeat changes nothing. Here it is in code.
A group of \(s\) members, among whom \(k\) things can be heard, takes at most \(k s + 1\) passes, since every pass but the last adds at least one thing to one member.
From here an arrow is an implication, “if this is true, then that must be”. Two new rules arrive for the guest list. At least one of Amara and Omar comes, and Sofia comes only if Omar does not. Each rule mentions two statements, and each statement is true or false. The question is whether some choice of who comes keeps both rules. With many rules of two statements each, this is the problem called 2-SAT.
Each rule “a or b” gives two arrows. If a is false, b must be true, and if b is false, a must be true. Draw one vertex for each statement and one for its opposite, such as “Amara comes” and “Amara doesn’t”. That makes six vertices. Then draw the two arrows per rule.
Drawing the rules as arrows is a reduction. It turns a new problem into one already solved, here finding the strong components. No choice works exactly when some statement and its opposite end up in one strong component, since then each forces the other [9]. Otherwise the topological order of the groups gives a choice that works: a statement is true when its group comes later than its opposite’s. Here no statement shares a group with its opposite. The library’s group order gives a solution in which Amara and Omar come and Sofia does not. Another order of the groups can give another choice that works.
In the code, person \(i\) coming is statement \(2i\) and not coming is \(2i + 1\), so a ^ 1 turns a statement into its opposite.
The whole function is in satisfiability.py.
Kosaraju and Sharir’s method, a sibling of Algorithm T, walks the graph twice, and the second walk goes against the arrows. The appendix has it, with the compact layout both walks run on.
On random graphs of a million vertices, Algorithm T found the groups about twice as fast as Kosaraju and Sharir’s two walks. On random graphs of 10,000 vertices, it was about 6,000 times as fast as a search from every vertex.
On random graphs of a million vertices, Algorithm T took 77 ms, and Kosaraju and Sharir’s two walks took 158 ms. On graphs of 10,000 vertices with four arrows each on average, Algorithm T took 249 µs. The plain way, a search from every vertex and a group for each pair that reach each other, took 1.50 s. On the six-person chat the plain way was still slower. It took 107 ns where Algorithm T took 80 ns, so the plain way lost on every graph measured.
The dependency graph of crates.io, the Rust package registry, has one vertex per package and an arrow from each package to every package that depends on it (353,271 packages, 2,372,334 arrows, the newest version of each, from the registry’s data dump of October 2026). On it, Kahn’s method took 2.6 ms and found 253,574 packages stuck. Algorithm T took 8.7 ms and found 41 knots of two or more packages. Together they hold 752 packages, and the largest holds 643 packages. Another 26 packages depend directly on themselves, each a knot of one. About one arrow in nine is an optional dependency, which a build needs only when a feature turns it on. With the optional arrows left out, the stuck set falls to 13,126 packages and the largest knot to 5 packages. The 643-package knot exists only through optional arrows, so a build without those features never meets it.
5.4 What is this all about?
Graph decomposition
Twice now the chapter has taken a graph and handed back a simpler picture, first an order, then a set of groups with a graph of groups. Each picture answered one question cheaply, and each kept some facts and dropped others. To decompose a graph here is to choose the picture the next question needs. You say what it keeps, what it drops and what it permits, and you check that it keeps its promise.
| Picture | Promise | Keeps | Drops | Permits |
|---|---|---|---|---|
| a topological order, or the stuck set | every vertex once, every arrow forward; or a set of vertices, each waiting for one in the set | who may go before whom | which order among many, and, when stuck, which cycle | running the plan in order, or naming who is stuck |
| one named cycle | a path of real arrows back to its start | one cycle | every other cycle | showing the people one cycle to break |
| strong components and the graph of groups | groups of mutual reachability; reachability between groups; no cycle among them | who reaches whom | who waits for whom inside a group | ordering the groups, with one rule for each knot |
The weakest link in a chain is the strongest because it can break it.
Stanisław Jerzy Lec, Unkempt Thoughts
5.5 Whose phone matters?
Bridges, cut vertices and the block-cut forest
The next question needs a different kind of graph. Until now an arrow went one way, but from here a link goes both ways. If Amara can pass a message to Mateo, Mateo can pass one back, so the drawing loses its arrowheads.
Thursday, the day the restaurant wants the number of guests. The private room is booked through Kenji’s cousin, and only she can confirm it. Here is who can pass a message to whom, both ways.
Which people would cut someone off from the cousin if their phone alone died?
Two minutes. You’re done when you can name every such person and say whom each one cuts off.
Look at your drawing before reading on. Whose phone matters?
The drawing is now an undirected graph. Two vertices are connected when a path of links joins them. A path and a cycle are defined as before, using links, except that a cycle may not go out and back along the same link. A message gets from anyone to anyone, because the whole drawing is one connected piece. The question is what one failure does to it. A cut vertex is a single vertex whose removal leaves more pieces than before. A bridge is a single link whose removal does the same.
Two people matter. If your phone dies, your school friends are cut off from the cousin and from your work friends too. If Kenji’s phone dies, the cousin is cut off from everyone. The link between Kenji and his cousin is a bridge, since she is alone if it fails. Every other link has a way round it.
The blocks are the largest parts of the network that no single failure inside them can split. In a block of three or more vertices, every two of them have two routes between them that share no other vertex, and a block need not have a link between every two of its vertices. A bridge with its two ends is a block too. Two blocks share at most one vertex, and a vertex they share is a cut vertex. The block-cut forest draws that: one node for each block, one for each cut vertex, and a link from each cut vertex to every block it belongs to [10, Sec. 3.1].
Who must a message from Amara go through to reach the cousin? On the forest, walk from Amara’s block to the cousin’s. The path passes your node, then the work block, then Kenji’s node. The cut vertices strictly between are you and Kenji, and those are exactly the people whose failure alone would cut Amara off from the cousin. From Priya, the path passes only Kenji. The forest also shows that the only place where your school friends and your work friends touch is you.
5.5.1 The walk, on links that go both ways
The walk keeps a climb-back number again, but it measures something new. The new number is how far up the part of the walk below a vertex can reach, using at most one link that is not on the walk’s own path, and never the link it arrived by [11], [12, Sec. 8.6.1]. At each vertex it finishes, the walk asks whether everything below this vertex could still reach the rest if the vertex above it failed.
The walk enters a vertex, numbers it, and follows its links one at a time. A link to a vertex not met yet is a tree link: the walk goes down it. A link to a vertex met earlier is a second way back, and the current vertex’s climb-back number may fall to the earlier vertex’s entry number. The walk identifies the arrival link by its own id and skips that link, since going back along it proves nothing. When a vertex finishes, its parent takes its climb-back number if it is lower, since anywhere the part below can reach, the parent’s part can reach too. If the part below cannot climb above the parent, every route out of it runs through the parent, and the parent separates it. If it cannot even reach the parent, the link between them is a bridge.
To list the blocks, the walk pushes every link it explores onto a link stack. When a parent is found to separate the part below it, the links pushed since the walk went down to that part are one block, and they come off the stack together (invariant 2). A leader takes its group off the open list in the same way.
Figure 5.14 runs the walk on Thursday’s drawing, starting at you. Vertices are numbered as the walk meets them, and each step carries the name of what the walk does.
Step 13 shows the parent test. Amara’s part of the walk is Amara, Mateo and Omar. It can climb back only as far as entry number 1, which is you. It cannot climb above you, so its links come off the stack as one block.
Before step 26, say whether the cousin’s one link is a bridge. At step 26 the cousin cannot climb back even as far as Kenji. So the link between them is a bridge. Kenji is not where the walk started, so he separates her from the rest.
Step 31 shows the rule for the walk’s starting vertex. You are where the walk started, and the starting vertex has no one above it. You separate exactly because the walk went down from you twice, once to Amara and once to Sofia.
Set beside Algorithm T’s, this walk’s climb-back number answers a different question.
| Strong components | Blocks | |
|---|---|---|
| Question | Who reaches whom both ways? | What survives one failure? |
| Climb-back number | How far back the walk can get inside an unfinished group | How far back the part below can get without the link it came by |
| Result | Groups that share no vertex, and a graph of groups | Blocks that share cut vertices, and a block-cut forest |
On links that go both ways, every link that is not a tree link joins a vertex to one above it on the walk’s path, never to another branch [11], [12, Sec. 8.6.1]. So the part of the walk below a child touches the rest of the network only through its parent, or through a link that climbs above the parent. If the part cannot climb above the parent, there is no such link, and removing the parent cuts the part off. If the part can, it keeps a way round, so the parent separates exactly when some child’s part cannot. If the part cannot even reach the parent, the tree link is its only link to the rest, and that link is a bridge. Amara, Mateo and Omar climb back only to you, so every route from them to Sofia’s side runs through you. The cousin’s climb-back number stays at 8, so her link to Kenji is her only one.
The starting vertex has nothing above it, so the parent test would always mark it. The parts below two of its children meet only through it, since no link crosses between branches. Two or more children mean parts only the root joins, and one child leaves the rest in one piece. The walk gave you two children, Amara and Sofia.
When a vertex finishes, its parent runs the tests.
The whole function is in block_cut.py.
Here is the forest’s answer to “who must the message go through?” in code.
Two links between the same two vertices are two ways round each other, so neither is a bridge, and both lie in one block. The walk identifies the arrival link by its id and skips only that link, so the second copy counts as a way back. A link from a vertex to itself joins nothing to anything, so the walk ignores it, and it lies in no block. A vertex with no links, or with only such links, is a block on its own.
On random connected networks of 10,000 vertices, the walk was about 2,500 times as fast as deleting each link in turn. For one link asked about once, though, the plain way wins.
The networks had 10,000 vertices and 20,000 links. The walk took 720 µs, and the plain way, deleting each link in turn and counting the pieces, took 1.81 s. On a million vertices, one deletion and one count took 67 ms, and the whole walk took 198 ms.
In an IETF standard for fast reroute, routers find the cut vertices and blocks of their network with the same climb-back numbers, to plan a second path for when one cable or router fails [13].
Drawing works block by block too. A graph can be drawn without crossings exactly when each of its blocks can, so Hopcroft and Tarjan’s planarity test splits it into its blocks and tests each one [14].
5.5.2 What a single failure cannot tell you
The walk answers for one failure at a time. A network with no bridge and no cut vertex can still split when two things fail at once, and the frontier map names tools for that.
Ape alone… weak. Apes together… strong.
Caesar, Rise of the Planet of the Apes (2011)
5.6 Have you two met?
Union-find
Friday, at the restaurant. Your school friends and your work friends have never been in one room, so you start introducing people. From here a link means “has been introduced to”. Thursday’s links are already there, since everyone who could pass a message has met. All evening new links arrive one at a time, and so do new people who are already on your list, partners and friends of friends who know nobody yet. One new link comes when Amara meets Sofia by the coat rack.
All evening someone asks the same question about two people: are these two joined yet, through anyone at all? Thursday’s walk could answer the question, but it would walk the whole evening’s links each time, and the question comes after every introduction.
Introductions arrive one by one, and after each one someone asks “are these two joined yet?”. What would you keep, so that each question is quick? And what has to change when an introduction joins two groups that were apart?
Three minutes. You’re done when you can say what you keep for each person and what a join changes.
A natural answer keeps one person who stands for each group, as Algorithm T’s leader did for a strong component. Each person points to someone in their group, and following the pointers up ends at the person who stands for it. Two people are joined exactly when their pointers end at the same person. To join two groups, make one group’s top person point to the other’s. But which one goes under which?
If you choose carelessly, a chain grows. Introduce nine people one after another, each time putting the group you already have under the newcomer. After eight introductions the first person is eight steps below the top. With \(n\) people, one question can cost \(n - 1\) steps, no better than searching the evening’s introductions one by one.
The answers rest on invariant 1, and the bound for one lookup rests on invariant 2. The nearly constant long run rests on path compression together with the rank rule.
5.6.1 Trees that stay shallow
The structure is called union-find, after its two operations: find an item’s root, and union two groups [2, Secs. 8.3–8.5], [3, Sec. 19.3]. The box calls them a lookup and a merge. Each group is a tree: every item points to a parent in its group, and the one item that points to itself is the root, which stands for the group (invariant 1). Each root also carries a rank, a small number that stands in for the size of its tree. A merge finds both roots and then follows two rules.
- The smaller goes under the larger.⬢ The root of lower rank points to the root of higher rank, and no rank changes. On equal ranks, the second root goes under the first, and the first’s rank rises by one.
- One group is not merged with itself. If both items already have the same root, nothing changes, and the merge answers no.
A lookup adds a third rule. It rewrites what it read.⬢ On the way back from the root, every item the lookup walked through is pointed straight at the root. The next question about any of them takes one step. This is path compression. The strings chapter used the same name for squeezing a trie’s chains, and here it shortens parent pointers. It works in the same spirit as the search chapter’s splay tree, which every access reshapes.
Six guests numbered 0 to 5 start alone, and each is its own root with rank 0. Here are four introductions, one question, one introduction that changes nothing, and one that joins a smaller tree to a larger one.
| Step | Operation | Parents of 0–5 | Ranks of 0–5 | Groups |
|---|---|---|---|---|
| start | 0, 1, 2, 3, 4, 5 | 0, 0, 0, 0, 0, 0 | 6 | |
| 1 | union(0, 1): equal ranks, 1 goes under 0 | 0, 0, 2, 3, 4, 5 | 1, 0, 0, 0, 0, 0 | 5 |
| 2 | union(2, 3): equal ranks, 3 goes under 2 | 0, 0, 2, 2, 4, 5 | 1, 0, 1, 0, 0, 0 | 4 |
| 3 | union(0, 2): equal ranks, 2 goes under 0 | 0, 0, 0, 2, 4, 5 | 2, 0, 1, 0, 0, 0 | 3 |
| 4 | union(4, 5): equal ranks, 5 goes under 4 | 0, 0, 0, 2, 4, 4 | 2, 0, 1, 0, 1, 0 | 2 |
| 5 | find(3): walks 3, 2, 0, then points 3 at 0 | 0, 0, 0, 0, 4, 4 | 2, 0, 1, 0, 1, 0 | 2 |
| 6 | union(1, 3): both roots are 0, no merge | 0, 0, 0, 0, 4, 4 | 2, 0, 1, 0, 1, 0 | 2 |
| 7 | union(5, 1): rank 1 against rank 2, 4 goes under 0 | 0, 0, 0, 0, 0, 4 | 2, 0, 1, 0, 1, 0 | 1 |
Guest 2 kept its rank of 1 after it stopped being a root, and nothing reads it again, since ranks only matter at roots. Once lookups have shortened paths, rank is no longer the height of the tree. But a root of rank \(r\) still holds at least \(2^r\) items (invariant 2), so rank still stands in for size.
The whole class is in union_find.py.
5.6.2 Why the trees stay shallow
Claim: with the rank rule, no tree is deeper than \(\log_2\) of the number of items in it.
So the lookup in Listing 5.14, which calls itself once per step up, goes at most \(\log_2 n\) calls deep. That is under 30 calls for a billion items. The program’s call stack holds that easily, unlike the depth-first walk’s long paths.
Leave lookups aside for a moment. A root’s rank rises only when two roots of the same rank \(r\) merge, and then the new tree holds both trees, as a B-tree in the search chapter grows taller only at its root. By induction, a tree whose root has rank \(r\) holds at least \(2^r\) items. A single item has rank 0 and \(2^0 = 1\) item. Two trees of rank \(r\), each with at least \(2^r\) items, make one of rank \(r + 1\) with at least \(2^{r+1}\). Going up from any item, every step reaches an item of higher rank (invariant 2), so the depth of a tree is at most its root’s rank, and a tree of \(s\) items has rank at most \(\log_2 s\). A lookup walks at most \(\log_2 n\) links. Path compression moves no item to another tree and changes no root and no rank, and it points an item only at its root, whose rank is higher than the item’s. So invariant 2 survives, and the bound still holds.
Claim: one operation can still cost \(\log_2 n\), but a long run costs nearly a constant per operation. A single lookup can walk the whole depth of its tree, so the bound for one operation is \(\log_2 n\). But every lookup that walks a long path flattens it, so the next ones are cheap. The contracts chapter named the cost of a run amortized, a cost paid in installments⬢ and averaged over the run. Over a run of \(m\) operations on \(n\) items the total is \(O(m\,\alpha(n))\). Here \(\alpha\) is the inverse of Ackermann’s function, which grows so slowly that it is at most 4 for any \(n\) that fits in a computer [3, Sec. 19.4], [15].
With a question after each of 20,000 introductions, union-find was about 2,500 times as fast as a search after each one. For one question asked once over links already stored, the two cost about the same.
The run had 20,000 introductions among 10,000 people, with a question after each. Union-find took 254 µs in all, and a search after each introduction took 639 ms. After two million links among a million people, one search over the stored links took 23 ms, and building union-find and asking it took 25 ms. Without the rank rule, a run of 999,999 merges that builds the chain leaves the first person 999,999 links below the top, and a lookup from there took 2.10 ms. With the rule, the same merges leave the first person at the top and everyone else one link below, and by the claim above no lookup among a million people can walk more than 19 links. The rule slows the merges themselves, which took 2.5 ms with it and 1.1 ms without it.
5.6.3 Joined is not the same as hard to split
Back at the dinner. Amara and Sofia are introduced. Ask union-find whether Amara and the cousin are joined, and it says yes. It said yes before the introduction too, since Amara knew you, you knew Kenji, and Kenji knew his cousin. The introduction merged nothing, and the number of groups stayed the same.
Now ask Thursday’s question again: whose phone matters? Run the block walk on the evening’s links, with the new one between Amara and Sofia.
You are no longer a cut vertex, because your school friends and your work friends now touch twice. Kenji still is, and the link to the cousin is still a bridge. Union-find saw none of that. It answers whether two people are joined, not how many ways, and the introduction that removed one of the network’s weak points looked to it like nothing at all.
Then Sofia’s partner Lin arrives, and nobody else here has met her. Until her link to Sofia is added, union-find answers “no, not joined” for Lin and anyone else. That link merges her group of one into everyone else’s. That merge it does see, and the number of groups falls from two to one.
Union-find drops the path. It knows that two people are joined, not through whom, and not why. Keeping the reason costs extra storage for every merge.
5.6.4 When everyone joins
Introductions at one dinner are a few dozen links. Other networks get millions of random links: the pipes in a block of porous rock, the pixels of an image that touch, the links between strangers in a city. Watch what happens on a grid when links arrive at random. For a long time there are many small groups. Then, over a short stretch, one group grows to cover most of the grid.
This is percolation, and union-find is how it is simulated at scale. Each new link that arrives is one merge. Keep a size at each root beside its rank, and add the two sizes when two roots merge. The largest group can then be read as the links arrive [16].
Rust’s compiler uses union-find to join unknown types that must be equal when it infers types [17]. In the paths chapter, Kruskal’s method for the cheapest network uses union-find to ask whether two vertices are joined yet.
5.6.5 What union-find cannot tell you
Groups only merge. If two people fall out, union-find cannot split their group, and “joined now?” after a link is removed needs dynamic connectivity, which the frontier map points to. And it never says how well joined two people are. For that, run the block walk.
The library states each of the chapter’s four boxes in the proof assistant Lean, one file each, TopoOrder/Spec.lean, Scc/Spec.lean, Blocks/Spec.lean and UnionFind/Spec.lean, and Lean checks every step of the proofs written against them.
Kahn’s method is proved to return an order with every arrow forward, or a stuck set in which every vertex still waits for one in the set. The depth-first order is proved to return an order or a real cycle. Algorithm T is proved to keep its invariants as the Lean states them. It is proved to return exactly the strong components, numbered so that every arrow between groups goes forward. The graph of groups it returns has no cycle. That proof covers the walk the box describes and its early stop. The faster version that was timed is checked against it by tests. The block walk is proved to report a link or a vertex exactly when removing it alone splits the network, and to list exactly the vertices between two others. The parent test and the root rule are proved of the finished walk. Union-find’s promise and both its invariants are proved, and so is the depth bound of \(\log_2 n\) links per lookup. The 2-SAT rule is proved right both ways, on Algorithm T’s groups.
Some claims are argued instead. Kosaraju and Sharir’s method rests on the fact that the vertex finishing last lies in a group no other group points into. A textbook proves it [3, Sec. 20.5]. Union-find’s long-run bound of nearly a constant per operation is cited [15] rather than proved. Spreading news through a knot has no proof here.
Every theorem starts from the graph as drawn. Whether a reply became the right arrow is a question about what its writer meant, and no proof reaches back that far.
5.7 ✎ When assumptions change practice
The confirmations do not stop when you run Kahn’s method. While it is ordering the chat, Sofia messages you a new condition: she won’t confirm until Omar has. Say which line of the topological-order box this breaks, and whether the answer you get can be wrong or only late. Then say what you would run again, and on what.
On Thursday two phones die at once, yours and Amara’s. The block walk reported that only you and Kenji matter. Say whether that report was wrong, and which line of its box tells you what it promised. Then name a network of four people in which no single phone matters and two do.
After the dinner, Lin and Sofia fall out and delete each other’s numbers. Union-find still says they are joined. Say which line of its box this breaks, whether the answer is now wrong, and what you would have to keep instead to answer “joined now?” after a link disappears.
A build tool reports that six of its files form one strongly connected component and offers to “repeat the build until it settles”. Say when that is safe and when it never ends, and what you would ask about the files before you allow it.
5.8 ◆ What these are actually made of big picture
The chapter built an order, a walk that finds knots, a picture of groups, a walk that finds weak points, and a forest of trees that only merge. Open them up, and six ideas do all the work.
Kahn’s method = topological order. Topological order: take whoever waits for nobody, and each placement may free someone else. When nobody is free and people remain, they are the stuck set, the evidence that a cycle holds them.
Strong components and the graph of groups = DFS timestamps and low-link + contraction. DFS timestamps and low-link: one walk numbers people as it meets them, and a climb-back number says how far back each can get. Whoever cannot get back past themselves leads a group. Contraction: shrink each group to one vertex, and the knots are gone, leaving a graph with no cycle that a topological order can handle again.
Blocks and the block-cut forest = DFS timestamps and low-link, on links both ways. The same walk, with a climb-back number that measures something new, answers a new question. Can the part below a vertex climb above it without the link it came by? If not, the vertex separates.
Union-find = merge the smaller into the larger + rewrite on read. Merge the smaller into the larger: the tree of lower rank goes under the other, so no lookup walks more than \(\log_2 n\) links. Let a read rewrite what it walked: a lookup points everyone it passed straight at the root, so the next one is short. Neither changes who is in which group, only how fast the answer comes.
Spreading in a knot = strong components + monotone fixed point. Monotone fixed point: inside a group the news goes round until a pass changes nothing, and since nobody un-hears news, that pass means done. The groups, in topological order, then hand it on, each group once.
Some of these parts can be swapped for another part that does the same job. Figure 5.22 shows a few, each beside the choice this chapter made. The first four rows keep the promise, though they can change which right order comes out or what it costs. Without the rank rule, one lookup can walk a chain through every item. The swap in the last row breaks the promise. If a look at a vertex that is already out may lower a climb-back number, then on Wednesday’s chat Amara no longer leads, and her knot never comes out as a group of its own.
5.8.1 Choosing one, under pressure
Each row is a short contract, in the contracts chapter’s sense. The last column is its failure mode, what you see when its box’s Assumes line stops being true. In every row, that failure is an answer that looks exactly like a right one.
| The question | The picture | What it drops | If it breaks |
|---|---|---|---|
| who can go first, and in what order? | a topological order, or the stuck set | which of many orders; which cycle | an arrow added while it runs can leave a vertex placed before one it now waits for |
| which cycle holds them up? | one named cycle | every other cycle | an arrow added while it runs can end up pointing backwards in the order |
| who can only decide together, and what waits behind them? | strong components and the graph of groups | who waits for whom inside a group | an arrow added while it runs can leave apart two groups that now reach each other |
| whose single failure splits the network, and who stands between two people? | bridges, cut vertices, the block-cut forest | what two failures do | two failures at once can split a network reported as having no weak point |
| are these two joined yet, while links keep arriving? | union-find | the path, and how many paths | after a link is removed, its two sides still answer joined |
5.8.2 What each one costs
| Method | Time | Space | Measured |
|---|---|---|---|
| Kahn’s order | \(\Theta(n + m)\) | \(\Theta(n)\), a count per vertex and a queue | 2.12 ms on 100,000 vertices; the scan several seconds |
| depth-first order | \(\Theta(n + m)\) | \(\Theta(n)\), a frame per vertex on the path | not measured |
| Algorithm T | \(\Theta(n + m)\) | \(\Theta(n)\), a few numbers per vertex | 249 µs on 10,000 vertices; the plain way 1.50 s |
| the block walk | \(\Theta(n + m)\) | \(\Theta(n + m)\), a frame per vertex and the link stack | 720 µs on 10,000 vertices; deleting each link 1.81 s |
| union-find | \(O(\log n)\) per lookup; \(O(\alpha(n))\) per operation over a long run | \(\Theta(n)\), a parent and a rank per item | 254 µs for 20,000 links and questions; a search each 639 ms |
5.8.3 The same ideas, over and over
| Idea | Where else it runs |
|---|---|
| topological order | build systems; Lean’s declaration order; filling a table in the paths chapter |
| DFS timestamps and low-link | Lean grouping mutually recursive functions; LLVM’s call-graph passes; 2-SAT |
| contraction | road maps that answer in milliseconds, by contraction hierarchies (the paths chapter’s big picture); Karger’s cut in the flow chapter |
| merge the smaller into the larger | Kruskal’s method in the paths chapter; percolation at scale |
| rewrite on read | union-find’s compression, as in Rust’s type inference; the search chapter’s splay tree |
| monotone fixed point | compiler analyses; Bellman–Ford’s rounds in the paths chapter |
5.9 ◆ Where that leaves the dinner big picture
Nobody at the dinner ran an algorithm. But each evening asked a question with a different shape, and each shape had its own picture. On Wednesday the question was an order, and the answer was either an order or the people who could not be placed. Then it was the knot, and the picture shrank the knot to one vertex, so the rest could be ordered around it. One walk found every knot, with two numbers per person, and each knot came out whole. On Thursday it was a single failure, and the picture was the blocks and the forest between them. On Friday it was “joined yet?”, and the picture was a forest of trees that only merge. Each picture kept what its question needed and dropped the rest, and each one could be checked.
Every answer here was exact, found by following links one at a time. Take two groups of 50 friends each, where everyone knows everyone else in their own group. Three links between six different people join the two groups. The block walk finds no cut vertex and no bridge, and union-find puts all 100 people in one group. All of it is true, and none of it says that the network is two groups held together by three links. The spectral chapter answers that from one matrix built from all the links at once [18, Sec. 1.5.4], ch. 21.
These structures also have other standard names. A cut vertex is also called an articulation point, and a block is a biconnected component. Union-find is also called a disjoint-set forest.
Every check in the chapter checked the picture against the graph. None of them checked the graph against the world. Omar’s reply said “I won’t confirm until Amara has”, and the drawing turned that into an arrow. If Omar had meant “I’d like to know whether Amara is coming”, the arrow was wrong, and every promise built on it held for the wrong plan. You checked the plan. Did you write down the right ifs?
5.10 ✎ Hands-on projects practice
Projects come first. In each one you build something, measure something, or explain something to another person. They have no single right answer, so judge them against the checks each one asks you to build. After them come the self-check problems, numbered exercises that each come with an answer you can check. Where a project needs code, let an AI write it, and the times given assume that it does. Three things are still your job when the AI helps. You say what the code must do, build the check that shows it does, and judge what comes back.
Project 1 · checking · medium · ~1 hour
Check a schedule you did not make. Ask an AI for a build order of thirty files with their imports, or a grouping of them into strongly connected components. Before you ask, write the checks an answer must pass. An order must hold every file once and put every import before the file that needs it. A grouping must pass the three checks of Checking a grouping you did not compute, with the graph of groups built from the original imports. Run them. Then delete one line from your checker, and find an answer the weakened checker passes that the full one rejects. Say whether that answer’s fault was in the code, in the box it was meant to keep, or in the design of the checker.
Project 2 · union-find · medium · ~1.5 hours
Watch a cluster appear. Build a grid of \(n\) by \(n\) sites, add links between neighboring sites in random order, and keep the groups with union-find. Plot the largest group’s share against the share of links added, for three sizes of grid. Then link without the rank rule, always putting the first root under the second, on a sequence of merges that builds a chain. Measure the chain’s depth. Then time a lookup from the bottom of the chain and the same lookup again, with and without path compression. Say which rule mattered on random links, and which on the chain.
Project 3 · the block walk · medium · ~1 hour
Find the weak points of a real network. Take a public map of a small network, a city’s tram lines or a country’s rail links, or draw one with at least twenty stops. Report its bridges and its cut vertices. Then pick two stops, and report the stops between them whose failure alone would cut the two apart. Check one reported bridge by deleting it and counting the pieces. Then say which one extra link would remove the most cut vertices.
Project 4 · optional · reachability · ~2 hours
What a search index can reach. Build a small directed graph where each point links to its few nearest others, as a graph index does. From the entry point, follow every link, ignoring distance, and list the points never reached. Then run a search that keeps only the closest candidates, the geometry chapter’s beam, and show a point that is reachable and still never found. Say why “reachable” is not “found”. Build the graph yourself. The geometry chapter’s beam search is all you need from it.
Project 5 · design · hard · ~3 hours
Design a dependency analyzer, with an AI. A team keeps its tasks and what each waits for, and some tasks are already done. It wants four lists: what can start now, what will be able to start later, what is caught in a knot, and what is blocked behind one. There are about a hundred thousand tasks with a few prerequisites each. The chapter’s structures are one answer. Find yours, and check that it keeps what it promises.
- Write the problem first. Write the top half of a box: goal, promise, cost, assumptions. Leave the idea and the invariants empty. They are what the design will find.
- Check the promise where a machine holds it. Read
Workbench.Contractin the library’slean/AlgoDesign/Graphs/Workbench/Spec.lean, the contract every candidate owes. Check that each line says what your promise says, and change the contract where it does not. - Hand the top half to an AI, with the bench,
algodesign.graphs.workbenchinpython/algodesign/graphs/workbench.py. A candidate sees the tasks only through the bench’s countedPlan. Ask for the code in one language and for its box. The AI may tune onPRACTICE_SEEDS. Keep some seeds and some of your test plans to yourself. - Judge what comes back. Run
judgeon your own seeds and read itsreport, beside the chapter’s ownchapter_candidate. Then, on plans you wrote and plans the AI did not see, run your own checks: every unfinished task in exactly one list, and each list’s rule. - Change the requirement. The team now asks why a blocked task is blocked, and wants a chain of real waits from a task in a knot to the blocked task. Say what your representation has to keep that it did not, and change it.
- Choose the evidence. When nothing can be ordered, should the analyzer show the stuck set or a named cycle? Choose, and say why, for the team that reads it.
Hand in the final box whole, with a line for each repair saying whether it fixed the code, the box or the design, and why. ★ Prove in Lean that your design meets Workbench.Contract.
Another brief or another AI gives another run. This is one.
Round 1. The AI dropped the done tasks and took the rest from the front, as Kahn’s method does. Tasks free from the start were ready now, and tasks freed along the way were later. What never came free it split into strong components. A group of two or more tasks, or a task that waits on itself, was counted in a knot, and the rest were blocked. The answer was the four lists and nothing else, and every check passed. The AI’s own note found what the checks had read past. The AI’s box said a task in a knot “waits, through other unfinished tasks, on itself”, but a task that waits on itself directly goes through no other task. Read by its words, that task is in no knot and is not ready. Nothing before it is in a knot either, so the box files it under later. A task that will never start is listed as one that will. The AI counted it a knot. The check in step 2 had read the promise for what it meant, not for what it said. The blocked list had the same slip the other way, saying “through other tasks” where the knot said unfinished ones. Fix the box: a task in a knot waits on itself, directly or through other unfinished tasks, and a blocked task waits, through other unfinished tasks, on a task in a knot.
Round 2. The team then asked why a blocked task is blocked. The AI kept the four lists and added one search along waits between unfinished tasks. The search goes out from every knot at once, one step at a time. For each blocked task it kept one number, the task it was first reached from. Asked why, it walks those numbers back to a knot and turns the walk around. Every chain it gave was made of real waits, and answering never read the plan again. Nothing to repair. On the same plans it kept fewer numbers per task than the chapter’s own structures, Algorithm T and the same search from the knots.
Along the way the AI noted two things no check looks for. On plans made of long chains, a blocked task’s shortest chain ran to 12,500 tasks, more than any team will read. The promise says nothing of its length. Asked whether a stuck plan should show the stuck set or a named cycle, it chose a cycle, with how many tasks the knot holds and how many wait behind the knot. A team breaks a knot one wait at a time, and a list of about 20,000 tasks in a knot says nothing about where to cut. Which answer helps is the goal’s to say, and only a reader of the answers can judge it.1
Here is the end of a group’s coming out in Algorithm T, with one line missing.
def come_out(members):
for x in members:
group_of[x] = len(groups)
groups.append(members)Every test passes on graphs where no arrow points into a group that has already come out.
- Before running anything, say which line is missing, and which of the box’s invariants it breaks.
- Find the smallest graph on which this version reports a wrong grouping. Smallest means fewest arrows. Say what it reports, and what is right.
- Run your graph through the three checks of Checking a grouping you did not compute. Which check catches it?
Only after you have your own answer, hand the four lines to an AI and ask what is wrong with them. Does its answer find the problem? Whether the line matters depends on what the rest of the walk reads, which the AI was not shown.
5.11 ✎ Self-check problems practice
Transfer 1 · middling · ~30 min
From which day on? A town lays one cable a day between two of its eight places, A to H, and never removes one. In order, days 1 to 12: DE, CH, HF, BE, AG, DB, HE, HD, CB, CG, GF, AF.
- From which day on can A reach H? Answer it with union-find, one cable at a time.
- Now you may not keep anything between questions. All you have is a check that takes a day \(t\), walks the first \(t\) cables, and says whether A reaches H. Use the contracts chapter’s binary search, the one that found the first build that crashed. It needs one sentence to stay true at every step. What is that sentence here, and why does it stay true? Run it on the twelve days, starting from
lo= 1 andhi= 12 and checking the middle day, rounded down, untillo=hi. How many checks did you need, and how many would 5,000 cables need? - Which assumption of union-find’s box is the same fact that lets the binary search work? What happens to both if cables can also be cut?
- Day 10. Before it, A is joined only to G (day 5). Cable CG on day 10 joins A’s group to the group of C, H, F, E, D and B.
- The sentence is “the first day is between
loandhi”, starting from 1 and 12. It stays true because reaching only ever switches from no to yes as days pass, so a no at day \(t\) means the answer is later than \(t\), and a yes means it is \(t\) or earlier. The checks go day 6 no, day 9 no, day 11 yes, day 10 yes. That is four checks, and the answer is 10. Other starts and roundings can get lucky with three on these days, but twelve days need four in the worst case, since \(2^3 = 8 < 12\). For 5,000 cables it takes at most 13 checks, since \(2^{13} = 8{,}192 \ge 5{,}000\). And 13 can be needed, since \(2^{12} = 4{,}096\) is too few. - “Groups only merge, never split.” It is what makes “joined by day \(t\)?” switch once, from no to yes. If cables can be cut, union-find gives wrong answers. The answers can switch back, and the binary search’s sentence stops being true.
Transfer 2 · middling · ~30 min
Which scooters stand together? A city wants to know which parked scooters stand in groups. Two scooters are close when they are at most 2 blocks apart east to west and at most 2 blocks apart north to south. A group is every scooter you can reach by steps from one scooter to a close one. Nine scooters stand at A (1, 1), B (2, 2), C (4, 4), D (9, 2), E (10, 4), F (5, 9), G (7, 9), H (11, 5) and I (5, 5).
- Take the scooters in turn. Keep the groups in a union-find. For each scooter, ask the geometry chapter’s range tree for every scooter in the square 2 blocks each way around it. Merge the scooter you asked about with each one found. Which merges join two groups, and how many groups are left?
- Checking every pair would also work. How many pairs is that for nine scooters, and for 100,000? About how many steps do the square questions take for 100,000 scooters?
- Now close means at most 2 blocks apart in a straight line. Why can you still ask for the square, and what must happen to everything it finds? What are the groups now? At night the scooters start to move. Which line of each structure’s box stops holding?
- Six merges join two groups, AB, BC, CI, DE, EH and FG, so \(9 - 6 = 3\) groups are left. A, B, C and I form one group. D, E and H form another, and F and G the third. A’s square finds B, B’s finds A and C, C’s finds B and I, D’s finds E, E’s finds D and H, F’s finds G, G’s finds F, H’s finds E, and I’s finds C. Every other merge, such as B with A, finds the two already in one group and changes nothing.
- 36 pairs for nine. For 100,000 it is \(100{,}000 \cdot 99{,}999 / 2\), about 5 billion. The squares take 100,000 questions, each about \((\log_2 100{,}000)^2 \approx 276\) steps plus one per scooter found, so the total is a few tens of millions of steps. The estimate holds while each square has a few scooters. If they all crowded into one square, every question would report all of them, and the count would be back near the pairs. Union-find adds nearly a constant per merge.
- A scooter within 2 blocks in a straight line is within 2 blocks each way, so the square misses nothing. But it can find too much, and every scooter it finds has to be measured, the geometry chapter’s check every candidate. B and C are inside each other’s squares but \(\sqrt{8} \approx 2.8\) apart, and D and E are \(\sqrt{5} \approx 2.2\) apart. There are now five groups: A and B, C and I, E and H, F and G, and D alone. When the scooters move, the range tree’s goal no longer holds, since it is for places that don’t change. Union-find’s groups only merge, never split, so a scooter that rides away still counts as part of its old group. Both have to be built again from where the scooters stand now.
Transfer 3 · middling · ~25 min
Who must every message pass through? A vertex dominates another when every path from the start to the other passes through it.
- In Thursday’s drawing (Figure 5.12), start at Omar. Which people must every message from Omar to the cousin pass through? Read the answer off the block-cut forest, without trying paths.
- Now arrows. Five vertices S, A, B, C, D, with arrows S→A, S→B, A→C, C→B, B→D and C→D, and S the start. Find every dominator the plain way. Delete one vertex at a time, search from S, and see who is no longer reached. How many searches is that for \(n\) vertices, and what does each cost?
- Forget the arrowheads and run the block walk on the same five vertices. Which vertex does it miss as a dominator, and which path in the drawing without arrowheads explains the miss?
- You and Kenji. On the forest the path from Omar’s block to the cousin’s runs through you, then the work friends’ block, then Kenji, and the cut vertices on that path are exactly the people whose phone alone would cut Omar off from the cousin.
- Deleting A leaves C unreached, so A dominates C. Deleting B, C or D leaves everyone else reached, since B is reached through C or straight from S, and D through B or C. So S is the nearest dominator of A, B and D, and A of C. That is one search per vertex, so \(n\) searches. Each is a look at every vertex and arrow, so the total is about \(n(n+m)\) steps.
- Without arrowheads the five vertices form one block, so the walk finds no cut vertex and says only S dominates C. The walk misses A. The path S, B, C reaches C without A, but it uses the arrow C→B backwards, which the arrows do not allow. Each vertex’s nearest dominator is its parent in the dominator tree, and Lengauer and Tarjan build the whole tree in near-linear time, from depth-first numbers [19]. Compilers use it to find where values from different branches of a program meet [20], and memory tools to show how much memory each object keeps alive [21].
Transfer 4 · middling · ~25 min
Can a grouping bring its own evidence? The contracts chapter trusted an answer that carries evidence you can check, like a sorted list beside its input. Now the planning app sends evidence with its grouping of Wednesday’s chat (Figure 5.5). Its groups are Kenji; Sofia; the knot of Amara, Priya and Mateo; and Omar. For each group it picks one member and sends two trees. In the first, each member but the chosen one has an arrow coming in from a member listed before it. In the second, each has an arrow going out to a member listed before it. A group of one sends two empty trees. For the knot the app picks Amara.
- Out from Amara: Amara→Priya, then Priya→Mateo.
- Into Amara: Mateo→Amara, then Priya→Mateo.
- Check both trees against the drawing. What do they prove together about the knot, and which of the three checks of a grouping does that settle?
- How many arrows do check 2’s searches look at on the chat, and how many do the trees ask you to confirm? Which checks do the trees leave to do, and why? Try splitting the knot into Amara with Mateo, and Priya alone, each piece with its own trees.
- A second app puts Omar into the knot. For Amara it sends the out tree Amara→Omar, Amara→Priya, Priya→Mateo, and the into tree Mateo→Amara, Priya→Mateo, Omar→Amara. Check it. What does the evidence fail to prove, and does that alone make the grouping wrong? What if the into tree had left Omar out instead?
- All four arrows are in the drawing. Priya waits for Amara, Mateo for Priya, and Amara for Mateo. Each tree lists Priya and Mateo once, each hung on someone listed before. The out tree shows that Amara reaches Priya and Mateo, and the into tree that both of them reach Amara. So any two of the three reach each other through Amara. Mateo, for one, reaches Priya by way of Amara. The knot is strongly connected, which settles check 2 without a search.
- The searches look at every arrow twice, once from each end, so there are 12 looks for the 6 arrows. Nine of those looks belong to the knot. Among them are Amara→Omar, which leaves the group, and a second arrow into Mateo, who is already found. The trees name 4 arrows, 2 in each. However many arrows a graph has, the trees name fewer than 2 per vertex. Confirming one is a single look when the app gives each arrow’s own number, as the rows store it. With only two names, you would search a row. The trees leave checks 1 and 3. They say nothing about arrows between groups, so they cannot show that a group is as large as it should be. Split the knot. Amara→Mateo and Mateo→Amara make good trees for Amara with Mateo, and Priya alone needs none. Every tree holds, yet Amara→Priya and Priya→Mateo run between the two pieces both ways. Check 3 builds its graph from the arrows and finds that cycle. Check 3 still reads every arrow once, so the evidence saves check 2’s searches, not the look at every arrow.
- Omar→Amara is not in the drawing. The arrow runs from Amara to Omar, since Omar waits for her. The out tree holds, and it proves that Amara reaches all four. The into tree proves that Priya and Mateo reach Amara, and nothing about Omar. Broken evidence alone does not make a grouping wrong. It leaves the grouping unproved, and the checker refuses the evidence or runs check 2’s search instead. Here the search settles it. No arrow leaves Omar, so he reaches nobody, and the grouping is wrong. An into tree without Omar would prove nothing about him either, so the check also confirms that both trees list every member.
Transfer 5 · middling · ~25 min
Take a merge back. A type checker joins two groups on a guess. Then it finds the guess was wrong and wants the merge undone. Swap one part of union-find. A lookup no longer rewrites what it read, so there is no path compression. The rank rule stays. Every union call also writes one entry in a log, naming the root that went under and whether the other root’s rank rose. When nothing merged, the entry is empty. Undo takes the newest entry back. An empty entry changes nothing. Otherwise the root that went under is a root again, a risen rank falls by one, and there is one group more.
- Run the six guests of Table 5.4, steps 1 to 6, without path compression. Where does guest 3 point after step 5, and what does the log hold after step 6? Then undo twice. What are the parents, the ranks and the number of groups now?
- Put path compression back, keep the same log, and run steps 1 to 6 again. Then undo three times. Which guest ends up in the wrong group, and why? Does the number of groups show it?
- Without compression, does the promise of union-find’s box still hold? What happens to the cost of one lookup, and to the cost of a long run?
- The structure with undo promises two things: right answers to “are these two joined?”, and an undo that takes the last
unioncall back exactly. Say which part each comes from, and which part only keeps lookups cheap.
- Guest 3 still points at 2. The lookup walked 3, 2, 0 and answered 0, but rewrote nothing. Oldest first, the log holds 1 under 0, 3 under 2, 2 under 0 and 5 under 4, each with a rise. Then comes an empty entry for step 6, which merged nothing. The first undo takes back step 6 and changes nothing. The second takes back step 4, so 5 is a root again and 4’s rank falls back to 0. The parents of 0–5 are 0, 0, 0, 2, 4, 5. The ranks are 2, 0, 1, 0, 0, 0, and there are 3 groups.
- Guest 3. The lookup in step 5 pointed 3 straight at 0, and no entry recorded it. The three undos take back steps 6, 4 and 3, so 2 is a root again and 0’s rank falls to 1. The parents are now 0, 0, 2, 0, 4, 5. Guest 3 still points at 0, so it sits with 0 and 1. Yet step 2, which put it with 2, was never taken back. The log holds what each
unioncall wrote, and a lookup’s rewrites are not in it. The group count says 4, the right number for steps 1 and 2, so the count alone hides the error. And root 2 now has rank 1 with one item in its tree, fewer than the \(2^1\) that invariant 2 requires. - Yes. Every answer comes from following parents up to the root (invariant 1), and a merge keeps that true by putting one root under another, with compression or without it. A lookup now changes nothing at all. One lookup still walks at most \(\log_2 n\) steps, because that bound comes from the rank rule (invariant 2), and the rank rule stays. The nearly constant cost over a long run is gone. Nothing shortens a path, so asking about the deepest item again and again costs the same whole walk every time.
- Right answers come from invariant 1, which every merge keeps. An exact undo comes from the swap itself. When lookups write nothing, the only changes are what each
unioncall wrote, one parent and perhaps one rank, and the log holds exactly those. The rank rule only keeps lookups cheap, at most \(\log_2 n\) steps each.
Here are forty exercises. Each shows roughly how long it takes, and everything you need for them is in the chapter so far. The answers are on a page of their own.
If you only do four, do Exercises 1, 7, 12 and 15.
They are grouped by kind of task, not by structure. To practice one structure, here are the exercises for each section:
- Who can confirm first?: 1, 2, 3, 4, 5, 6, 17, 26, 32, 35, 37
- Nobody moves until somebody does: 7, 8, 9, 10, 11, 18, 22, 23, 28, 29, 33, 39
- Whose phone matters?: 12, 13, 14, 19, 24, 27, 40
- Have you two met?: 15, 16, 20, 21, 25, 30, 31, 34, 36, 38
5.11.1 Run it and report the state
Exercise 1 · gentle · ~10 min
Run Kahn’s method on the graph of Figure 5.23. An arrow from x to y means x must be placed before y. Count the arrows into every vertex, queue the vertices with none, from a upward, and keep the queue first in, first out: take the front vertex, place it, lower the count of every vertex its arrows lead to, in alphabetical order, and queue a vertex when its count reaches 0. Which vertices are ready at the start, which vertices wait in the queue after each placement, and what is the order?
Exercise 2 · gentle · ~10 min
Run Kahn’s method, as in Exercise 1, on the graph of Figure 5.24. Which vertices does it place, in what order, and which vertices are stuck?
Exercise 3 · gentle · ~10 min
Run the depth-first walk on the graph of Exercise 1. Start from a, then the next vertex not yet entered in alphabetical order, and take each vertex’s arrows in alphabetical order of where they lead. A vertex finishes when every arrow out of it has been followed. In what order do the vertices finish, and what order does reversing it give?
Exercise 4 · middling · ~10 min
Run the depth-first walk on the graph of Figure 5.25. Start from a, then the next vertex not yet entered in alphabetical order, and take each vertex’s arrows in alphabetical order of where they lead. Stop at the first arrow that leads to a vertex still on the walk’s path. Which vertices are on the path then, from the start, which arrow is it, and which cycle does it name?
Exercise 5 · middling · ~20 min
Walk the graph of Figure 5.26 depth first, to the end this time: an arrow to a vertex on the path does not stop the walk. Start from a, then the next vertex not yet entered in alphabetical order, and take each vertex’s arrows in alphabetical order of where they lead. Keep a clock that starts at 0 and ticks by one each time the walk enters a vertex or leaves it for good, and write down each vertex’s two times. Then sort the arrows into four kinds. A tree arrow is one the walk enters a new vertex by. A back arrow leads to a vertex still on the path. A forward arrow leads to a vertex already left that was entered after the arrow’s own start, so it lies below it in the walk. A cross arrow leads to a vertex already left that was entered before the arrow’s start. Give each vertex’s times and each kind’s arrows, in the order the walk looks along them.
Exercise 6 · middling · ~15 min
The links of Figure 5.27 go both ways, and no two vertices share more than one link, so a vertex’s neighbors and its links are the same count. Delete any vertex with fewer than k neighbors left; deleting it lowers each neighbor’s count by one; repeat until every vertex left has at least k. What is left is the k-core (Batagelj and Zaveršnik). Which vertices form the 2-core, and which the 3-core?
Then: Kahn’s method keeps a queue of the vertices ready to place. What would you keep so that each deletion finds the next vertex to delete without looking at every vertex again?
Exercise 7 · hard · ~25 min
Run Algorithm T on the graph of Figure 5.28. Start from a, then the next vertex not yet entered in alphabetical order, and take each vertex’s arrows in alphabetical order of where they lead. Number vertices from 1 as the walk enters them; a vertex’s climb-back number starts as its own number. Looking along an arrow to a vertex met but not out, or coming back over an arrow, a vertex takes the other end’s climb-back number if it is smaller; a vertex whose group is out is passed by. Stop when done: once every vertex is entered and the current vertex climbs back as far as the root it started from, everything not yet out comes out as one group. Give each vertex’s entry number, its climb-back number when its group comes out, the groups in the order they come out, and the groups numbered from 0 so that every arrow between two groups goes from a smaller number to a larger one.
Exercise 8 · hard · ~20 min
Walk the graph of Exercise 7 again, recursively and to the end, with no early stop. Start from a, then the next vertex not yet entered in alphabetical order, and take each vertex’s arrows in alphabetical order of where they lead. Run it twice, with two rules for an arrow from a vertex to one met but not out. The classical rule: the vertex takes that vertex’s entry number if it is smaller. Algorithm T’s rule: it takes that vertex’s climb-back number if it is smaller. In both, coming back from a vertex it entered, a vertex takes that vertex’s climb-back number if it is smaller, and a vertex leads a group when it finishes with its climb-back number equal to its own. What is each vertex’s climb-back number when it finishes, under each rule?
Then: Where the two tables differ, why do the two walks still find the same groups?
Exercise 9 · gentle · ~5 min
Shrink each group of Exercise 7 to one vertex, keeping the numbers it gave them, and keep one arrow from group c to a different group d whenever some arrow of the graph leads from a vertex of c to a vertex of d. Which arrows does the graph of groups have?
Exercise 10 · middling · ~10 min
In the graph of Exercise 7, read an arrow as “can pass a message to”. a has heard news 1 and d news 2; nobody else has heard anything, and nobody forgets. Settle the groups of Exercise 7 in their numbered order, and inside a group pass news along its arrows until a whole round changes nothing. What has each vertex heard at the end?
Exercise 11 · middling · ~20 min
Find true or false for x1, x2 and x3 that makes every clause hold: (¬x2 or x3), (x2 or x1), (¬x2 or ¬x3), (¬x2 or x1), (¬x3 or ¬x1). Draw the six literals x1, ¬x1, x2, ¬x2, x3, ¬x3 as vertices, in that order, and give each clause (p or q) its two arrows, ¬p → q and ¬q → p. Find the groups with Algorithm T, starting from x1 and taking each literal’s arrows in the order above, and number them so every arrow between groups goes from a smaller number to a larger one. Then set xᵢ true exactly when its group’s number is larger than ¬xᵢ’s. What are the groups, and the answer?
Then: Add one clause that leaves no answer at all, and say how the groups show it.
Exercise 12 · hard · ~25 min
Run the block walk on the graph of Figure 5.29. Start from a, then the next vertex not yet entered in alphabetical order, and take each vertex’s links in alphabetical order of the vertex at the other end. Number vertices from 1 as the walk enters them. Skip the link a vertex was entered by. A link to a vertex entered earlier goes on the link stack and passes that vertex’s entry number if it is smaller; a link to a new vertex goes on the stack and the walk goes down it. When a vertex finishes, the vertex above it takes its climb-back number if smaller; if that number is no earlier than the upper vertex’s own, pop the stack down to the link between them: one block. Give each vertex’s entry number and its climb-back number when it finishes, the blocks in the order they come off the stack, the bridges and the cut vertices.
Exercise 13 · middling · ~10 min
Draw the block-cut forest of the graph of Exercise 12: a node for each block, a node for each cut vertex, and a line from each cut vertex to every block that holds it. Which vertices, each failing alone, cut b off from e?
Exercise 14 · middling · ~10 min
In the graph of Figure 5.30, f and g are joined by two links. Run the block walk of Exercise 12: it skips only the very link a vertex was entered by, so the other copy counts as a link back. Which links are bridges, and which vertices are cut vertices?
Then: Now skip every link back to the vertex a vertex was entered from. What does the walk report, and which answer is right?
Exercise 15 · middling · ~15 min
Eight items a to h start alone, each of rank 0. A union looks up its first item, then its second; if the two roots are the same it merges nothing and answers no. Otherwise the root of lower rank goes under the other, and on equal ranks the second root goes under the first, whose rank rises by one. Every lookup points each item it walked straight at the root. Run union(g, a), union(f, b), union(f, e), union(a, g), union(f, b), union(g, h), union(g, b), find(b), union(g, e), union(d, b). What does each step answer, how many groups are there after it, and where does every item point at the end, with which ranks?
Exercise 16 · middling · ~15 min
Seven items a to g start alone, in a union-find that can take merges back. It never shortens a path, and unions follow the rules of Exercise 15. Every union call writes one entry in a log, an empty one when it merges nothing, and an undo takes back the last entry. Run union(g, d), union(g, f), union(d, a), union(a, d), union(f, g), undo(), undo(), union(a, d), joined(g, a). What does each step answer, how many groups are there after it, and where does every item point at the end?
5.11.2 Which promise broke
Each item hands you something a program produced and claims is correct. Say whether it is, and if it is not, name the promise or invariant it breaks and the smallest change that would mend it. One of them is correct, and saying so is the answer.
Exercise 17 · middling · ~10 min
Kahn’s method on the graph of Exercise 1 returns the order a, e, b, d, f, c, h, g.
Exercise 18 · middling · ~10 min
A program groups the vertices of Exercise 7 as {b, g}, {d}, {c, e, f}, {h}, {a}, and says each group’s vertices reach each other.
Exercise 19 · middling · ~10 min
On the graph of Exercise 12, a program reports f–g as a bridge.
Exercise 20 · middling · ~10 min
A union-find has received the links of Figure 5.31, one union each, and answers that a and b are not joined.
Exercise 21 · middling · ~10 min
A union-find over a to h stores the links a→a, b→a, c→b, d→a, e→e, f→e, g→g, h→a, the ranks a 2, b 1, c 0, d 0, e 1, f 0, g 0, h 0, and a count of 3 groups.
5.11.3 You supply the input
Exercise 22 · middling · ~10 min
Add one arrow to the graph of Exercise 7 so that every vertex reaches every other: the whole graph becomes one group. Give one that works.
Then: Say which arrows work, all of them, and why.
Exercise 23 · middling · ~15 min
Two weak checkers judge a grouping of the graph of Exercise 7. The first checks that every vertex is in exactly one group and each group is strongly connected, then trusts the graph of groups the answer supplies and checks only that it has no cycle. The second checks that every vertex is in one group and that the graph of groups, built from the arrows, has no cycle, and skips the check that each group is strongly connected. For each, find a wrong grouping it accepts.
Then: Say what every wrong grouping each one accepts has in common.
Exercise 24 · middling · ~15 min
Add one link to the graph of Exercise 12, between two vertices not yet linked, so that no bridge is left.
Then: Say which links work, all of them, and why.
Exercise 25 · middling · ~10 min
Eight items a to h start alone, with the union rules of Exercise 15. Give a sequence of unions after which some item sits three links below its root.
Then: Say what every such sequence has in common.
5.11.4 Which idea do you reach for
These exercises describe a situation, most of them far from graphs, and ask which of the six ideas of Table 5.7 you would use. Each has four options: pick the one you would reach for first.
Exercise 26 · gentle · ~5 min
A kitchen cooks a banquet of forty dishes. Some dishes need a sauce or a stock that another dish produces, and one cook can work on one dish at a time. In what order should the cook start them?
- contraction
- topological order
- monotone fixed point
- rewrite on read
Exercise 27 · middling · ~10 min
A power company wants every substation whose failure alone would black out some neighborhood, on a grid of a million substations, in one pass over the grid.
- merge smaller into larger
- topological order
- DFS timestamps and low-link
- rewrite on read
Exercise 28 · middling · ~10 min
A delivery planner works on a city where, inside each neighborhood, every street leads round to every other. It wants to plan between neighborhoods only, treating each one as a single stop, and still know which neighborhood can be reached from which.
- contraction
- monotone fixed point
- rewrite on read
- merge smaller into larger
Exercise 29 · middling · ~10 min
A security tool works out, for each variable of a program, every untrusted input whose data could flow into it. Data flows round loops, and a variable’s list of inputs only grows.
- topological order
- monotone fixed point
- DFS timestamps and low-link
- contraction
Exercise 30 · middling · ~10 min
A chain of shops merges with other chains again and again. Each merge relabels every shop of one chain with the other chain’s name, and relabeling a shop costs a letter to its staff. How do you keep the total number of letters small?
- monotone fixed point
- topological order
- merge smaller into larger
- contraction
Exercise 31 · middling · ~10 min
A file system lets a shortcut point to another shortcut, which points to another, and only the last points to the file. The same shortcuts are opened all day, and following a long chain is slow.
- rewrite on read
- contraction
- DFS timestamps and low-link
- monotone fixed point
5.11.5 The tests pass. What did they miss?
Code that fails its tests is easy to catch. The costly kind passes every test, because nobody wrote a test for the requirement it breaks.
Exercise 32 · middling · ~15 min
A university’s course planner orders courses so that every course comes after its prerequisites. Its tests pass: on a thousand random catalogues it returns every course once with every prerequisite earlier. After launch, two departments each list the other’s course as a prerequisite, and the planner prints a list of courses with no warning; students plan around the courses it left out without knowing they are missing. What requirement did the tests miss?
Then: Write the requirement as a sentence a test could check.
Exercise 33 · middling · ~15 min
A build tool draws an arrow from each module to every module that imports it, groups modules that import each other in circles, and then builds the groups by number, group 0 first. The grouping’s tests pass: on random graphs, two modules share a group exactly when each reaches the other, checked against a plain search. In use, builds fail because a group is built before a group it imports. What requirement did the tests miss?
Then: Write the test.
Exercise 34 · middling · ~15 min
An AI writes a union-find for a photo app that groups pictures of the same scene. Its tests pass: on fifty items and random unions, every answer to “joined?” matches a plain search over the links. Its union always hangs the first root under the second, and its lookup never shortens a path. In production, pictures arrive one by one, and each arrival calls union(the picture before, the new one). After a hundred thousand pictures, a single question takes a noticeable pause. What requirement did the tests miss?
Then: Write the test that would have caught it.
5.11.6 Fill in the contract
No options this time. The workload below is not one of the chapter’s, and the answer is not a name: it is a short answer to each of the contracts chapter’s six questions.
Exercise 35 · hard · ~40 min
A spreadsheet holds a hundred thousand cells, and a cell’s formula may read other cells. When someone edits a cell, every cell that depends on it, directly or through others, must show its new value before the next keystroke, and no cell may be computed from a value that is about to change. Someone sometimes writes a formula that reads itself through other cells. Work out the parts of a contract for this workload, in the order the contracts chapter works them out, one or two sentences each.
Then: Which part of your contract tells the spreadsheet what to show when formulas read each other in a circle, and why does the order alone not settle it?
5.11.7 Fix the code, the box, or the design?
Each item starts from code an AI wrote from one of the chapter’s design boxes, and something it did that looks wrong. Decide which of three things happened. The code breaks a promise in the box: fix the code. The code keeps the box but misses what you wanted: fix the box. The design keeps its promise, but its assumptions or its cost no longer fit the job: change the design. Say why.
Exercise 36 · middling · ~10 min
You give an AI the union-find design box and ask for the code. Its union finds both roots and links them by rank, but never asks whether the roots are the same. After union(a, b), union(b, a) and union(a, b) on four items, the root a has rank 3 and 2 items in its tree, and the group count says 1. Every lookup still answers correctly. Which of the three is it, and why?
Then: Name a test you would keep from the AI that catches it.
Exercise 37 · middling · ~10 min
An AI writes a course planner from the topological order box. On the graph of Exercise 1 it lists a, e, d, b, f, c, h, g. Every arrow points forward. The registrar complains that whenever several courses could come next, the list should take them alphabetically, and here it does not. Which of the three is it, and why?
Then: Rewrite the line of the box that has to change, say what the change costs, and give the answer the registrar expects.
Exercise 38 · middling · ~10 min
A social app keeps a union-find of its users, one union per friendship, and answers “are these two connected?”. On the links of Exercise 20, a and e unfriend each other. The app still says they are connected, though no chain of friendships joins them any more. Which of the three is it, and why?
Then: Name a design that fits, and say what it costs.
Exercise 39 · middling · ~10 min
An AI writes 2-SAT from the strong components box. On the clauses of Exercise 11, it answers x1 false, x2 true, x3 true, and (¬x2 or ¬x3) is false under it. Its tests checked only whether it said “no answer” at the right times. Which of the three is it, and why?
Then: Name the test you would keep from the AI.
5.11.8 Pieces that no single link failure splits
Exercise 40 · hardest in the chapter · ~90 min
You already have:
- the block walk and its bridges, printed in the chapter
- the block walk’s promise, in its box’s words, “A link or vertex is reported exactly when its failure alone splits the network”
- union-find, or any search that follows links
Write a procedure, as code or as precise steps, that splits the vertices of a connected network into its largest pieces that no single link failure can split, and joins those pieces into a tree, one line per bridge. Your answer must say how a piece is found, why two vertices in one piece stay joined after any one link fails, and why the pieces with the bridges form a tree.
Three checks tell you whether you got it right:
- On the graph of Figure 5.32, your pieces are exactly the groups a search finds once every bridge is deleted, and your tree has one line per bridge.
- A vertex where two cycles meet is one piece with both cycles, though it is two blocks.
- A doubled link puts its two vertices in one piece.
Stretch: Show that your procedure takes one look per vertex and per link, and that the pieces really are the largest: a link inside a piece lies on a cycle.
Put this somewhere you’ll see it in about a week, and when you do, answer from memory first, with no scrolling back and no AI. Getting it wrong and then looking is the point. Looking first isn’t.
What does Kahn’s method hand back when there is no order, and why is that evidence that a cycle exists?
In Algorithm T, what makes a person a leader, and who comes out with them?
Why does the graph of groups never have a cycle?
Name the three checks of a grouping you did not compute, and the lie each one catches.
What does a climb-back number measure on links that go both ways, and why does the walk skip the link it arrived by?
Union-find says two people are joined. What does that not tell you?
NoteAnswerThrough whom, and how many ways. It keeps no path, so it cannot say who connects them, and it says “joined” whether one link holds them together or ten. Whether a single failure would split them is a question for the block walk.
Pick one of the chapter’s design boxes and write it from memory. Say what it promises, its idea and invariants, and what its cost depends on. If it assumes anything, say what you would see if that broke. Then open the box and compare.
Whichever of those you couldn’t reconstruct is the one to reread, and only that one. If you got all seven, come back again in a month instead.
5.12 ★ Frontier map advanced
What follows is optional. It is a short tour of ideas just past the edge of this chapter. Skip it now if you’d rather move on, and come back later.
This chapter read a graph that holds still and asked about one failure at a time. Current work changes that in six ways, one per entry below.
- The arrows keep arriving.
- A guess about them is available.
- Many workers share the job.
- Links disappear as well as appear.
- Failures come in twos and threes.
- A trained model may do the job.
Each entry ends with a question you can now ask of any system that makes the same choice.
5.12.1 The chat keeps talking
Incremental cycle detection
A build system that is told about one new dependency at a time should not reorder everything from scratch. Incremental cycle detection keeps an order as arrows arrive and reports the moment an arrow would close a cycle. Abseil’s deadlock detector keeps one with Pearce and Kelly’s method [22]. OCaml’s build system Dune uses the method of Bender, Fineman, Gilbert and Tarjan [23], in a version whose correctness and cost were proved in Coq [24]. The proof covers the detector, not the build system around it. The proof assumes no arrow is added twice, and Dune’s own code has to check that itself. Which part of your tool does its proof cover?
5.12.2 A guess about tomorrow’s arrows
Algorithms with predictions
Builds repeat. Yesterday’s dependencies are a good guess at today’s, and a planner who has read last week’s chat can guess who will wait for whom this week. Recent work keeps strongly connected components as arrows arrive, guided by a prediction of the arrows still to come [25]. The vertices are known from the start, and the arrows come one at a time. Before any arrive, the structure reads the predicted arrows, which may be wrong, and works out parts of the answer in advance. A real arrow that was predicted then finds its work partly done. When the prediction is good, the structure is nearly as fast as one that knows every arrow in advance. It slows down smoothly as the prediction’s error grows. That error is set by the single worst-placed arrow, so one arrow that arrives far from where it was predicted costs as much as a bad guess everywhere. The authors also ran it on real graphs, and the speed-ups they measured followed what the theory predicted. The prediction is of the arrows, not of the groups. What does a wrong guess cost, and who notices?
5.12.3 More hands
Work in parallel
The graph of groups is also a schedule. Groups that do not reach each other can be built at the same time. Strong components themselves can now be found in parallel without random choices, with less work than first finding who reaches whom [26]. More workers cannot shorten a long chain of groups in which each waits for the one before. The chain’s length is what the contracts chapter calls the job’s span. Union-find shared by many workers has a harder problem. Two merges at once must still leave one correct forest. Which part of your plan can more workers not shorten?
5.12.4 Falling out
Links that disappear
Union-find never splits a group. Keeping “joined now?” correct while links are added and removed is fully dynamic connectivity. Bounds that hold on average over many updates have been known for decades. Recent work gives a polylogarithmic bound on every single update. It holds with high probability, even when the updates are chosen against the structure [27]. What does “joined now?” cost when links can go?
5.12.5 Other ways to cut
Two failures, and other decompositions
The block walk answers for one failure. A structure now answers “are these two vertices still connected if up to three vertices fail?” in constant time, built from the same kind of depth-first numbers [28]. Cut vertices themselves can now be kept up to date as links come and go, in about \(\log^2 n\) time per change, averaged over a run [29]. Other decompositions answer other questions. Expanders, which the flow chapter meets, split a graph into well-knit pieces with few links between them. The block-cut forest arranges a network as a tree of pieces that overlap in single vertices. A tree-decomposition lets the pieces overlap in more, and a graph’s treewidth says how small its largest piece can then be made [10, Secs. 12.3–12.4]. Which question needs which picture?
5.12.6 Can a machine just do it?
Learned graph algorithms
Small transformers trained on reachability learn to search by expanding what every vertex reaches all at once. They find it harder as the graphs grow, and more parameters do not fix it [30]. A second study says when a model learns the real method. A simplified transformer with \(L\) layers can decide connectivity by multiplying the graph’s table of links by itself. That works on graphs where every two connected vertices are at most \(3^L\) links apart. Trained mostly on graphs within that reach, it learns the method. Trained mostly on larger ones, it learns a shortcut based on how many links each vertex has [31]. Large models solve mazes by writing out a breadth-first search in text, step by step, at a cost of thousands of tokens per maze [32]. In each case the answer is a picture of a graph, and the chapter’s checks apply to it. A stuck set is checked arrow by arrow, a grouping by the three checks, and a reported bridge by deleting it and counting the pieces. But a model can check its picture and still have drawn the wrong graph. Who checks that the graph is the right one?
5.13 ★ Appendix: the second walk and the compact layout advanced
5.13.1 Kosaraju and Sharir’s two walks
Algorithm T finds the groups in one walk. Kosaraju and Sharir’s method uses two [3, Sec. 20.5], [33]. The first walk, along the arrows, records the order in which the vertices finish. The second walk goes against the arrows, starting from the vertex that finished last, and everything it reaches that has no group yet is one group. Then it starts again from the latest-finished vertex still without a group.
Why against the arrows? The vertex that finished last lies in a group that no other group points into. Walking along the arrows from it would wander into the groups below. Walking against them, it can only reach vertices that reach it, and the only ones without a group yet are its own group’s members. With that group set aside, the same holds again for the latest-finished vertex left.
5.13.2 The compact layout
Both walks read rows of arrows, one row per vertex, many times over. The library stores all the rows in one array, each vertex’s arrows next to each other, with a second array saying where each row starts. That is the compact layout [34, Sec. 2.3]. The reversed copy that check 2 and the second walk need is the same layout built from the arrows turned around. The compact layout is fast to read and cheap to build once, and adding an arrow means rebuilding it.
On a graph of a million vertices and four million arrows, the compact layout took 80 MB of memory and adjacency lists took 94 MB. Kahn’s method ran in 43 ms on the compact layout and in 85 ms on the lists. Adding one arrow to the compact layout means building it again, which took 0.19 s. Adding one arrow to a list took a few nanoseconds.
5.14 ★ Appendix: taking a merge back advanced
Some uses of union-find try a merge and then change their minds, like the type checker of Transfer 5 or a search that backtracks. Taking a merge back is easy if the forest never rewrites itself. Keep the rank rule and drop path compression. Then a merge changes one parent and perhaps one rank. A log of those changes lets the last call be undone exactly [35]. It holds one entry per union call. The entry is empty when nothing merged. A lookup then costs up to \(\log_2 n\) links every time, since nothing shortens the paths. With compression the log would have to record every pointer each lookup rewrote, and the nearly constant bound no longer survives rollbacks on its own.
src/build.h (class Plan, queue ready_).” https://github.com/ninja-build/ninja/blob/v1.13.2/src/build.h, 2025.Lib/graphlib.py (TopologicalSorter).” https://github.com/python/cpython/blob/v3.15.0/Lib/graphlib.py, 2026.src/Lean/Util/SCC.lean and src/Lean/Elab/PreDefinition/Main.lean (partitionPreDefs).” https://github.com/leanprover/lean4/blob/v4.35.0/src/Lean/Util/SCC.lean, 2026.llvm/include/llvm/Analysis/CGSCCPassManager.h and llvm/include/llvm/Transforms/IPO/Inliner.h.” https://github.com/llvm/llvm-project/blob/llvmorg-23.1.3/llvm/include/llvm/Analysis/CGSCCPassManager.h, 2026.compiler/rustc_infer/src/infer/type_variable.rs (table eq_relations, built on the ena crate).” https://github.com/rust-lang/rust/blob/1.99.1/compiler/rustc_infer/src/infer/type_variable.rs, 2026.The rounds and numbers come from one run on plans of 100,000 tasks each. The chain length and the knot’s size are the AI’s own and come from the plans it practiced on. The same AI wrote both rounds, given only each round’s brief. The briefs, the candidates and the script that judges them are in
scripts/design_run_graphs/in the book’s repository.↩︎