Graph::Traversal (3)
Leading comments
Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) Standard preamble: ========================================================================
NAME
Graph::Traversal - traverse graphsSYNOPSIS
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->...
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".