Graph::Traversal(3pm)

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. If not supplied, defaults to the same as "next_root".

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.

AUTHOR AND COPYRIGHT

Jarkko Hietaniemi [email protected]

LICENSE

This module is licensed under the same terms as Perl itself.