-
-
10 Oct 2021 20:06:24 UTC
- Distribution: Graph
- Source (raw)
- Browse (raw)
- Changes
- How to Contribute
- Repository
- Issues
- Testers (241 / 0 / 0)
- Kwalitee
Bus factor: 2- 94.33% Coverage
- License: perl_5
- Perl: v5.6.0
- Activity
24 month- Tools
- Download (144.04KB)
- MetaCPAN Explorer
- Permissions
- Subscribe to distribution
- Permalinks
- This version
- Latest version
- Dependencies
- Heap
- List::Util
- Safe
- Scalar::Util
- Set::Object
- Storable
- and possibly others
- Reverse dependencies
- CPAN Testers List
- Dependency graph
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
, adown_edge
, or across_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 undefiningnext_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
ornext_alphabetic
.
The parameters
first_root
andnext_successor
have a 'hierarchy' of how they are determined: if they have been explicitly defined, use that value. If not, use the value ofnext_alphabetic
, if that has been defined. If not, use the value ofnext_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.
Module Install Instructions
To install Graph, copy and paste the appropriate command in to your terminal.
cpanm Graph
perl -MCPAN -e shell install Graph
For more information on module installation, please visit the detailed CPAN module installation guide.