### Graph::UnionFind (3)

#### Leading comments

Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) Standard preamble: ========================================================================

#### 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 "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.