

 
Manual Reference Pages  GRAPH::UNIONFIND (3)
.ds Aq ’
NAME
Graph::UnionFind  unionfind data structures
CONTENTS
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 unionfind 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 unionfind seen this vertex?
$uf>has( $v )
DESCRIPTION
Unionfind 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 unionfind 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 unionfind.

union

$uf>union($u, $v)
Add the edge uv to the unionfind. Also implicitly adds the vertices.

has

$uf>has($v)
Return true if the vertex v has been added to the unionfind, false otherwise.

find

$uf>find($v)
Return the unionfind 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 unionfind 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.20.3  GRAPH::UNIONFIND (3)  20081127 
Visit the GSP FreeBSD Man Page Interface. Output converted with manServer 1.07. 