NAME
Graph::Traverse - A traverse() method for the Graph module.
SYNOPSIS
use Graph;
use Graph::Traverse;
my $g = Graph->new();
$g->add_path(qw(A B1 B2 C));
$g->add_path(qw(A D1 D2 C));
my $vertices = $g->traverse('A');
# $vertices now is ['B', 'C', 'D'] or some combination thereof
my $paths = $g->traverse('A', {hash => 1});
# $paths contains a hash like this:
# { 'B1' => { 'vertex' => 'B1',
# 'path' => ['A', 'B1'],
# 'weight' => 1 },
# 'B2' => { 'vertex' => 'B2',
# 'path' => ['A', 'B1', 'B2'],
# 'weight' => 2 },
# 'D1' => { 'vertex' => 'D1',
# 'path' => ['A', 'D1'],
# 'weight' => 1 },
# 'D2' => { 'vertex' => 'D2',
# 'path' => ['A', 'D1', 'D2'],
# 'weight' => 2 },
# 'C' => { 'vertex' => 'C',
# 'path' => ['A', 'D1', 'D2', 'C'],
# 'weight' => 3 }
# }METHODS
The only method resides in the Graph package (not Graph::Traverse) so that any descendant of Graph can call it.
traverse ( $start_vertex, [ \%opts ] );
traverse ( \@start_vertices , [ \%opts ] );
Traverses edges from the start vertex (or vertices) [either a single vertex's name, or an array of vertex names, may be passed], finding adjacent vertices using the 'next' function (by default, 'successors'), until either a maximum accumulated edge weight ('max' option, if given) is exceeded (by default using the 'weight' attribute, or specify an 'attribute'), or until a callback function ('cb') returns a nonzero value. By default, the return value is the list of vertices encountered in the search.
Note that as we traverse the graph, we may encounter the same vertex several times, but only the shortest path (lowest weight) will be retained.
The following options are available:
- hash
-
Use with a nonzero value to return a hash where keys are vertex names, and values are as follows:
- vertex
-
The current (found) vertex.
- path
-
The path from the starting vertex (or one of the starting vertices) to the current vertex.
- weight
-
The accumulated weight from the starting vertex. By default, each edge's 'weight' attribute is used; see options 'attribute' and 'vertex'.
- terminal
-
If the 'cb' option is provided, this is the value that the function returned at this vertex.
- attribute
-
The edge (or vertex) attribute to use as each edge's (vertex's) weight.
- max
-
A maximum weight, above which the traversal will terminate. If undefined, the traversal continues either until there are no more vertices to search (e.g., no further successors), or until the callback function (if any) returns a nonzero value.
- default
-
The default weight value for an edge (or vertex).
- vertex
-
If this option is true, accumulate the weight of each successive vertex, rather than the weights of the edges.
- cb
-
A callback function which is called for each discovered vertex. It is called as follows:
&$callback($self, $vertex, $weight, $opts))Where the arguments are: the Graph object itself; the name of the current vertex; the accumulated weight at that vertex; and the options hash as passed to traverse().
If the callback function returns a nonzero value, the successors (or whatever vertices might be returned by the 'next' function) beyond the current vertex are not searched. The callback's value at each vertex will be saved in the returned hash, if any.
Note that multiple paths to a given vertex may cause multiple callbacks with varying weights.
- all
-
Useful only when 'hash' is true and a 'cb' function is given. If 'all' is omitted, or is set to a nonzero value, the returned hash will include all vertices which were encountered in the traversal. If 'all' has a nonzero value, only the vertices for which the callback returned a nonzero value will be added to the hash.
- weights
-
Use option 'weights', with a nonzero value, to obtain a returned list of vertex=>weight_value.
- next
-
The name of a Graph method to find adjacent vertices. By default, 'successors' is used; alternate useful values include 'predecessors' and 'neighbors'.
AUTHOR
William Lindley <wlindley@wlindley.com>
COPYRIGHT
Copyright 2019, William Lindley
LICENSE
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.