Disjoint set union

Imagine that after a snowfall all the streets of central Almaty are closed and are opened one at a time, in random order. While few are open, the city falls apart into islands: two or three crossings joined by a cleared street, with impassable ones all around. Each new street either merges two islands into one or closes a loop inside an island and changes nothing. The question asked again and again: are these two crossings on the same island? Below are 7909 crossings and 10,423 pieces of street from OpenStreetMap. The islands are coloured, the largest in the section's colour. Watch the graph: for a long time almost nothing happens, and then the city grows together in a jolt.

In random order the largest island stays tiny for a long time: with half the streets open it has 110 crossings, at 70 % 1574. And the next ten percent of streets swell it to 5630 crossings, more than two thirds of the city. It covers half the city at the 8040th street of 10,423, that is, at 77.1 %. If the main roads are opened first and then smaller streets, half the city is connected already at 45.2 % of the streets: the main roads are the skeleton on which the blocks hang. And if streets are opened from short to long, the jolt comes even later, at 83.5 %.

Such a sharp transition is called percolation, from the Latin for “seeping through”: this is how water finds a way through porous stone once enough pores are open. For the square lattice, where each node has four neighbours, the threshold is exactly half of the links; Harry Kesten proved this in 1980. A city crossing has 2.6 streets on average, one crossing in six is a dead end, and the threshold is higher. The whole curve on the graph comes from one pass: streets are added one at a time, and after each one the structure knows at once the number of islands and the size of the largest. How it works is the subject of this article.

The idea

Each set is a tree in which each element remembers only its parent, and the root is its own parent and serves as the name of the set. To find which set an element is in, climb the parents up to the root. To merge two sets, hang the root of one under the root of the other. To keep the trees low, the smaller tree is hung under the larger, and on every climb to the root the elements passed are rehung closer to it.

There are two operations: find(x) returns the root of the set containing x, and union(a, b) merges the sets of a and b. Elements are “in the same set” if their find is the same. The whole forest is one array parent: parent[x] is the parent of x, and for a root parent[x] = x. On the streets of Almaty an element is a crossing, a set is an island, and an opened street (a, b) is a call union(a, b). If find(a) and find(b) coincided before the merge, the street closed a loop.

Note what the structure cannot do. It does not remember which streets connect the crossings, and it cannot cut a set apart again. Breadth-first or depth-first search also finds the connected pieces of a graph, but anew each time, in O(V + E). Disjoint set union is good where links are only added and questions alternate with additions. An introduction to it through the electrification of Moravia is in the course chapter “Greed and electricity”.

Why a tree grows into a stick

If sets are merged any old way, the forest can degenerate. Take sixteen elements and merge (1, 0), (2, 1), …, (15, 14), each time hanging the old root under the newcomer: you get a chain, and find(0) goes through all fifteen steps. The Chain button below builds exactly that. Then switch the union to “by size” and press Chain again, or keep the chain and choose compression: tap element 0 twice, and find straightens the path.

There are two tricks against degeneration, and they complement each other.

Union by size. Keep the size of the tree at the root, and when merging hang the smaller tree under the root of the larger. A variant is union by rank, where an estimate of the height is kept instead of the size; their bounds are the same. On the chain from the example, by size gives a star: each new element goes right under the root.

Path compression. Since find has walked the path to the root anyway, rehang the elements passed closer to it. Full compression makes two passes: find the root, then hang everyone on the path onto it. Path halving manages with one pass: each element on the path is rehung onto its grandparent, parent[x] = parent[parent[x]], and the path shortens by about half. Both variants have the same bounds, and halving is simpler and needs no recursion.

The program dsu from the code section counts what the tricks cost on 4096 elements. On the chain without tricks the deepest element is at depth 4095, and find for each of the 4096 elements walks 8,386,560 steps in total, 2048 per call. Union by size turns the same chain into a star: 4095 steps for all the calls, one each. Path halving alone, without sizes, leaves a chain of length 4095, but the very first calls of find flatten it: all 4096 calls together take 10,111 steps. For union by size the worst order is different, a tournament: merge pairs, then pairs of pairs, and so on. The depth is then 12 = log₂ 4096, and that is the limit, as proved below.

Why it is so fast

Without union by size this is false; the chain from the example proves it. Path compression alone also gives a logarithm, but only on average over a sequence of operations: a single find may walk a long path, but afterwards the path becomes short, and the expensive call in effect pays for the cheapness of the following ones. Such accounting is called amortised.

Together the two tricks give a bound that long resisted proof. In 1973 John Hopcroft and Jeffrey Ullman showed that m operations on n elements cost O(m log* n), where log* n is how many times the binary logarithm must be taken to get down to one: for the number 2⁶⁵⁵³⁶, which has almost twenty thousand decimal digits, log* is five. In 1975 Robert Tarjan proved the exact bound O(m α(m, n)), where α is the inverse Ackermann function. The Ackermann function grows faster than any tower of powers, and its inverse more slowly than any iterated logarithm: for any number of elements that fits in the memory of any computer, α is at most 4. This bound cannot be improved: in 1989 Michael Fredman and Michael Saks proved that any structure for this problem spends, in the worst case, at least on the order of α per operation on average, and this is not about the forest with parents but about any way of storing the sets.

Code

The class is two arrays and two operations. Path halving is one line in the find loop; no recursion is needed, and on a chain of hundreds of thousands of elements the program will not hit the stack depth limit. Besides the class, the program runs the experiment from the section above: it builds the forest with two orders of merging, a chain and a tournament, with and without the tricks, and counts the steps.

Note the array parent in the first example: element 7 has parent 6, not the root 4. A merge does not touch elements inside the trees, and path compression rehangs only those that find passed through. The forest is never “perfectly flat”, and it does not need to be: it is flat where it is walked.

And this is the first scene as a program: the real street graph, three orders of opening and the table from which the graph is drawn. The shuffle is the Fisher–Yates algorithm with its own generator, so the order of the streets is the same in Python, Go and the scene.

The last line of the output is a hint towards a neighbouring article. In the order “from short to long”, each street that merges two islands is an edge of the minimum spanning tree of the street graph, and the whole program is Kruskal's algorithm. The last such street, 3053 metres long, is the longest edge of this tree.

No deleting: turn time around

The structure has a fundamental limitation: what has been merged cannot be cut apart again. The root of one tree hangs under the root of another, and nobody remembered which street connected them. So the question “the city was cleared after a snowfall: when did the islands merge?” is answered at once, while the reverse one, “streets are closed one after another: when will the city fall apart?”, is not. Wind the graph in the scene back: each time it builds the forest anew from scratch, because it cannot undo a merge.

If the list of closures is known in advance, there is a way out: read it from the end. Start with the city in which everything that will be closed is already closed, and open the streets in reverse order. Each closure read backwards is a merge, and the answers to the questions also come out backwards; all that remains is to reverse them. This is a common technique for processing queries out of order, offline, and the problem about street closures is built on it. Its tests are the same Almaty: if streets are closed in random order, the city falls apart at the eighth closure already (there are many dead ends), and if all 2616 pieces of major roads are closed, 1472 separate parts remain. When closures arrive one at a time and must be answered at once, far more complex structures of dynamic connectivity are needed: the best known deterministic one, by Holm, de Lichtenberg and Thorup (2001), spends O(log² n) per change on average over a sequence.

There is also an intermediate option: undoing the last merges, like an undo button in an editor. If path compression is given up and only union by size kept, each merge changes two cells, the parent of one root and the size of the other, and these can be remembered on a stack and restored. The depth stays logarithmic by the theorem above. Offline algorithms that go over the time intervals during which each edge exists rest on such undos.

What it costs

Memory is two arrays of n numbers: the parent and the size (only roots need the size). On real data the count is even more modest than the bounds promise. Look at the last counter of the first scene: while the whole city is opened, find is called 20,846 times, twice per street, and in random order walks only 12,418 steps, 0.6 steps per call on average; in the other two orders almost the same. Most calls find the element right at the root or one step from it.

A typical problem is the connected pieces of a graph whose edges arrive as a stream. Compare with a traversal: breadth-first search finds the components in O(V + E), but after each new edge it would have to be run again, and on the 10,423 streets of Almaty that is ten thousand traversals of the city. Disjoint set union answers the same question after every street, and the whole graph in the scene costs one pass.

Where it is used

• The minimum spanning tree. Kruskal's algorithm goes over the edges from light to heavy and takes an edge if its ends have different find: exactly the program city with the order “shortest first”.
• Labelling regions in images. The function measure.label from scikit-image, which numbers the connected blobs in a picture, keeps the labels in an array forest; its source has both find_root and path compression. The problem about dark islands is the same on a photograph.
• Percolation physics. The Hoshen–Kopelman algorithm (1976) labels clusters on a lattice the same way, and the Newman–Ziff method (2000) adds links one at a time and gets the whole curve at once, like the graph in our scene.
• Compilers. This is where it all began: variables declared to share the same memory form equivalence classes, and the compiler needs to know these classes in full.
• Mazes. Randomised Kruskal: go over the walls between cells in random order and knock a wall down if the cells on its two sides are not yet connected. The result is a maze with exactly one path between any two cells.

Forty percent on Fortran declarations

In Fortran and similar languages of the sixties one could declare that two variables or two arrays occupy the same memory: the EQUIVALENCE statement. Declarations hook onto each other, A with B, B with C, and the compiler has to assemble equivalence classes from them and give each class a place in memory. In May 1964 Bernard Galler and Michael Fischer published the note “An improved equivalence algorithm” in Communications of the ACM. The algorithm was based on a tree structure and, as the abstract says, identified all the equivalence classes in one scan of the declarations, reducing computation time by 40 percent compared with a previously published method. This was the forest with parents.

After that the structure became a favourite proving ground of theory. Hopcroft and Ullman proved the bound via log* in 1973, Tarjan the exact bound via the inverse Ackermann function in 1975, and in 1979 Tarjan showed that a wide class of pointer algorithms cannot work faster. In 1984 Tarjan and Jan van Leeuwen analysed all the variants of compression, including halving. Independently of computer scientists, the physicists Joseph Hoshen and Raoul Kopelman devised the same technique in 1976 for counting clusters in percolation problems.

Problems

In the first problem dark patches on a photograph merge as the brightness threshold grows, and the islands must be counted after each step. In the second the streets of Almaty are not opened but closed, and time will have to be turned around.