Graph::UnionFind − union−find data structures
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 )
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.
|
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.
Jarkko Hietaniemi [email protected]
This module is licensed under the same terms as Perl itself.