Graph::UnionFind(3) User Contributed Perl Documentation Graph::UnionFind(3)NAMEGraph::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 "union_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 "union_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 "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.
perl v5.14.0 2008-11-27 Graph::UnionFind(3)
