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.