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($g, %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..$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.
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.
|