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 the vertices to the union-find.
$uf->union([$u, $v], [$w, $x], ...)
Add the edge u-v to the union-find. Also implicitly adds the vertices.
@partitions = $uf->find(@v)
For each given vertex, return the union-find partition it belongs to, or
undefif it has not been added.
$uf = Graph::UnionFind->new()
Return true of the vertices belong to the same union-find partition the vertex v belongs to, false otherwise.
Jarkko Hietaniemi email@example.com
This module is licensed under the same terms as Perl itself.