6 ms·
The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the sa
by jtolmar 4y ago
The union-find data structure / algorithm is useful and a lot of fun.
The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.)
The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged with. To check if two elements are in the same set, check if they have the same parent. Without analyzing it, it sounds like you'll average findRoot() performance of O(log(n)), worst-case O(n).
There are a couple of simple optimizations you can do to this structure, the type of things that seem like they shouldn't end up affecting asymptotic runtime all that much. The first is that, whenever you find a root, you can re-parent all the nodes you visited on the way to that root, so they'll all be quicker to look up next time. The other is that you keep track of the size of sets, and always make the larger set be the parent of the smaller.
And neither of those actually do anything impressive alone, but if you use both, the algorithm suddenly becomes incredibly fast, with the slowest-growing (non-constant) complexity I've ever heard of: O(the inverse of the Ackermann function(n)). Or, for any reasonable N, O(4 or less).
- kizer 4y agoIf at some point you have a cycle, you can then reparent and remove the cycle, right? This structure in general then can encode transitive relations effectively? Something like “a and b …” “b and c …” “c and a …”.
- thaumasiotes 4y ago> If at some point you have a cycle, you can then reparent and remove the cycle, right? You'd never have a cycle. The way a cycle would theoretically arise would have to be joining something to its own child. But you don't naively join the two objects you're given - you find their root objects, and join those. If - as would be necessary for a cycle to form - they have the same root, you can return without doing anything. If we call unite(a,b) unite(b,c) unite(c,a) then we should end up with this structure: c / \ b a With parents on the right, the structure will be a-b after the first call and a-b-c after the second call. The reason we end up with a shallower tree after the third call is that when a is passed to unite, we call find on it and it gets reparented directly to c. Then, c (the representative for c) and c (the representative for a) are already related, so we don't adjust the structure further. > This structure in general then can encode transitive relations effectively? Well... no. This structure embodies the concept of an equivalence relation. You wouldn't be able to use it to express a general transitive relation, only a transitive relation that is also symmetric and reflexive.
- kizer 4y agoThanks!
- JamesUtah07 4y agoIs there a name for the data structure/algorithm?
- deleted 4y ago[deleted]
- lenocinor 4y agohttps://en.m.wikipedia.org/wiki/Disjoint-set_data_structure https://en.m.wikipedia.org/wiki/Disjoint-set_data_structure
- deleted 4y ago[deleted]
- whoisburbansky 4y agoIt's called union-find, but also disjoint-set sometimes. The process of reparenting nodes is called path compression, and the optimization of using the larger set of the two as the parent when merging is usually just called "union by rank." Any of those terms should give you more details upon search.
- mentater 4y agoWouldn't that be extremely useful and a polynomial solution for 3-SAT, which is NP complete?
- xigoi 4y agoHow is it a solution to 3-SAT?
- HelloNurse 4y agoSAT complexity results from blowing up a reasonable number of variables/clauses (very rarely equivalent to others) in the formula to an enormous number of variable assignments (too many to store, and having only three classes, formula true or false or not evaluated so far, that are not useful equivalencies). What disjoint sets are you thinking of tracking?
- jcranmer 4y agoI think I understand why you're confused here. To the extent that union-find is similar to SAT, it's similar to 2-SAT: the constraints you're reasoning about are defined only on pairs of elements, whereas 3-SAT is fundamentally reasoning about triplets (at least one of these three variables is true). Notably, 2-SAT is a variant of SAT that is polynomial in time, unlike 3-SAT.
- endgame 4y agoI have heard stories about annotating the edges with elements from a group rather than using unlabelled edges. Have you heard anything about that?
- eutectic 4y agoYou can efficiently maintain count/max/sum/hash/etc. for each component. It's occasionally useful.
- deleted 4y ago[deleted]
- zimpenfish 4y agoOh, huh, this is serendipitously handy because I need to be doing something like that this weekend (translating from Go to Rust - I already have a reparenting solution using hashes but hopefully this is easier / better.)
- kragen 4y agoMy writeup of union find is in https://dercuano.github.io/notes/incremental-union-find.html https://dercuano.github.io/notes/incremental-union-find.html. I did not in fact find a way to make it efficiently support incremental edge deletion, which is what I was looking for.
- thaumasiotes 4y ago> I did not in fact find a way to make it efficiently support incremental edge deletion, which is what I was looking for. I don't understand this goal. The interior connections aren't relevant to a union-find structure; ideally you have a bunch of trees of depth 2 (assuming the root is at depth 1), but the internal structure could be anything. That fact immediately means that the consequence of removing an edge is not well-defined - it would separate the two objects joined by the edge, and it would also randomly divide the original connected set into two connected sets, each containing one of those two objects. Which object each "third party" object ended up being associated with would be an artifact of the interior structure of the union-find, which is not known and is constantly subject to change as you use the union-find. If all you want is to be able to remove a single object from a connected set, on the assumption that your union-find always has the ideal flat structure, that's very easy to do - call find on the object you want to remove, which will link it directly to the root of its structure, and then erase that link.
- kragen 4y agoUnion find takes as input some undirected graph <N, E> and internally constructs (and progressively mutates) a directed graph <N, E'> which it uses to efficiently answer queries about whether two nodes n₁, n₂ ∈ N are in the same connected component of <N, E>. It additionally supports incrementally adding edges to E. My quest was to find a way to incrementally delete edges from E, not E'. You're talking about deleting edges from E', which I agree is not generally a useful thing to do. For example, your N might be the cells of a maze map, and your E might be the connections between adjacent cells that are not separated by a wall. In that case you can tear down a wall and add a corresponding edge to E. But it would be nice in some cases to rebuild a wall, which might separate two previously connected parts of the maze. I was looking for an efficient way to handle that, but I didn't find one.
- baby 4y agoWe use it to wire different outputs and inputs to gates in a zero-knowledge proof circuit!
- hexomancer 4y agoI have always wanted to really understand this data structure. Sure, I can follow the analysis with the potential functions and all, but I never really understood how Tarjan came up with the functions in the first place. Does anybody have a resource which intuitively explains the analysis?
- hashingroll 4y agoThis might a long read but it is well-written reader-friendly analysis of Tarjan's proof with chain of reasoning. https://codeforces.com/blog/entry/98275 https://codeforces.com/blog/entry/98275
- simonlindholm 4y agoHere's a writeup I made a while ago: https://www.overleaf.com/read/hjbshsqmjwpg https://www.overleaf.com/read/hjbshsqmjwpg
- sn9 4y agoRobert Sedgewick has a great explanation in his Algorithms book. He has gorgeous diagrams alongside his explanations.
- hexomancer 4y agoIs it in an old edition? I just downloaded an extremely legitimate version of Algorithms 4th edition but it has no section on union data structure.
- sn9 4y agoIt should be in Chapter 1 Section 5 of the 4th edition. It's even in the table of contents.
- hexomancer 4y agoSorry, my bad. I searched for the word "disjoint" expecting it to be prominent in this section but somehow this word only appears 3 times in this book non of which are in this section! Anyway, while the figures in this work were indeed gorgeous, it was not what I was looking for. It did not even contain a non-intuitive analysis of the inverse ackermann complexity, much less an intuitive one!
- rag-hav 4y agoI wrote a beginner's guide on this topic a while ago https://medium.com/nybles/efficient-operations-on-disjoint-sets-354814df6f3a https://medium.com/nybles/efficient-operations-on-disjoint-s...
- contificate 4y agoAgreed, union-find is great. My favourite usage of it in practice is for solving first-order (syntactic) unification problems. Destructive unification by means of rewriting unbound variables to be links to other elements is a very pretty solution - especially when you consider the earlier solutions such as that of Robinson's unification which, when applied, often involves somewhat error-prone compositions of substitutions (and is much slower). The fact that the forest of disjoint sets can be encoded in the program values you're manipulating is great (as opposed to, say, the array-based encoding often taught first): makes it very natural to union two elements, chase up the tree to the set representative, and only requires minor adjustment(s) to the representation of program values. Destructive unification by means of union-find for solving equality constraints (by rewriting unbound variables into links and, thus, implicitly rewriting terms - without explicit substitution) makes for very easy little unification algorithms that require minimal extension to the datatypes you intend to use and removing evidence of the union-find artefacts can be achieved in the most natural way: replace each link with its representative by using find(l) (a process known as "zonking" in the context of type inference algorithms). Basic demonstration of what I'm talking about (the incremental refinement of the inferred types is just basic union-find usage): https://streamable.com/1jyzg8 https://streamable.com/1jyzg8
- IanCal 4y agoThis sounds super useful thanks! I think I'll have something this can be used for, with individual claims of whether two elements are in the same set, then easily getting the largest set of equal items.
- MichaelMoser123 4y agoCan you give some examples where union-find is applied to great benefit?
- superjan 4y agoOne example is connected component analyis on images. In one linear scan of an image (2d or 3d) you can find all connected blobs in an image.
- fumblebee 4y agoA while back I had to perform an entity resolution task on several million entities. We arrived at a point in the algorithm where we had a long list of connected components by ids that needed to be reduced into a mutually independent set of components, e.g. ({112, 531, 25}, {25, 238, 39, 901}, {43, 111}, ...) After much head banging about working out way to do this that wouldn't lead to an out-of-memory error, we found the Disjoint Set Forest Data Structure and our prayers were answered. I was very grateful for it!
- BeetleB 4y agoExactly the same for me. We had a defect management system, and a defect can be connected to others as dupes. We'd have whole chains of dupes. We used union find to identify them.
- jobigoud 4y agoI used it to find and track islands of connected polygons in 3D meshes.
- clashmeifyoucan 4y agoa textbook example of an algorithm that works very well with union-find is the kruskal's algorithm to find the minimum weight spanning tree given a graph. Using union-find improves the time complexity of the algorithm from O(V²) to O(ElogV). This happens because kruskal's algorithm essentially selects the cheapest edge not already included in our spanning tree that won't cause a cycle. So union-find is able to speed up this potential cycle check which would otherwise be naively quadratic.
- anewpersonality 4y agoI remember getting this in an interview without ever coming across it.. basically, fuck union find.
- divan 4y agoI remember Ravelin shared their story of using it in card fraud detection code. Basically they managed to replace a full-fledged graph database with small piece of code using union-find in Go. Was a great talk. https://skillsmatter.com/skillscasts/8355-london-go-usergroup https://skillsmatter.com/skillscasts/8355-london-go-usergrou...