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($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 chosen 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.

   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.36.0                                       2023-10-31                              Graph::Traversal(3pm)