Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | package Graph::Traversal; |
2 | ||
3 | use strict; | |
4 | local $^W = 1; | |
5 | ||
6 | use Graph::Base; | |
7 | ||
8 | use vars qw(@ISA); | |
9 | @ISA = qw(Graph::Base); | |
10 | ||
11 | =head1 NAME | |
12 | ||
13 | Graph::Traversal - graph traversal | |
14 | ||
15 | =head1 SYNOPSIS | |
16 | ||
17 | use Graph::Traversal; | |
18 | ||
19 | =head1 DESCRIPTION | |
20 | ||
21 | =over 4 | |
22 | ||
23 | =cut | |
24 | ||
25 | =pod | |
26 | ||
27 | =item new | |
28 | ||
29 | $s = Graph::Traversal->new($G, %param) | |
30 | ||
31 | Returns a new graph search object for the graph $G | |
32 | and the parameters %param. | |
33 | ||
34 | Usually not used directly but instead via frontends like | |
35 | Graph::DFS for depth-first searching and Graph::BFS for | |
36 | breadth-first searching: | |
37 | ||
38 | $dfs = Graph::DFS->new($G, %param) | |
39 | $bfs = Graph::BFS->new($G, %param) | |
40 | ||
41 | I<%param documentation to be written> | |
42 | ||
43 | =cut | |
44 | ||
45 | sub new { | |
46 | my $class = shift; | |
47 | my $G = shift; | |
48 | ||
49 | my $S = { G => $G }; | |
50 | ||
51 | bless $S, $class; | |
52 | ||
53 | $S->reset(@_); | |
54 | ||
55 | return $S; | |
56 | } | |
57 | ||
58 | =pod | |
59 | ||
60 | =item reset | |
61 | ||
62 | $S->reset | |
63 | ||
64 | Resets a graph search object $S to its initial state. | |
65 | ||
66 | =cut | |
67 | ||
68 | sub reset { | |
69 | my $S = shift; | |
70 | my $G = $S->{ G }; | |
71 | ||
72 | @{ $S->{ pool } }{ $G->vertices } = ( ); | |
73 | $S->{ active_list } = [ ]; | |
74 | $S->{ root_list } = [ ]; | |
75 | $S->{ preorder_list } = [ ]; | |
76 | $S->{ postorder_list } = [ ]; | |
77 | $S->{ active_pool } = { }; | |
78 | $S->{ vertex_found } = { }; | |
79 | $S->{ vertex_root } = { }; | |
80 | $S->{ vertex_successors } = { }; | |
81 | $S->{ param } = { @_ }; | |
82 | $S->{ when } = 0; | |
83 | } | |
84 | ||
85 | # _get_next_root_vertex | |
86 | # | |
87 | # $o = $S->_get_next_root_vertex(\%param) | |
88 | # | |
89 | # (INTERNAL USE ONLY) | |
90 | # Returns a vertex hopefully suitable as a root vertex of a tree. | |
91 | # | |
92 | # If $param->{ get_next_root } exists, it will be used the determine | |
93 | # the root. If it is a code reference, the result of running it | |
94 | # with parameters ($S, %param) will be the next root. Otherwise | |
95 | # it is assumed to be the next root vertex as it is. | |
96 | # | |
97 | # Otherwise an unseen vertex having the maximal out-degree | |
98 | # will be selected. | |
99 | # | |
100 | sub _get_next_root_vertex { | |
101 | my $S = shift; | |
102 | my %param = ( %{ $S->{ param } }, @_ ? %{ $_[0] } : ( )); | |
103 | my $G = $S->{ G }; | |
104 | ||
105 | if ( exists $param{ get_next_root } ) { | |
106 | if ( ref $param{ get_next_root } eq 'CODE' ) { | |
107 | return $param{ get_next_root }->( $S, %param ); # Dynamic. | |
108 | } else { | |
109 | my $get_next_root = $param{ get_next_root }; # Static. | |
110 | ||
111 | # Use only once. | |
112 | delete $S->{ param }->{ get_next_root }; | |
113 | delete $_[0]->{ get_next_root } if @_; | |
114 | ||
115 | return $get_next_root; | |
116 | } | |
117 | } else { | |
118 | return $G->largest_out_degree( keys %{ $S->{ pool } } ); | |
119 | } | |
120 | } | |
121 | ||
122 | # _mark_vertex_found | |
123 | # | |
124 | # $S->_mark_vertex_found( $u ) | |
125 | # | |
126 | # (INTERNAL USE ONLY) | |
127 | # Marks the vertex $u as a new vertex in the search object $S. | |
128 | # | |
129 | sub _mark_vertex_found { | |
130 | my ( $S, $u ) = @_; | |
131 | ||
132 | $S->{ vertex_found }->{ $u } = $S->{ when }++; | |
133 | delete $S->{ pool }->{ $u }; | |
134 | } | |
135 | ||
136 | # _next_state | |
137 | # | |
138 | # $o = $S->_next_state(%param) | |
139 | # | |
140 | # (INTERNAL USE ONLY) | |
141 | # Returns a graph search object. | |
142 | # | |
143 | sub _next_state { | |
144 | my $S = shift; # The current state. | |
145 | ||
146 | my $G = $S->{ G }; # The current graph. | |
147 | my %param = ( %{ $S->{ param } }, @_); | |
148 | my ($u, $v); # The current vertex and its successor. | |
149 | my $return = 0; # Return when this becomes true. | |
150 | ||
151 | until ( $return ) { | |
152 | ||
153 | # Initialize our search when needed. | |
154 | # (Start up a new tree.) | |
155 | unless ( @{ $S->{ active_list } } ) { | |
156 | do { | |
157 | $u = $S->_get_next_root_vertex(\%param); | |
158 | return wantarray ? ( ) : $u unless defined $u; | |
159 | } while exists $S->{ vertex_found }->{ $u }; | |
160 | ||
161 | # A new root vertex found. | |
162 | push @{ $S->{ active_list } }, $u; | |
163 | $S->{ active_pool }->{ $u } = 1; | |
164 | push @{ $S->{ root_list } }, $u; | |
165 | $S->{ vertex_root }->{ $u } = $#{ $S->{ root_list } }; | |
166 | } | |
167 | ||
168 | # Get the current vertex. | |
169 | $u = $param{ current }->( $S ); | |
170 | return wantarray ? () : $u unless defined $u; | |
171 | ||
172 | # Record the vertex if necessary. | |
173 | unless ( exists $S->{ vertex_found }->{ $u } ) { | |
174 | $S->_mark_vertex_found( $u ); | |
175 | push @{ $S->{ preorder_list } }, $u; | |
176 | # Time to return? | |
177 | $return++ if $param{ return_next_preorder }; | |
178 | } | |
179 | ||
180 | # Initialized the list successors if necessary. | |
181 | $S->{ vertex_successors }->{ $u } = [ $G->successors( $u ) ] | |
182 | unless exists $S->{ vertex_successors }->{ $u }; | |
183 | ||
184 | # Get the next successor vertex. | |
185 | $v = shift @{ $S->{ vertex_successors }->{ $u } }; | |
186 | ||
187 | if ( defined $v ) { | |
188 | # Something to do for each successor? | |
189 | $param{ successor }->( $u, $v, $S ) | |
190 | if exists $param{ successor }; | |
191 | ||
192 | unless ( exists $S->{ vertex_found }->{ $v } ) { | |
193 | # An unseen successor. | |
194 | $S->_mark_vertex_found( $v ); | |
195 | push @{ $S->{ preorder_list } }, $v; | |
196 | $S->{ vertex_root }->{ $v } = $S->{ vertex_root }->{ $u }; | |
197 | push @{ $S->{ active_list } }, $v; | |
198 | $S->{ active_pool }->{ $v } = 1; | |
199 | ||
200 | # Something to for each unseen edge? | |
201 | # For multiedges, triggered only for the first edge. | |
202 | $param{ unseen_successor }->( $u, $v, $S ) | |
203 | if exists $param{ unseen_successor }; | |
204 | } else { | |
205 | # Something to do for each seen edge? | |
206 | # For multiedges, triggered for the 2nd, etc, edges. | |
207 | $param{ seen_successor }->( $u, $v, $S ) | |
208 | if exists $param{ seen_successor }; | |
209 | } | |
210 | ||
211 | # Time to return? | |
212 | $return++ if $param{ return_next_edge }; | |
213 | ||
214 | } elsif ( not exists $S->{ vertex_finished }->{ $u } ) { | |
215 | # Finish off with this vertex (we run out of descendants). | |
216 | $param{ finish }->( $S ); | |
217 | ||
218 | $S->{ vertex_finished }->{ $u } = $S->{ when }++; | |
219 | push @{ $S->{ postorder_list } }, $u; | |
220 | delete $S->{ active_pool }->{ $u }; | |
221 | ||
222 | # Time to return? | |
223 | $return++ if $param{ return_next_postorder }; | |
224 | } | |
225 | } | |
226 | ||
227 | # Return an edge if so asked. | |
228 | return ( $u, $v ) if $param{ return_next_edge }; | |
229 | ||
230 | # Return a vertex. | |
231 | return $u; | |
232 | } | |
233 | ||
234 | =pod | |
235 | ||
236 | =item next_preorder | |
237 | ||
238 | $v = $s->next_preorder | |
239 | ||
240 | Returns the next vertex in preorder of the graph | |
241 | encapsulated within the search object $s. | |
242 | ||
243 | =cut | |
244 | ||
245 | sub next_preorder { | |
246 | my $S = shift; | |
247 | ||
248 | $S->_next_state( return_next_preorder => 1, @_ ); | |
249 | } | |
250 | ||
251 | =cut | |
252 | ||
253 | =item next_postorder | |
254 | ||
255 | $v = $S->next_postorder | |
256 | ||
257 | Returns the next vertex in postorder of the graph | |
258 | encapsulated within the search object $S. | |
259 | ||
260 | =cut | |
261 | ||
262 | sub next_postorder { | |
263 | my $S = shift; | |
264 | ||
265 | $S->_next_state( return_next_postorder => 1, @_ ); | |
266 | } | |
267 | ||
268 | =pod | |
269 | ||
270 | =item next_edge | |
271 | ||
272 | ($u, $v) = $s->next_edge | |
273 | ||
274 | Returns the vertices of the next edge of the graph | |
275 | encapsulated within the search object $s. | |
276 | ||
277 | =cut | |
278 | ||
279 | sub next_edge { | |
280 | my $S = shift; | |
281 | ||
282 | $S->_next_state( return_next_edge => 1, @_ ); | |
283 | } | |
284 | ||
285 | =pod | |
286 | ||
287 | =item preorder | |
288 | ||
289 | @V = $S->preorder | |
290 | ||
291 | Returns all the vertices in preorder of the graph | |
292 | encapsulated within the search object $S. | |
293 | ||
294 | =cut | |
295 | ||
296 | sub preorder { | |
297 | my $S = shift; | |
298 | ||
299 | 1 while defined $S->next_preorder; # Process entire graph. | |
300 | ||
301 | return @{ $S->{ preorder_list } }; | |
302 | } | |
303 | ||
304 | =pod | |
305 | ||
306 | =item postorder | |
307 | ||
308 | @V = $S->postorder | |
309 | ||
310 | Returns all the vertices in postorder of the graph | |
311 | encapsulated within the search object $S. | |
312 | ||
313 | =cut | |
314 | ||
315 | sub postorder { | |
316 | my $S = shift; | |
317 | ||
318 | 1 while defined $S->next_postorder; # Process entire graph. | |
319 | ||
320 | return @{ $S->{ postorder_list } }; | |
321 | } | |
322 | ||
323 | =pod | |
324 | ||
325 | =item edges | |
326 | ||
327 | @V = $S->edges | |
328 | ||
329 | Returns all the edges of the graph | |
330 | encapsulated within the search object $S. | |
331 | ||
332 | =cut | |
333 | ||
334 | sub edges { | |
335 | my $S = shift; | |
336 | my (@E, $u, $v); | |
337 | ||
338 | push @E, $u, $v while ($u, $v) = $S->next_edge; | |
339 | ||
340 | return @E; | |
341 | } | |
342 | ||
343 | =pod | |
344 | ||
345 | =item roots | |
346 | ||
347 | @R = $S->roots | |
348 | ||
349 | Returns all the root vertices of the trees of | |
350 | the graph encapsulated within the search object $S. | |
351 | "The root vertices" is ambiguous: what really happens | |
352 | is that either the roots from the previous search made | |
353 | on the $s are returned; or a preorder search is done | |
354 | and the roots of this search are returned. | |
355 | ||
356 | =cut | |
357 | ||
358 | sub roots { | |
359 | my $S = shift; | |
360 | ||
361 | $S->preorder | |
362 | unless exists $S->{ preorder_list } and | |
363 | @{ $S->{ preorder_list } } == $S->{ G }->vertices; | |
364 | ||
365 | return @{ $S->{ root_list } }; | |
366 | } | |
367 | ||
368 | =pod | |
369 | ||
370 | =item _vertex_roots | |
371 | ||
372 | %R = $S->_vertex_roots | |
373 | ||
374 | Returns as a hash of ($vertex, index) pairs where index is an index | |
375 | into the vertex_root list of the traversal. | |
376 | ||
377 | "The root vertices" is ambiguous; see the documentation of the roots() | |
378 | method for more details. | |
379 | ||
380 | (This is the old vertex_roots().) | |
381 | ||
382 | =cut | |
383 | ||
384 | sub _vertex_roots { | |
385 | my $S = shift; | |
386 | my $G = $S->{ G }; | |
387 | ||
388 | $S->preorder | |
389 | unless exists $S->{ preorder_list } and | |
390 | @{ $S->{ preorder_list } } == $G->vertices; | |
391 | ||
392 | return | |
393 | map { ( $_, $S->{ vertex_root }->{ $_ } ) } $G->vertices; | |
394 | } | |
395 | ||
396 | =pod | |
397 | ||
398 | =item vertex_roots | |
399 | ||
400 | %R = $S->vertex_roots | |
401 | ||
402 | Returns as a hash of ($vertex, $root) pairs all the vertices | |
403 | and the root vertices of their search trees of the graph | |
404 | encapsulated within the search object $S. | |
405 | ||
406 | "The root vertices" is ambiguous; see the documentation of | |
407 | the roots() method for more details. | |
408 | ||
409 | (See also _vertex_roots()). | |
410 | ||
411 | =cut | |
412 | ||
413 | sub vertex_roots { | |
414 | my $S = shift; | |
415 | my $G = $S->{ G }; | |
416 | ||
417 | $S->preorder | |
418 | unless exists $S->{ preorder_list } and | |
419 | @{ $S->{ preorder_list } } == $G->vertices; | |
420 | ||
421 | return | |
422 | map { ( $_, $S->{root_list}[$S->{ vertex_root }->{ $_ }] ) } | |
423 | $G->vertices; | |
424 | } | |
425 | ||
426 | # DELETE | |
427 | # | |
428 | # (INTERNAL USE ONLY) | |
429 | # The Destructor. | |
430 | # | |
431 | sub DELETE { | |
432 | my $S = shift; | |
433 | ||
434 | delete $S->{ G }; # Release the graph. | |
435 | } | |
436 | ||
437 | =pod | |
438 | ||
439 | =back | |
440 | ||
441 | =head1 COPYRIGHT | |
442 | ||
443 | Copyright 1999, O'Reilly & Associates. | |
444 | ||
445 | This code is distributed under the same copyright terms as Perl itself. | |
446 | ||
447 | =cut | |
448 | ||
449 | 1; |