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(%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:
27 tree_edge
29 Called when traversing an edge that belongs to the traversal tree.
30 Called with arguments ($u, $v, $self).
31 non_tree_edge
33 Called when an edge is met which either leads back to the traversal
34 tree (either a "back_edge", a "down_edge", or a "cross_edge").
35 Called with arguments ($u, $v, $self).
36 pre_edge
38 Called for edges in preorder. Called with arguments ($u, $v,
39 $self).
40 post_edge
42 Called for edges in postorder. Called with arguments ($u, $v,
43 $self).
44 back_edge
46 Called for back edges. Called with arguments ($u, $v, $self).
47 down_edge
49 Called for down edges. Called with arguments ($u, $v, $self).
50 cross_edge
52 Called for cross edges. Called with arguments ($u, $v, $self).
53 pre
55 pre_vertex
56 Called for vertices in preorder. Called with arguments ($v,
57 $self).
58 post
60 post_vertex
61 Called for vertices in postorder. Called with arguments ($v,
62 $self).
63 first_root
65 Called when choosing the first root (start) vertex for traversal.
66 Called with arguments ($self, $unseen) where $unseen is a hash ref‐
67 erence with the unseen vertices as keys.
68 next_root
70 Called when choosing the next root (after the first one) vertex for
71 traversal (useful when the graph is not connected). Called with
72 arguments ($self, $unseen) where $unseen is a hash reference with
73 the unseen vertices as keys. If you want only the first reachable
74 subgraph to be processed, set the next_root to "undef".
75 start
77 Identical to defining "first_root" and undefining "next_root".
78 next_alphabetic
80 Set this to true if you want the vertices to be processed in alpha‐
81 betic order (and leave first_root/next_root undefined).
82 next_numeric
84 Set this to true if you want the vertices to be processed in
85 numeric order (and leave first_root/next_root undefined).
86 next_successor
88 Called when choosing the next vertex to visit. Called with argu‐
89 ments ($self, $next) where $next is a hash reference with the pos‐
90 sible next vertices as keys. Use this to provide a custom ordering
91 for choosing vertices, as opposed to "next_numeric" or "next_alpha‐
92 betic".
93 The parameters "first_root" and "next_successor" have a 'hierarchy' of
95 how they are determined: if they have been explicitly defined, use that
96 value. If not, use the value of "next_alphabetic", if that has been
97 defined. If not, use the value of "next_numeric", if that has been
98 defined. If not, the next vertex to be visited is chose randomly.
99 Methods
101 The following methods are available:
103 unseen
105 Return the unseen vertices in random order.
106 seen
108 Return the seen vertices in random order.
109 seeing
111 Return the active fringe vertices in random order.
112 preorder
114 Return the vertices in preorder traversal order.
115 postorder
117 Return the vertices in postorder traversal order.
118 vertex_by_preorder
120 $v = $t->vertex_by_preorder($i)
121 Return the ith (0..$V-1) vertex by preorder.
123 preorder_by_vertex
125 $i = $t->preorder_by_vertex($v)
126 Return the preorder index (0..$V-1) by vertex.
128 vertex_by_postorder
130 $v = $t->vertex_by_postorder($i)
131 Return the ith (0..$V-1) vertex by postorder.
133 postorder_by_vertex
135 $i = $t->postorder_by_vertex($v)
136 Return the postorder index (0..$V-1) by vertex.
138 preorder_vertices
140 Return a hash with the vertices as the keys and their preorder
141 indices as the values.
142 postorder_vertices
144 Return a hash with the vertices as the keys and their postorder
145 indices as the values.
146 tree
148 Return the traversal tree as a graph.
149 has_state
151 $t->has_state('s')
152 Test whether the traversal has state 's' attached to it.
154 get_state
156 $t->get_state('s')
157 Get the state 's' attached to the traversal ("undef" if none).
159 set_state
161 $t->set_state('s', $s)
162 Set the state 's' attached to the traversal.
164 delete_state
166 $t->delete_state('s')
167 Delete the state 's' from the traversal.
169 Backward compatibility
171 The following parameters are for backward compatibility to Graph 0.2xx:
173 get_next_root
175 Like "next_root".
176 successor
178 Identical to having "tree_edge" both "non_tree_edge" defined to be
179 the same.
180 unseen_successor
182 Like "tree_edge".
183 seen_successor
185 Like "seed_edge".
186 Special callbacks
188 If in a callback you call the special "terminate" method, the traversal
190 is terminated, no more vertices are traversed.
191
193 Graph::Traversal::DFS, Graph::Traversal::BFS
194
196 Jarkko Hietaniemi jhi@iki.fi
197
199 This module is licensed under the same terms as Perl itself.
200perl v5.8.8 2004-11-08 Graph::Traversal(3)