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.