File MFSet.h

↰ Parent directory (ADS/mfset)

The MFSET of section 10.2, the union of disjoint sets: Mfset( n ) makes the n components {0} , … , {n - 1}, find( x ) gives the representative of the component of x, merge( x , y ) joins the components of x and y, if they are distinct.

Definition (ADS/mfset/MFSet.h)

Detailed Description

MFSet keeps the components as a forest, a vector of parents p, the roots with p[ x ] = x being the representatives (section 10.2.2): find() goes up to the root, merge() makes a root a child of the other. Two heuristics may be switched off, to study them:

  • the union by rank (section 10.2.3): rank[ r ] is the height of the tree of the root r, the lower tree goes under the higher one and the rank grows by one only when they are equal; by the Teorema 10.1 a tree of root r has at least :math:` 2^{rank[ r ]} ` nodes, so find() and merge() take O( log n );

  • the union by size, in place of the rank: size[ r ] is the number of nodes of the tree of the root r, and the smaller tree goes under the larger one (on a tie, the root of y under that of x). A node goes one level down only when its tree at least doubles, hence a tree of root r has height at most :math:` log_2 size[ r ] `, and the bound O( log n ) is the same;

  • the compression of the paths (section 10.2.4): find() makes each node on its way a child of the root. With both, a sequence of m operations, :math:` m geq n , takes :math: O( n + m alpha( m , n ) ) , where :math: alpha `, the inverse of the function of Ackermann, is at most 4 for every n and m that fit in a computer. Then rank[ r ] is an upper bound to the height (exercise 10.7).

find() is the iterative version in two passes, the root first and then the compression, with no stack (exercise 10.8). File ListMFSet.h has the realization on lists of section 10.2.1. components() gives the MFSET of the connected components of an unoriented graph, which can then follow new edges (section 10.2.5).

The contracts [see File Contract.h]: the elements are in [ 0 , n ), find() gives a root and after merge() x and y have the same root; the invariant is that the parents form a forest of count() trees, the rank growing towards the roots with the union by rank, and size[ r ] the number of nodes of the tree of each root r with the union by size. merge() of two elements already in the same component returns false and changes nothing, a relaxation of the precondition that they are in distinct components which some specifications state. The operations are defined in MFSet.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 10.2, https://algoritmicamente.it/materiali/libro/capitoli/cap10.pdf

    1. Galler, M. J. Fischer, An improved equivalence algorithm, Communications of the ACM 7(5), 301-303, 1964, doi:10.1145/364099.364331

    1. Tarjan, Efficiency of a good but not linear set union algorithm, Journal of the ACM 22(2), 215-225, 1975, doi:10.1145/321879.321884

    1. 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

Included By

Namespaces

Classes

Functions