{ if (navigator.userAgent.match('HeadlessChrome')) return ''; return md`The above is a visualization of the [union-find (or disjoint-set) data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) with "union-by-rank" and "path-compression" as implemented in [the "\`union-find\`" module](https://github.com/mikolalysenko/union-find) by Mikola Lysenko. This first section is an introduction to this data structure with a different flavor than the discussion on Wikipedia; feel free to [skip ahead](#chartSection) if you're already familiar with it! Here's a prototypical problem where organizing your data with a union-find data structure is helpful: suppose you're studying the dynamics of friend groups in a certain country where (1) friendships are only ever created, never broken, and (2) when two people become friends, their respective groups of friends become one. How might you keep track of the groups as they grow and merge together? How might you quickly determine whether two given people are in the same friend group? A first observation is that the friend groups are connected components of the "friendship graph", a [graph (or network)](https://en.wikipedia.org/wiki/Graph_%28discrete_mathematics%29) whose nodes (or vertices) are the individuals and whose links (or edges) are all friendships between them. So really, we're looking for algorithms to label and update connected components of graphs (so, if you prefer, you can think instead about [segmentation of 2D images or 3D scans](https://en.wikipedia.org/wiki/Image_segmentation), or [alias analysis in compiler theory](https://en.wikipedia.org/wiki/Alias_analysis), or [type inference](https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#Degrees_of_freedom_instantiating_the_rules), or any other situation where stuff gets linked to other stuff and you want to keep track of it as it happens.) Naïvely, you might create an [array](https://en.wikipedia.org/wiki/Array_data_structure) or [list](https://en.wikipedia.org/wiki/List_%28abstract_data_type%29) for each component and then join them when two people from different groups befriend each other. However, when the groups get large, merging arrays (to update the groups) is slow, as is searching lists (to determine what cluster a person is in). Enter the **union-find data structure**! To apply it, associate each person to an element called a "set" in the data structure. Then the "union" and "find" methods will efficiently answer all the questions above. How does it work? Each set has two nonnegative integers, a "parent" and a "rank". In the \`union-find\` module, these are stored in arrays called (confusingly) \`roots\` and (less confusingly) \`ranks\` so that, e.g., the parent of the *j*th set is \`roots[j-1]\` and its rank is \`ranks[j-1]\`. In the graphic above, each set corresponds to a randomly-colored disk, labeled by its index. Sets that are their own parents will be called "roots" in what follows (in ordinary font, not \`code font\`, to distinguish from the poorly-named parent array in this module). Roots are drawn with a special dashed outline. Non-root sets are connected by arrows to their parents. The visualization shows that the sets form [directed trees](https://en.wikipedia.org/wiki/Tree_%28graph_theory%29), rooted precisely at, well, the roots. **If you remember nothing else from this notebook -- remember that the union-find data structure is made up of trees!** These trees (and the underlying data structure) are constructed via the following three operations: - *Make a new set* this adds a new set to the data structure, by appending \`j-1\` to \`roots\` and \`0\` to \`ranks\`. In [code](https://github.com/mikolalysenko/union-find/blob/b0686c58f73e2c84cebdcb1b4f35f75eef168266/index.js#L23): \`\`\`js proto.makeSet = function() { var n = this.roots.length; this.roots.push(n); this.ranks.push(0); return n; } \`\`\` In other words, each new set is initialized as its own parent and with its rank is equal to zero.

The effect of a *Make* operation in the graphic is something from nothing:

- *Find* given an index of some set, this returns the index of the root of its tree. Thus if *Find*(i) = *Find*(j), i and j must be in the same tree. The search procedure is simple: start at the indexed set, and then repeatedly go to the parent; graphically, just "follow the arrows". The [code](https://github.com/mikolalysenko/union-find/blob/b0686c58f73e2c84cebdcb1b4f35f75eef168266/index.js#L30) is straightforward (though I protest again against the fact that the parent array is named \`roots\`): \`\`\`js proto.find = function(x) { var x0 = x var roots = this.roots; while(roots[x] !== x) { x = roots[x] } \`\`\` After the search completes at, say, set \`x\`, each set that was visited is then attached directly to \`x\`. This process, called "path-compression", flattens the tree and makes future *Find* operations faster. \`\`\`js while(roots[x0] !== x) { var y = roots[x0] roots[x0] = x x0 = y } return x; } \`\`\`

A *Find* operation on set 5 returns 6, but also results in both 1 and 5 being reattached to the root 6:

- *Link* (aka *Union*) given two indices, this links the two trees containing those two sets. *Find* operations are first performed to determine the two tree roots. In [code](https://github.com/mikolalysenko/union-find/blob/b0686c58f73e2c84cebdcb1b4f35f75eef168266/index.js#L44): \`\`\`js proto.link = function(x, y) { var xr = this.find(x) , yr = this.find(y); \`\`\` If they are the same, then they were already in the same tree, and no linking is required. \`\`\`js if(xr === yr) { return; } \`\`\` Otherwise, consider the ranks of the two roots. (This is where the "union-by-rank" part of the algorithm starts.) \`\`\`js var ranks = this.ranks , roots = this.roots , xd = ranks[xr] , yd = ranks[yr]; \`\`\` If they differ, the parent of the lower-rank root is set to the larger-rank root. (I remind you again that the \`roots\` array contains references to the parents, not the roots.) \`\`\`js if(xd < yd) { roots[xr] = yr; } else if(yd < xd) { roots[yr] = xr; \`\`\` If the ranks are equal, one of the sets has its rank incremented and then the other set is attached to it. \`\`\`js } else { roots[yr] = xr; ++ranks[xr]; } } \`\`\` Joining the trees at their roots ensures that the data structure always encodes a set of trees (cycles are never formed), and the union-by-rank procedure keeps the trees flat, improving efficiency.

This example *Link* operation was performed on sets 1 and 7 and results in the merging of the trees rooted at 0 and 2:

Now, go ahead and try out these operations using the controls [above](#svg)! Note that only the labels of the sets and the connections between them (i.e. the topology of the graph) in the graphic arise from the data structure discussed here; the force-driven layout is arbitrary and chosen just for aesthetic purposes. For an alternate view (with fewer possibly distracting features): **See also**: [David Galles's JS visualization of disjoint-sets](https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html). Since the algorithm has been engineered to make the trees very flat, the *Find* operations are quick. Similarly, the *Link* operations perform only two *Find* operations and modify \`roots\` and \`ranks\` at two or fewer indices. Indeed, it can be shown that the average time cost per operation is very nearly constant, independent of the total number of sets! For more technical details, see the references in [the Wikipedia article](https://en.wikipedia.org/wiki/Disjoint-set_data_structure). Thus, returning to our friendship application, using this data structure, we can both efficiently keep the friend clusters up-to-date and also quickly query whether two people are in the same cluster, no matter the number of people we wish to track. *A technical side note*: what if you want to keep track of connected components in graphs where both edge additions and deletions are allowed? For example, you might like to study friendship networks without the restriction (1) that friendships, once created are never broken. Well, union-find won't do (it's worth thinking about why!), but it turns out that there do exist fairly efficient algorithms. The keywords are "fully-dynamic graph connectivity algorithms", and one place to start reading might be [these slides by Christian Wulff-Nilsen](https://u.cs.biu.ac.il/~liamr/slides_dynconn.pdf). (I'd love to see a visualization of one of these algorithms!) `}