table of contents
Graph::UnionFind(3)  User Contributed Perl Documentation  Graph::UnionFind(3) 
NAME¶
Graph::UnionFind  unionfind 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 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 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.
Unionfind 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 unionfind graph.
API¶
 add

$uf>add(@v)
Add the vertices to the unionfind.
 union

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

@partitions = $uf>find(@v)
For each given vertex, return the unionfind 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 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.
20240701  perl v5.40.0 