1Graph::Traversal(3) User Contributed Perl Documentation Graph::Traversal(3)
2
6 Graph::Traversal - traverse graphs
7
9 Don't use Graph::Traversal directly, use Graph::Traversal::DFS or
10 Graph::Traversal::BFS instead.
11 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
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 Callback parameters
25 The following callback parameters are available:
26 tree_edge
28 Called when traversing an edge that belongs to the traversal tree.
29 Called with arguments ($u, $v, $self).
30 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 pre_edge
37 Called for edges in preorder. Called with arguments ($u, $v,
38 $self).
39 post_edge
41 Called for edges in postorder. Called with arguments ($u, $v,
42 $self).
43 back_edge
45 Called for back edges. Called with arguments ($u, $v, $self).
46 down_edge
48 Called for down edges. Called with arguments ($u, $v, $self).
49 cross_edge
51 Called for cross edges. Called with arguments ($u, $v, $self).
52 pre
54 pre_vertex
55 Called for vertices in preorder. Called with arguments ($v,
56 $self).
57 post
59 post_vertex
60 Called for vertices in postorder. Called with arguments ($v,
61 $self).
62 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 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 start
76 Identical to defining "first_root" and undefining "next_root".
77 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 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 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 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 chose randomly.
98 Methods
100 The following methods are available:
101 unseen
103 Return the unseen vertices in random order.
104 seen
106 Return the seen vertices in random order.
107 seeing
109 Return the active fringe vertices in random order.
110 preorder
112 Return the vertices in preorder traversal order.
113 postorder
115 Return the vertices in postorder traversal order.
116 vertex_by_preorder
118 $v = $t->vertex_by_preorder($i)
119 Return the ith (0..$V-1) vertex by preorder.
121 preorder_by_vertex
123 $i = $t->preorder_by_vertex($v)
124 Return the preorder index (0..$V-1) by vertex.
126 vertex_by_postorder
128 $v = $t->vertex_by_postorder($i)
129 Return the ith (0..$V-1) vertex by postorder.
131 postorder_by_vertex
133 $i = $t->postorder_by_vertex($v)
134 Return the postorder index (0..$V-1) by vertex.
136 preorder_vertices
138 Return a hash with the vertices as the keys and their preorder
139 indices as the values.
140 postorder_vertices
142 Return a hash with the vertices as the keys and their postorder
143 indices as the values.
144 tree
146 Return the traversal tree as a graph.
147 has_state
149 $t->has_state('s')
150 Test whether the traversal has state 's' attached to it.
152 get_state
154 $t->get_state('s')
155 Get the state 's' attached to the traversal ("undef" if none).
157 set_state
159 $t->set_state('s', $s)
160 Set the state 's' attached to the traversal.
162 delete_state
164 $t->delete_state('s')
165 Delete the state 's' from the traversal.
167 Backward compatibility
169 The following parameters are for backward compatibility to Graph 0.2xx:
170 get_next_root
172 Like "next_root".
173 successor
175 Identical to having "tree_edge" both "non_tree_edge" defined to be
176 the same.
177 unseen_successor
179 Like "tree_edge".
180 seen_successor
182 Like "seed_edge".
183 Special callbacks
185 If in a callback you call the special "terminate" method, the traversal
186 is terminated, no more vertices are traversed.
187
189 Graph::Traversal::DFS, Graph::Traversal::BFS
190
192 Jarkko Hietaniemi jhi@iki.fi
193
195 This module is licensed under the same terms as Perl itself.
196perl v5.28.0 2015-09-22 Graph::Traversal(3)