Graph::UnionFind(3pm) User Contributed Perl Documentation Graph::UnionFind(3pm)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.
perl v5.10.0 2008-11-27 Graph::UnionFind(3pm)
Check Out this Related Man Page
Graph::Traversal(3pm) User Contributed Perl Documentation Graph::Traversal(3pm)NAME
Graph::Traversal - traverse graphs
SYNOPSIS
Don't use Graph::Traversal directly, use Graph::Traversal::DFS or Graph::Traversal::BFS instead.
use Graph;
my $g = Graph->new;
$g->add_edge(...);
use Graph::Traversal::...;
my $t = Graph::Traversal::...->new(%opt);
$t->...
DESCRIPTION
You can control how the graph is traversed by the various callback parameters in the %opt. In the parameters descriptions below the $u and
$v are vertices, and the $self is the traversal object itself.
Callback parameters
The following callback parameters are available:
tree_edge
Called when traversing an edge that belongs to the traversal tree. Called with arguments ($u, $v, $self).
non_tree_edge
Called when an edge is met which either leads back to the traversal tree (either a "back_edge", a "down_edge", or a "cross_edge").
Called with arguments ($u, $v, $self).
pre_edge
Called for edges in preorder. Called with arguments ($u, $v, $self).
post_edge
Called for edges in postorder. Called with arguments ($u, $v, $self).
back_edge
Called for back edges. Called with arguments ($u, $v, $self).
down_edge
Called for down edges. Called with arguments ($u, $v, $self).
cross_edge
Called for cross edges. Called with arguments ($u, $v, $self).
pre
pre_vertex
Called for vertices in preorder. Called with arguments ($v, $self).
post
post_vertex
Called for vertices in postorder. Called with arguments ($v, $self).
first_root
Called when choosing the first root (start) vertex for traversal. Called with arguments ($self, $unseen) where $unseen is a hash
reference with the unseen vertices as keys.
next_root
Called when choosing the next root (after the first one) vertex for traversal (useful when the graph is not connected). Called with
arguments ($self, $unseen) where $unseen is a hash reference with the unseen vertices as keys. If you want only the first reachable
subgraph to be processed, set the next_root to "undef".
start
Identical to defining "first_root" and undefining "next_root".
next_alphabetic
Set this to true if you want the vertices to be processed in alphabetic order (and leave first_root/next_root undefined).
next_numeric
Set this to true if you want the vertices to be processed in numeric order (and leave first_root/next_root undefined).
next_successor
Called when choosing the next vertex to visit. Called with arguments ($self, $next) where $next is a hash reference with the possible
next vertices as keys. Use this to provide a custom ordering for choosing vertices, as opposed to "next_numeric" or "next_alphabetic".
The parameters "first_root" and "next_successor" have a 'hierarchy' of how they are determined: if they have been explicitly defined, use
that value. If not, use the value of "next_alphabetic", if that has been defined. If not, use the value of "next_numeric", if that has
been defined. If not, the next vertex to be visited is chose randomly.
Methods
The following methods are available:
unseen
Return the unseen vertices in random order.
seen
Return the seen vertices in random order.
seeing
Return the active fringe vertices in random order.
preorder
Return the vertices in preorder traversal order.
postorder
Return the vertices in postorder traversal order.
vertex_by_preorder
$v = $t->vertex_by_preorder($i)
Return the ith (0..$V-1) vertex by preorder.
preorder_by_vertex
$i = $t->preorder_by_vertex($v)
Return the preorder index (0..$V-1) by vertex.
vertex_by_postorder
$v = $t->vertex_by_postorder($i)
Return the ith (0..$V-1) vertex by postorder.
postorder_by_vertex
$i = $t->postorder_by_vertex($v)
Return the postorder index (0..$V-1) by vertex.
preorder_vertices
Return a hash with the vertices as the keys and their preorder indices as the values.
postorder_vertices
Return a hash with the vertices as the keys and their postorder indices as the values.
tree
Return the traversal tree as a graph.
has_state
$t->has_state('s')
Test whether the traversal has state 's' attached to it.
get_state
$t->get_state('s')
Get the state 's' attached to the traversal ("undef" if none).
set_state
$t->set_state('s', $s)
Set the state 's' attached to the traversal.
delete_state
$t->delete_state('s')
Delete the state 's' from the traversal.
Backward compatibility
The following parameters are for backward compatibility to Graph 0.2xx:
get_next_root
Like "next_root".
successor
Identical to having "tree_edge" both "non_tree_edge" defined to be the same.
unseen_successor
Like "tree_edge".
seen_successor
Like "seed_edge".
Special callbacks
If in a callback you call the special "terminate" method, the traversal is terminated, no more vertices are traversed.
SEE ALSO
Graph::Traversal::DFS, Graph::Traversal::BFS
AUTHOR AND COPYRIGHT
Jarkko Hietaniemi jhi@iki.fi
LICENSE
This module is licensed under the same terms as Perl itself.
perl v5.10.0 2008-11-28 Graph::Traversal(3pm)