Graph::Traversal  traverse graphs

Graph::Traversal  traverse graphs
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>...
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.
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.
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..$V1) vertex by preorder.
 preorder_by_vertex

$i = $t>preorder_by_vertex($v)

Return the preorder index (0..$V1) by vertex.
 vertex_by_postorder

$v = $t>vertex_by_postorder($i)

Return the ith (0..$V1) vertex by postorder.
 postorder_by_vertex

$i = $t>postorder_by_vertex($v)

Return the postorder index (0..$V1) 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.
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
.
If in a callback you call the special terminate
method,
the traversal is terminated, no more vertices are traversed.
the Graph::Traversal::DFS manpage, the Graph::Traversal::BFS manpage
Jarkko Hietaniemi jhi@iki.fi
This module is licensed under the same terms as Perl itself.
Graph::Traversal  traverse graphs
