man Graph::UnionFind () - union-find data structures

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 known also as disjoint sets).

Graph::UnionFind() is used for Graph::connected_components(), Graph::connected_component(), and Graph::same_connected_components() if you specify a true CWunion_find parameter when you create an undirected graph.

Note that union-find is one way: you cannot (easily) 'ununion' vertices once you have 'unioned' them. This means that if you delete edges from a CWunion_find graph, you will get wrong results from the Graph::connected_components(), Graph::connected_component(), and Graph::same_connected_components().

API

add
    $uf->add($v)
Add the vertex v to the union-find.
union
    $uf->union($u, $v)
Add the edge u-v to the union-find. Also implicitly adds the vertices.
has
    $uf->has($v)
Return true if the vertex v has been added to the union-find, false otherwise.
find
    $uf->find($v)
Return the union-find partition the vertex v belongs to, or CWundef 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.