NAME

       Graph::UnionFind - union-find data structures

SYNOPSIS

           use Graph::UnionFind;
           my $uf = Graph::UnionFind->new;

           # Add the vertices to the data structure.
           $uf->add($u);
           $uf->add($v);

           # Join the partitions of the vertices.
           $uf->union( $u, $v );

           # Find the partitions the vertices belong to
           # in the union-find data structure.  If they
           # are equal, they are in the same partition.
           # If the vertex has not been seen,
           # undef is returned.
           my $pu = $uf->find( $u );
           my $pv = $uf->find( $v );
           $uf->same($u, $v) # Equal to $pu eq $pv.

           # Has the union-find seen this vertex?
           $uf->has( $v )

DESCRIPTION

       Union-find is a special data structure that can be used to track the partitioning of a set
       into subsets (a problem also known as disjoint sets).

       "Graph::UnionFind" is used for "connected_components" in Graph, "connected_component" in
       Graph, and "same_connected_components" in Graph if you specify a true "unionfind"
       parameter when you create an undirected graph.

       Union-find is one way: you cannot (easily) 'ununion' vertices once you have 'unioned'
       them. This is why Graph throws an exception if you try to delete edges from a union-find
       graph.

   API
       add
               $uf->add(@v)

           Add the vertices to the union-find.

       union
               $uf->union([$u, $v], [$w, $x], ...)

           Add the edge u-v to the union-find.  Also implicitly adds the vertices.

       find
               @partitions = $uf->find(@v)

           For each given vertex, return the union-find partition it belongs to, or "undef" if it
           has not been added.

       new
               $uf = Graph::UnionFind->new()

           The constructor.

       same
               $uf->same($u, $v)

           Return true of the vertices belong to the same union-find partition the vertex v
           belongs to, false otherwise.

AUTHOR AND COPYRIGHT

       Jarkko Hietaniemi jhi@iki.fi

LICENSE

       This module is licensed under the same terms as Perl itself.