1Graph::Traversal(3)   User Contributed Perl Documentation  Graph::Traversal(3)
2
3
4

NAME

6       Graph::Traversal - traverse graphs
7

SYNOPSIS

9       Don't use Graph::Traversal directly, use Graph::Traversal::DFS or
10       Graph::Traversal::BFS instead.
11
12           use Graph;
13           my $g = Graph->new;
14           $g->add_edge(...);
15           use Graph::Traversal::...;
16           my $t = Graph::Traversal::...->new($g, %opt);
17           $t->...
18

DESCRIPTION

20       You can control how the graph is traversed by the various callback
21       parameters in the %opt.  In the parameters descriptions below the $u
22       and $v are vertices, and the $self is the traversal object itself.
23
24   Callback parameters
25       The following callback parameters are available:
26
27       tree_edge
28           Called when traversing an edge that belongs to the traversal tree.
29           Called with arguments ($u, $v, $self).
30
31       non_tree_edge
32           Called when an edge is met which either leads back to the traversal
33           tree (either a "back_edge", a "down_edge", or a "cross_edge").
34           Called with arguments ($u, $v, $self).
35
36       pre_edge
37           Called for edges in preorder.  Called with arguments ($u, $v,
38           $self).
39
40       post_edge
41           Called for edges in postorder.  Called with arguments ($u, $v,
42           $self).
43
44       back_edge
45           Called for back edges.  Called with arguments ($u, $v, $self).
46
47       down_edge
48           Called for down edges.  Called with arguments ($u, $v, $self).
49
50       cross_edge
51           Called for cross edges.  Called with arguments ($u, $v, $self).
52
53       pre
54       pre_vertex
55           Called for vertices in preorder.  Called with arguments ($v,
56           $self).
57
58       post
59       post_vertex
60           Called for vertices in postorder.  Called with arguments ($v,
61           $self).
62
63       first_root
64           Called when choosing the first root (start) vertex for traversal.
65           Called with arguments ($self, $unseen) where $unseen is a hash
66           reference with the unseen vertices as keys.
67
68       next_root
69           Called when choosing the next root (after the first one) vertex for
70           traversal (useful when the graph is not connected).  Called with
71           arguments ($self, $unseen) where $unseen is a hash reference with
72           the unseen vertices as keys.  If you want only the first reachable
73           subgraph to be processed, set the next_root to "undef".
74
75       start
76           Identical to defining "first_root" and undefining "next_root".
77
78       next_alphabetic
79           Set this to true if you want the vertices to be processed in
80           alphabetic order (and leave first_root/next_root undefined).
81
82       next_numeric
83           Set this to true if you want the vertices to be processed in
84           numeric order (and leave first_root/next_root undefined).
85
86       next_successor
87           Called when choosing the next vertex to visit.  Called with
88           arguments ($self, $next) where $next is a hash reference with the
89           possible next vertices as keys.  Use this to provide a custom
90           ordering for choosing vertices, as opposed to "next_numeric" or
91           "next_alphabetic".
92
93       The parameters "first_root" and "next_successor" have a 'hierarchy' of
94       how they are determined: if they have been explicitly defined, use that
95       value.  If not, use the value of "next_alphabetic", if that has been
96       defined.  If not, use the value of "next_numeric", if that has been
97       defined.  If not, the next vertex to be visited is chosen randomly.
98
99   Methods
100       The following methods are available:
101
102       unseen
103           Return the unseen vertices in random order.
104
105       seen
106           Return the seen vertices in random order.
107
108       seeing
109           Return the active fringe vertices in random order.
110
111       preorder
112           Return the vertices in preorder traversal order.
113
114       postorder
115           Return the vertices in postorder traversal order.
116
117       vertex_by_preorder
118               $v = $t->vertex_by_preorder($i)
119
120           Return the ith (0..$V-1) vertex by preorder.
121
122       preorder_by_vertex
123               $i = $t->preorder_by_vertex($v)
124
125           Return the preorder index (0..$V-1) by vertex.
126
127       vertex_by_postorder
128               $v = $t->vertex_by_postorder($i)
129
130           Return the ith (0..$V-1) vertex by postorder.
131
132       postorder_by_vertex
133               $i = $t->postorder_by_vertex($v)
134
135           Return the postorder index (0..$V-1) by vertex.
136
137       preorder_vertices
138           Return a hash with the vertices as the keys and their preorder
139           indices as the values.
140
141       postorder_vertices
142           Return a hash with the vertices as the keys and their postorder
143           indices as the values.
144
145       tree
146           Return the traversal tree as a graph.
147
148       has_state
149               $t->has_state('s')
150
151           Test whether the traversal has state 's' attached to it.
152
153       get_state
154               $t->get_state('s')
155
156           Get the state 's' attached to the traversal ("undef" if none).
157
158       set_state
159               $t->set_state('s', $s)
160
161           Set the state 's' attached to the traversal.
162
163       delete_state
164               $t->delete_state('s')
165
166           Delete the state 's' from the traversal.
167
168   Special callbacks
169       If in a callback you call the special "terminate" method, the traversal
170       is terminated, no more vertices are traversed.
171

SEE ALSO

173       Graph::Traversal::DFS, Graph::Traversal::BFS
174
176       Jarkko Hietaniemi jhi@iki.fi
177

LICENSE

179       This module is licensed under the same terms as Perl itself.
180
181
182
183perl v5.34.0                      2022-01-21               Graph::Traversal(3)
Impressum