File RemUnionFind.h
↰ Parent directory (ADS/mfset)
The engineered MFSET, beyond the book [see File MFSet.h for the forest of section 10.2 with the union by rank and the compression of the paths]: the union of disjoint sets by the algorithm of Rem with splicing, which the experiments of Patwary, Blair and Manne found the fastest of the sequential algorithms of union and find.
Definition (ADS/mfset/RemUnionFind.h)
Detailed Description
UnionFind [see File UnionFind.h] is the other engineered MFSET, the union by size with the halving of the paths on signed integers; this one links by index, needs no sizes, and its merge() stops as soon as the two climbs meet.
The parents are a vector of 32-bit integers, and a parent is never smaller than its child, :math:` p[ x ] ge x ` for every x, the roots having :math:` p[ x ] = x ` (so that every path increases strictly to its root, and a climb ends after at most n steps): the union by index takes the place of the union by rank, with no array of ranks. merge( x , y ) climbs the two paths from x and y together, always from the one whose parent is smaller: if that one is a root it is linked under the parent of the other one and the two sets are one; otherwise its parent is replaced by the larger parent of the other one (the splicing), which only shortens its path, and the climb goes on from its old parent. When the two climbs reach the same parent, x and y were in the same set. The climb stops as soon as the sets are joined, often well below the roots, and each step both compresses and moves on, so that the two finds and the link of the union by rank become one interleaved walk. find( x ) climbs with the halving of the path, each node on the way made a child of its grandparent, in one pass. The link by index is the naive link, which with the splicing or the halving takes :math:` O( m log_{1 + m / n} n ) ` time for m operations in the worst case (Tarjan and van Leeuwen), and :math:` O( m alpha( m , n ) ) ` expected time, the bound of the union by rank, when the elements are numbered in a random order (Goel, Khanna, Larkin and Tarjan).
The contracts [see File Contract.h]: the elements are in [ 0 , n ), n < :math:` 2^{32} `; find() gives a root and after merge() x and y have the same root; the invariant is that every parent is not smaller than its child and that the roots are count(), an O( n ) check at the level 3 on the sets of up to 4096 elements. The operations are defined in RemUnionFind.tpp.
Patwary, J. R. S. Blair, F. Manne, Experiments on union-find algorithms for the disjoint-set data structure, Proceedings of SEA 2010, LNCS 6049, 411-423, 2010, doi:10.1007/978-3-642-13193-6_35
Goel, S. Khanna, D. H. Larkin, R. E. Tarjan, Disjoint set union with randomized linking, Proceedings of SODA 2014, 1005-1017, 2014, doi:10.1137/1.9781611973402.75
Dijkstra, A Discipline of Programming, Prentice-Hall, 1976 (the chapter on the algorithm of Rem for the equivalence classes)
Tarjan, J. van Leeuwen, Worst-case analysis of set union algorithms, Journal of the ACM 31(2), 245-281, 1984, doi:10.1145/62.2160
- Donato Meoli
Dipartimento di Informatica Universita’ di Pisa
by Donato Meoli
Includes
ADS/Contract.h(File Contract.h)ADS/mfset/impl/RemUnionFind.tppcstddefcstdintvector