Mercurial > repos > deepakjadmin > mayatool3_test2

comparison lib/Graph/PathsTraversal.pm @ 0:4816e4a8ae95 draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author deepakjadmin
date Wed, 20 Jan 2016 09:23:18 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4816e4a8ae95
1 package Graph::PathsTraversal;
2 #
3 # $RCSfile: PathsTraversal.pm,v $
4 # $Date: 2015/02/28 20:49:06 $
5 # $Revision: 1.29 $
6 #
7 # Author: Manish Sud <msud@san.rr.com>
8 #
9 # Copyright (C) 2015 Manish Sud. All rights reserved.
10 #
11 # This file is part of MayaChemTools.
12 #
13 # MayaChemTools is free software; you can redistribute it and/or modify it under
14 # the terms of the GNU Lesser General Public License as published by the Free
15 # Software Foundation; either version 3 of the License, or (at your option) any
16 # later version.
17 #
18 # MayaChemTools is distributed in the hope that it will be useful, but without
19 # any warranty; without even the implied warranty of merchantability of fitness
20 # for a particular purpose. See the GNU Lesser General Public License for more
21 # details.
22 #
23 # You should have received a copy of the GNU Lesser General Public License
24 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
25 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
26 # Boston, MA, 02111-1307, USA.
27 #
28
29 use strict;
30 use Carp;
31 use Exporter;
32 use Graph;
33 use Graph::Path;
34
35 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
36
37 @ISA = qw(Exporter);
38 @EXPORT = qw();
39 @EXPORT_OK = qw();
40
41 %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]);
42
43 # Setup class variables...
44 my($ClassName);
45 _InitializeClass();
46
47 # Overload Perl functions...
48 use overload '""' => 'StringifyPathsTraversal';
49
50 # Class constructor...
51 sub new {
52 my($Class, $Graph) = @_;
53
54 # Initialize object...
55 my $This = {};
56 bless $This, ref($Class) || $Class;
57 $This->_InitializePathsTraversal($Graph);
58
59 return $This;
60 }
61
62 # Initialize object data...
63 sub _InitializePathsTraversal {
64 my($This, $Graph) = @_;
65
66 # Graph object...
67 $This->{Graph} = $Graph;
68
69 # Traversal mode: Vertex or Path
70 $This->{TraversalMode} = '';
71
72 # Traversal type: DFS, DFSWithLimit, BFS, BFSWithLimit...
73 $This->{TraversalType} = '';
74
75 # For finding root vertex and controlling search...
76 my(@VertexIDs);
77 @VertexIDs = $This->{Graph}->GetVertices();
78 %{$This->{VerticesToVisit}} = ();
79 @{$This->{VerticesToVisit}}{ @VertexIDs } = @VertexIDs;
80
81 # Root vertex of all visited vertices...
82 %{$This->{VerticesRoots}} = ();
83
84 # Visited vertices...
85 %{$This->{VisitedVertices}} = ();
86
87 # Finished vertices...
88 %{$This->{FinishedVertices}} = ();
89
90 # List of active vertices during DFS/BFS search...
91 @{$This->{ActiveVertices}} = ();
92
93 # List of ordered vertices traversed during DFS/BFS search...
94 @{$This->{Vertices}} = ();
95
96 # Vertex neighbors during traversal...
97 %{$This->{VerticesNeighbors}} = ();
98
99 # Vertices depth from root...
100 %{$This->{VerticesDepth}} = ();
101
102 # Predecessor of each vertex during vertex traversal. For root vertex, it's root itself...
103 %{$This->{VerticesPredecessors}} = ();
104
105 # Successors of each vertex during vertex traversal...
106 %{$This->{VerticesSuccessors}} = ();
107
108 # Vertices at different neighborhood levels during vertex traversal...
109 @{$This->{VerticesNeighborhoods}} = ();
110
111 # Vertices, along with their successors, at different neighborhood levels during vertex traversal...
112 @{$This->{VerticesNeighborhoodsWithSuccessors}} = ();
113
114 # Visited edges during Path TraversalMode...
115 %{$This->{VisitedEdges}} = ();
116 %{$This->{VisitedEdges}->{From}} = ();
117 %{$This->{VisitedEdges}->{To}} = ();
118
119 # Vertex path during Path TraversalMode...
120 %{$This->{VerticesPaths}} = ();
121
122 # Allow cycles in paths during VertexNeighborhood TraversalMode. By default, cycles are not allowed
123 # during vertex traversal: a vertex is only visited once during BFS search for neighborhoods. For
124 # neighborhood vertices search during successors identification, vertex cycles are explicity allowed
125 # to indentify all successors.
126 $This->{AllowVertexCycles} = 0;
127
128 # Allow cycles in paths during Path TraversalMode...
129 $This->{AllowPathCycles} = 1;
130
131 # Cycle closure vertices during Path TraversalMode...
132 %{$This->{CycleClosureVertices}} = ();
133
134 # Paths traversed during search...
135 @{$This->{Paths}} = ();
136
137 return $This;
138 }
139
140 # Initialize class ...
141 sub _InitializeClass {
142 #Class name...
143 $ClassName = __PACKAGE__;
144 }
145
146 # Perform a depth first search (DFS)...
147 #
148 sub PerformDepthFirstSearch {
149 my($This, $RootVertexID) = @_;
150
151 if (defined $RootVertexID) {
152 if (!$This->{Graph}->HasVertex($RootVertexID)) {
153 carp "Warning: ${ClassName}->PerformDepthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist...";
154 return undef;
155 }
156 }
157 return $This->_PerformVertexSearch("DFS", $RootVertexID);
158 }
159
160 # Perform a depth first search (DFS) with limit on depth...
161 #
162 sub PerformDepthFirstSearchWithLimit {
163 my($This, $DepthLimit, $RootVertexID) = @_;
164
165 if (!defined $DepthLimit) {
166 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Depth limit must be specified...";
167 return undef;
168 }
169 if ($DepthLimit < 0) {
170 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer...";
171 return undef;
172 }
173 if (defined $RootVertexID) {
174 if (!$This->{Graph}->HasVertex($RootVertexID)) {
175 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist...";
176 return undef;
177 }
178 }
179 return $This->_PerformVertexSearch("DFSWithLimit", $RootVertexID, $DepthLimit);
180 }
181
182 # Perform a breadth first search (BFS)...
183 #
184 sub PerformBreadthFirstSearch {
185 my($This, $RootVertexID) = @_;
186
187 if (defined $RootVertexID) {
188 if (!$This->{Graph}->HasVertex($RootVertexID)) {
189 carp "Warning: ${ClassName}->PerformBreadthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist...";
190 return undef;
191 }
192 }
193 return $This->_PerformVertexSearch("BFS", $RootVertexID);
194 }
195
196 # Perform a breadth first search (BFS) with limit...
197 #
198 sub PerformBreadthFirstSearchWithLimit {
199 my($This, $DepthLimit, $RootVertexID) = @_;
200
201 if (!defined $DepthLimit) {
202 carp "Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Depth limit must be specified...";
203 return undef;
204 }
205 if ($DepthLimit < 0) {
206 carp "Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer...";
207 return undef;
208 }
209 if (defined $RootVertexID) {
210 if (!$This->{Graph}->HasVertex($RootVertexID)) {
211 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist...";
212 return undef;
213 }
214 }
215 return $This->_PerformVertexSearch("BFSWithLimit", $RootVertexID, $DepthLimit);
216 }
217
218 # Perform appropriate vertex search...
219 #
220 sub _PerformVertexSearch {
221 my($This, $SearchType, $RootVertexID, $DepthLimit, $TargetVertexID) = @_;
222
223 # Setup search...
224 $This->{TraversalMode} = 'Vertex';
225 $This->{TraversalType} = $SearchType;
226
227 if (defined $RootVertexID) {
228 $This->{RootVertex} = $RootVertexID;
229 }
230 if (defined $DepthLimit) {
231 $This->{DepthLimit} = $DepthLimit;
232 }
233 if (defined $TargetVertexID) {
234 $This->{TargetVertex} = $TargetVertexID;
235 }
236
237 # Perform search...
238 return $This->_TraverseGraph();
239 }
240
241 # Perform DFS or BFS traversal with or without any limits...
242 #
243 sub _TraverseGraph {
244 my($This) = @_;
245 my($ProcessingVertices, $CurrentVertexID, $NeighborVertexID, $VertexID);
246
247 if ($This->{TraversalMode} !~ /^(Vertex|Path|VertexNeighborhood)$/i) {
248 return $This;
249 }
250
251 $ProcessingVertices = 1;
252
253 VERTICES: while ($ProcessingVertices) {
254 # Set root vertex...
255 if (!@{$This->{ActiveVertices}}) {
256 my($RootVertexID);
257
258 $RootVertexID = $This->_GetRootVertex();
259 if (!defined $RootVertexID) {
260 $ProcessingVertices = 0; next VERTICES;
261 }
262 $This->_ProcessVisitedVertex($RootVertexID, $RootVertexID);
263 }
264
265 # Get current active vertex...
266 $CurrentVertexID = $This->_GetActiveVertex();
267 if (!defined $CurrentVertexID) {
268 $ProcessingVertices = 0; next VERTICES;
269 }
270
271 # Get next available neighbor of current vertex...
272 #
273 $NeighborVertexID = $This->_GetNeighborVertex($CurrentVertexID);
274
275 # Process neighbor or current vertex...
276 if (defined $NeighborVertexID) {
277 $This->_ProcessVisitedVertex($NeighborVertexID, $CurrentVertexID);
278 }
279 else {
280 # Finished with all neighbors for current vertex...
281 $This->_ProcessFinishedVertex($CurrentVertexID);
282 }
283 }
284 return $This;
285 }
286
287 # Get root vertex to start the search...
288 #
289 # Notes:
290 # . User specification of root vertex forces traversal in a specific connected component
291 # of graph; To traverse find all connected components, perform traversal without specification of
292 # a root vertex.
293 #
294 sub _GetRootVertex {
295 my($This) = @_;
296 my($RootVertexID);
297
298 # Check for specified root vertex and constrain traversal to specific connected
299 # component by setting root limit...
300 if (exists $This->{RootVertex}) {
301 $RootVertexID = $This->{RootVertex};
302 delete $This->{RootVertex};
303 $This->{RootVertexSpecified} = 1;
304
305 return $RootVertexID;
306 }
307 # Traversal limited to connected component containing specified root vertex...
308 if (exists $This->{RootVertexSpecified}) {
309 return undef;
310 }
311
312 # Use first vertex in sorted available vertices list to get root vertex. Vertex
313 # with largest degree could also be used as root vertex. However, for all
314 # practical purposes, any arbitrary vertex can be used as root vertex to
315 # start search for another disconnected component of the graph.
316 #
317 my(@VerticesToVisit);
318
319 $RootVertexID = undef; @VerticesToVisit = ();
320 @VerticesToVisit = sort { $a <=> $b } keys %{$This->{VerticesToVisit}};
321 if (@VerticesToVisit) {
322 $RootVertexID = $VerticesToVisit[0];
323 }
324 return $RootVertexID;
325 }
326
327 # Get current or new active vertex for DFS/BFS traversals...
328 #
329 sub _GetActiveVertex {
330 my($This) = @_;
331 my($ActiveVertexID);
332
333 $ActiveVertexID = undef;
334 if ($This->{TraversalType} =~ /^(DFS|DFSWithLimit)$/i) {
335 # For DFS, it's last vertex in LIFO queue...
336 $ActiveVertexID = $This->{ActiveVertices}[-1];
337 }
338 elsif ($This->{TraversalType} =~ /^(BFS|BFSWithLimit)$/i) {
339 # For BFS, it's first vertex in FIFO queue...
340 $ActiveVertexID = $This->{ActiveVertices}[0];
341 }
342 return $ActiveVertexID;
343 }
344
345 # Get available neigbor of specified vertex...
346 #
347 sub _GetNeighborVertex {
348 my($This, $VertexID) = @_;
349
350 # Retrieve neighbors for vertex...
351 if (!exists $This->{VerticesNeighbors}{$VertexID}) {
352 @{$This->{VerticesNeighbors}{$VertexID}} = ();
353
354 if (exists $This->{DepthLimit}) {
355 # Only collect neighbors to visit below specified depth limit...
356 if ($This->{VerticesDepth}{$VertexID} < $This->{DepthLimit}) {
357 push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
358 }
359 else {
360 if (!exists $This->{RootVertexSpecified}) {
361 # Mark all other downstream neighbor vertices to be ignored from any further
362 # processing and avoid selection of a new root...
363 $This->_IgnoreDownstreamNeighbors($VertexID);
364 }
365 }
366 }
367 elsif (exists $This->{TargetVertex}) {
368 if ($VertexID != $This->{TargetVertex}) {
369 push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
370 }
371 }
372 else {
373 push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
374 }
375 }
376
377 if ($This->{TraversalMode} =~ /^Path$/i) {
378 # Get available neighbor for path search...
379 return $This->_GetNeighborVertexDuringPathTraversal($VertexID);
380 }
381 elsif ($This->{TraversalMode} =~ /^Vertex$/i) {
382 # Get unvisited neighbor for vertex search...
383 return $This->_GetNeighborVertexDuringVertexTraversal($VertexID);
384 }
385 elsif ($This->{TraversalMode} =~ /^VertexNeighborhood$/i) {
386 # Get available neighbor during vertex neighborhood search...
387 return $This->_GetNeighborVertexDuringVertexNeighborhoodTraversal($VertexID);
388 }
389 return undef;
390 }
391
392 # Get unvisited neighbor of specified vertex during vertex traversal...
393 #
394 sub _GetNeighborVertexDuringVertexTraversal {
395 my($This, $VertexID) = @_;
396 my($NeighborVertexID, $UnvisitedNeighborVertexID);
397
398 # Get unvisited neighbor...
399 $UnvisitedNeighborVertexID = undef;
400 NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
401 if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
402 $UnvisitedNeighborVertexID = $NeighborVertexID;
403 last NEIGHBOR;
404 }
405 }
406 return $UnvisitedNeighborVertexID;
407 }
408
409 # Get available neighbor of specified vertex during vertex neighborhood traversal...
410 #
411 sub _GetNeighborVertexDuringVertexNeighborhoodTraversal {
412 my($This, $VertexID) = @_;
413 my($NeighborVertexID, $UnvisitedNeighborVertexID);
414
415 # Get available neighbor...
416 $UnvisitedNeighborVertexID = undef;
417 NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
418 if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
419 $UnvisitedNeighborVertexID = $NeighborVertexID;
420 last NEIGHBOR;
421 }
422 # Look for any unvisited edge back to visited vertex...
423 if ($This->_IsVisitedEdge($VertexID, $NeighborVertexID) || $This->_IsVisitedEdge($NeighborVertexID, $VertexID)) {
424 next NEIGHBOR;
425 }
426 # Check its depth...
427 if (exists $This->{DepthLimit}) {
428 if (($This->{VerticesDepth}{$VertexID} + 1) > $This->{DepthLimit}) {
429 next NEIGHBOR;
430 }
431 }
432 # Its an edge that makes a cycle during BFS search...
433 if ($This->{AllowVertexCycles}) {
434 $This->{CycleClosureVertices}{$NeighborVertexID} = 1;
435 $UnvisitedNeighborVertexID = $NeighborVertexID;
436 last NEIGHBOR;
437 }
438 }
439 return $UnvisitedNeighborVertexID;
440 }
441
442 # Get available neighbor of specified vertex during path traversal...
443 #
444 sub _GetNeighborVertexDuringPathTraversal {
445 my($This, $VertexID) = @_;
446 my($NeighborVertexID, $UnvisitedNeighborVertexID);
447
448 # Get unvisited neighbor...
449 $UnvisitedNeighborVertexID = undef;
450 NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
451 if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
452 # An unvisited vertex...
453 $UnvisitedNeighborVertexID = $NeighborVertexID;
454 last NEIGHBOR;
455 }
456 # Look for any unvisited edge back to visited vertex...
457 if ($This->_IsVisitedEdge($VertexID, $NeighborVertexID) || $This->_IsVisitedEdge($NeighborVertexID, $VertexID)) {
458 next NEIGHBOR;
459 }
460 # Check its depth...
461 if (exists $This->{DepthLimit}) {
462 if (($This->{VerticesDepth}{$VertexID} + 1) >= $This->{DepthLimit}) {
463 next NEIGHBOR;
464 }
465 }
466
467 # It's the edge final edge of a cycle in case $NeighborVertexID is already in the path; otherwise, it's
468 # part of the path from a different direction in a cycle or a left over vertex during Limit search.
469 #
470 if ($This->_IsCycleClosureEdge($VertexID, $NeighborVertexID)) {
471 if ($This->{AllowPathCycles}) {
472 $This->{CycleClosureVertices}{$NeighborVertexID} = 1;
473 $UnvisitedNeighborVertexID = $NeighborVertexID;
474 last NEIGHBOR;
475 }
476 }
477 else {
478 $UnvisitedNeighborVertexID = $NeighborVertexID;
479 last NEIGHBOR;
480 }
481 }
482 return $UnvisitedNeighborVertexID;
483 }
484
485 # Process visited vertex...
486 #
487 sub _ProcessVisitedVertex {
488 my($This, $VertexID, $PredecessorVertexID) = @_;
489
490 if (!exists $This->{VisitedVertices}{$VertexID}) {
491 # Add it to active vertices list...
492 push @{$This->{ActiveVertices}}, $VertexID;
493
494 # Mark vertex as visited vertex and take it out from the list of vertices to visit...
495 $This->{VisitedVertices}{$VertexID} = 1;
496 delete $This->{VerticesToVisit}{$VertexID};
497 }
498
499 # Set up root vertex, predecessor vertex and distance from root...
500 if ($VertexID == $PredecessorVertexID) {
501 $This->{VerticesRoots}{$VertexID} = $VertexID;
502
503 $This->{VerticesPredecessors}{$VertexID} = $VertexID;
504 if (!exists $This->{VerticesSuccessors}{$VertexID}) {
505 @{$This->{VerticesSuccessors}{$VertexID}} = ();
506 }
507
508 $This->{VerticesDepth}{$VertexID} = 0;
509
510 if ($This->{TraversalMode} =~ /^Path$/i) {
511 $This->_ProcessVisitedPath($VertexID, $PredecessorVertexID);
512 }
513 }
514 else {
515 $This->{VerticesRoots}{$VertexID} = $This->{VerticesRoots}{$PredecessorVertexID};
516
517 $This->{VerticesPredecessors}{$VertexID} = $PredecessorVertexID;
518 if (!exists $This->{VerticesSuccessors}{$PredecessorVertexID}) {
519 @{$This->{VerticesSuccessors}{$PredecessorVertexID}} = ();
520 }
521 push @{$This->{VerticesSuccessors}{$PredecessorVertexID}}, $VertexID;
522
523 if (!exists $This->{VerticesDepth}{$VertexID}) {
524 $This->{VerticesDepth}{$VertexID} = $This->{VerticesDepth}{$PredecessorVertexID} + 1;
525 }
526
527 if ($This->{TraversalMode} =~ /^Path$/i) {
528 $This->_ProcessVisitedPath($VertexID, $PredecessorVertexID);
529 $This->_ProcessVisitedEdge($PredecessorVertexID, $VertexID);
530 }
531 elsif ($This->{TraversalMode} =~ /^VertexNeighborhood$/i) {
532 $This->_ProcessVisitedEdge($PredecessorVertexID, $VertexID);
533 }
534 }
535 return $This;
536 }
537
538 # Process visited path...
539 #
540 sub _ProcessVisitedPath {
541 my($This, $VertexID, $PredecessorVertexID) = @_;
542
543 # Initialize VerticesPath...
544 if (!exists $This->{VerticesPaths}{$VertexID}) {
545 @{$This->{VerticesPaths}{$VertexID}} = ();
546 }
547
548 if ($VertexID == $PredecessorVertexID) {
549 # Starting of a path from root...
550 push @{$This->{VerticesPaths}{$VertexID}}, $VertexID;
551 }
552 else {
553 # Setup path for a vertex using path information from predecessor vertex...
554 if (exists $This->{CycleClosureVertices}{$PredecessorVertexID}) {
555 # Start of a new path from predecessor vertex...
556 push @{$This->{VerticesPaths}{$VertexID}}, "${PredecessorVertexID}-${VertexID}";
557 }
558 else {
559 my($PredecessorVertexPath);
560 for $PredecessorVertexPath (@{$This->{VerticesPaths}{$PredecessorVertexID}}) {
561 push @{$This->{VerticesPaths}{$VertexID}}, "${PredecessorVertexPath}-${VertexID}";
562 }
563 }
564 }
565 return $This;
566 }
567
568 # Process visited edge...
569 #
570 sub _ProcessVisitedEdge {
571 my($This, $VertexID1, $VertexID2) = @_;
572
573 if (!exists $This->{VisitedEdges}->{From}->{$VertexID1}) {
574 %{$This->{VisitedEdges}->{From}->{$VertexID1}} = ();
575 }
576 $This->{VisitedEdges}->{From}->{$VertexID1}->{$VertexID2} = $VertexID2;
577
578 if (!exists $This->{VisitedEdges}->{To}->{$VertexID2}) {
579 %{$This->{VisitedEdges}->{To}->{$VertexID2}} = ();
580 }
581 $This->{VisitedEdges}->{To}->{$VertexID2}->{$VertexID1} = $VertexID1;
582
583 return $This;
584 }
585
586 # Finished processing active vertex...
587 #
588 sub _ProcessFinishedVertex {
589 my($This, $VertexID) = @_;
590
591 if (!exists $This->{FinishedVertices}{$VertexID}) {
592 $This->{FinishedVertices}{$VertexID} = $VertexID;
593 # Add vertex to list of vertices found by traversal...
594 push @{$This->{Vertices}}, $VertexID;
595 }
596
597 # Any active vertices left...
598 if (!@{$This->{ActiveVertices}}) {
599 return $This;
600 }
601
602 # Take it off active vertices list...
603 if ($This->{TraversalType} =~ /^(DFS|DFSWithLimit)$/i) {
604 # For DFS, it's last vertex in LIFO queue...
605 pop @{$This->{ActiveVertices}};
606 }
607 elsif ($This->{TraversalType} =~ /^(BFS|BFSWithLimit)$/i) {
608 # For BFS, it's first vertex in FIFO queue...
609 shift @{$This->{ActiveVertices}};
610 }
611 return $This;
612 }
613
614 # Mark all other downstream neighbor vertices to be ignored from any further
615 # processing...
616 #
617 sub _IgnoreDownstreamNeighbors {
618 my($This, $VertexID, $PredecessorVertexID) = @_;
619
620 if (exists $This->{VerticesToVisit}{$VertexID}) {
621 # Mark vertex as visited vertex and take it out from the list of vertices to visit...
622 $This->{VisitedVertices}{$VertexID} = 1;
623 delete $This->{VerticesToVisit}{$VertexID};
624
625 if (defined($PredecessorVertexID) && $This->{TraversalMode} =~ /^(Path|VertexNeighborhood)$/i) {
626 $This->_ProcessVisitedEdge($VertexID, $PredecessorVertexID);
627 }
628 }
629 my($NeighborVertexID, @NeighborsVertexIDs);
630
631 @NeighborsVertexIDs = ();
632 @NeighborsVertexIDs = $This->{Graph}->GetNeighbors($VertexID);
633 NEIGHBOR: for $NeighborVertexID (@NeighborsVertexIDs) {
634 if (!exists $This->{VerticesToVisit}{$NeighborVertexID}) {
635 # Avoid going back to predecessor vertex which has already been ignored...
636 next NEIGHBOR;
637 }
638 $This->_IgnoreDownstreamNeighbors($NeighborVertexID, $VertexID);
639 }
640 return $This;
641 }
642
643 # Is it a visited edge?
644 #
645 sub _IsVisitedEdge {
646 my($This, $VertexID1, $VertexID2) = @_;
647
648 if (exists $This->{VisitedEdges}->{From}->{$VertexID1}) {
649 if (exists $This->{VisitedEdges}->{From}->{$VertexID1}->{$VertexID2}) {
650 return 1;
651 }
652 }
653 elsif (exists $This->{VisitedEdges}->{To}->{$VertexID2}) {
654 if (exists $This->{VisitedEdges}->{To}->{$VertexID2}->{$VertexID1}) {
655 return 1;
656 }
657 }
658 return 0;
659 }
660
661 # Is it a cycle closure edge?
662 #
663 # Notes:
664 # . Presence of VertexID2 in DFS path traversed for VertexID1 make it a cycle
665 # closure edge...
666 #
667 sub _IsCycleClosureEdge {
668 my($This, $VertexID1, $VertexID2) = @_;
669
670 if (!exists $This->{VerticesPaths}{$VertexID1}) {
671 return 0;
672 }
673 my($Path);
674 for $Path (@{$This->{VerticesPaths}{$VertexID1}}) {
675 if (($Path =~ /-$VertexID2-/ || $Path =~ /^$VertexID2-/ || $Path =~ /-$VertexID2$/)) {
676 return 1;
677 }
678 }
679 return 0;
680 }
681
682 # Search paths starting from a specified vertex with no sharing of edges in paths traversed.
683 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
684 # completing the cycle.
685 #
686 sub PerformPathsSearch {
687 my($This, $StartVertexID, $AllowCycles) = @_;
688
689 # Make sure start vertex is defined...
690 if (!defined $StartVertexID) {
691 carp "Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Start vertex must be specified...";
692 return undef;
693 }
694
695 # Make sure start vertex is valid...
696 if (!$This->{Graph}->HasVertex($StartVertexID)) {
697 carp "Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist...";
698 return undef;
699 }
700
701 if (!defined $AllowCycles) {
702 $AllowCycles = 1;
703 }
704
705 # Perform paths search...
706 return $This->_PerformPathsSearch("AllLengths", $StartVertexID, $AllowCycles);
707 }
708
709 # Search paths starting from a specified vertex with length upto a specified length
710 # with no sharing of edges in paths traversed...
711 #
712 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
713 # completing the cycle.
714 #
715 sub PerformPathsSearchWithLengthUpto {
716 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
717
718 return $This->_PerformPathsSearchWithLength("LengthUpto", $StartVertexID, $Length, $AllowCycles);
719 }
720
721 # Search paths starting from a specified vertex with specified length
722 # with no sharing of edges in paths traversed...
723 #
724 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
725 # completing the cycle.
726 #
727 sub PerformPathsSearchWithLength {
728 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
729
730 return $This->_PerformPathsSearchWithLength("Length", $StartVertexID, $Length, $AllowCycles);
731 }
732
733
734 # Search paths starting from a specified vertex with length upto a specified length
735 # with no sharing of edges in paths traversed...
736 #
737 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
738 # completing the cycle.
739 #
740 sub _PerformPathsSearchWithLength {
741 my($This, $Mode, $StartVertexID, $Length, $AllowCycles) = @_;
742
743 # Make sure both start vertex and length are defined...
744 if (!defined $StartVertexID) {
745 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Start vertex must be specified...";
746 return undef;
747 }
748 if (!defined $Length) {
749 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Length must be specified...";
750 return undef;
751 }
752
753 if (!defined $AllowCycles) {
754 $AllowCycles = 1;
755 }
756
757 # Make sure both start vertex and length are valid...
758 if (!$This->{Graph}->HasVertex($StartVertexID)) {
759 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Vertex $StartVertexID doesn't exist...";
760 return undef;
761 }
762
763 if ($Length < 1) {
764 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1...";
765 return undef;
766 }
767
768 # Perform paths search...
769 return $This->_PerformPathsSearch($Mode, $StartVertexID, $AllowCycles, $Length);
770 }
771
772 # Search all paths starting from a specified vertex with sharing of edges in paths traversed...
773 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
774 # completing the cycle.
775 #
776 sub PerformAllPathsSearch {
777 my($This, $StartVertexID, $AllowCycles) = @_;
778
779 # Make sure start vertex is defined...
780 if (!defined $StartVertexID) {
781 carp "Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Start vertex must be specified...";
782 return undef;
783 }
784
785 # Make sure start vertex is valid...
786 if (!$This->{Graph}->HasVertex($StartVertexID)) {
787 carp "Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist...";
788 return undef;
789 }
790
791 if (!defined $AllowCycles) {
792 $AllowCycles = 1;
793 }
794
795 # Perform paths search...
796 return $This->_PerformAllPathsSearch("AllLengths", $StartVertexID, $AllowCycles);
797 }
798
799 # Search all paths starting from a specified vertex with length upto a specified length with sharing of
800 # edges in paths traversed.
801 #
802 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
803 # completing the cycle.
804 #
805 sub PerformAllPathsSearchWithLengthUpto {
806 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
807
808 return $This->_PerformAllPathsSearchWithLength("LengthUpto", $StartVertexID, $Length, $AllowCycles);
809 }
810
811 # Search all paths starting from a specified vertex with specified length with sharing of
812 # edges in paths traversed.
813 #
814 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
815 # completing the cycle.
816 #
817 sub PerformAllPathsSearchWithLength {
818 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
819
820 return $This->_PerformAllPathsSearchWithLength("Length", $StartVertexID, $Length, $AllowCycles);
821 }
822
823 # Search all paths starting from a specified vertex with length upto a specified length with sharing of
824 # edges in paths traversed.
825 #
826 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
827 # completing the cycle.
828 #
829 sub _PerformAllPathsSearchWithLength {
830 my($This, $Mode, $StartVertexID, $Length, $AllowCycles) = @_;
831
832 # Make sure both start vertex and length are defined...
833 if (!defined $StartVertexID) {
834 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Start vertex must be specified...";
835 return undef;
836 }
837 if (!defined $Length) {
838 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Length must be specified...";
839 return undef;
840 }
841
842 if (!defined $AllowCycles) {
843 $AllowCycles = 1;
844 }
845
846 # Make sure both start vertex and length are valid...
847 if (!$This->{Graph}->HasVertex($StartVertexID)) {
848 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Vertex $StartVertexID doesn't exist...";
849 return undef;
850 }
851
852 if ($Length < 1) {
853 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1...";
854 return undef;
855 }
856
857 # Perform paths search...
858 return $This->_PerformAllPathsSearch($Mode, $StartVertexID, $AllowCycles, $Length);
859 }
860
861 # Search paths between two vertices...
862 #
863 sub PerformPathsSearchBetween {
864 my($This, $StartVertexID, $EndVertexID) = @_;
865
866 # Make sure start and end vertices are defined...
867 if (!defined $StartVertexID) {
868 carp "Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: Start vertex must be specified...";
869 return undef;
870 }
871 if (!defined $EndVertexID) {
872 carp "Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: EndVertex vertex must be specified...";
873 return undef;
874 }
875 # Make sure start and end vertices are valid...
876 if (!$This->{Graph}->HasVertex($StartVertexID)) {
877 carp "Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $StartVertexID doesn't exist...";
878 return undef;
879 }
880 if (!$This->{Graph}->HasVertex($EndVertexID)) {
881 carp "Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $EndVertexID doesn't exist...";
882 return undef;
883 }
884
885 # Perform paths search...
886 return $This->_PerformPathsSearchBetween($StartVertexID, $EndVertexID);
887 }
888
889 # Search paths starting from root vertex with no sharing of edges...
890 #
891 # Notes:
892 # . Possible paths searche modes are: DFSPathsWithLimit, DFSPaths. And each
893 # of these modes supports any combination of two options: CommonEdges, Cycles.
894 # Default for CommonEdges - No; Cycles - No.
895 #
896 sub _PerformPathsSearch {
897 my($This, $Mode, $RootVertexID, $AllowCycles, $Length) = @_;
898
899 # Perform DFS path search...
900
901 $This->{TraversalMode} = 'Path';
902
903 if ($Mode =~ /^(LengthUpto|Length)$/i) {
904 my($DepthLimit);
905
906 $DepthLimit = $Length - 1;
907 $This->{TraversalType} = 'DFSWithLimit';
908 $This->{DepthLimit} = $DepthLimit;
909 }
910 else {
911 $This->{TraversalType} = 'DFS';
912 }
913 if (defined $RootVertexID) {
914 $This->{RootVertex} = $RootVertexID;
915 }
916
917 $This->{AllowPathCycles} = $AllowCycles;
918
919 # Perform search...
920 $This->_TraverseGraph();
921
922 # Make sure traversal did get the root vertex...
923 if (!exists $This->{VerticesDepth}{$RootVertexID}) {
924 return $This;
925 }
926 if ($Mode =~ /^Length$/i) {
927 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearchWithLength($Length);
928 }
929 else {
930 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearch();
931 }
932
933 return $This;
934 }
935
936 # Search all paths starting from root vertex with sharing of edges...
937 #
938 sub _PerformAllPathsSearch {
939 my($This, $Mode, $RootVertexID, $AllowCycles, $Length) = @_;
940
941 # Perform DFS path search...
942
943 $This->{TraversalMode} = 'AllPaths';
944
945 if ($Mode =~ /^(LengthUpto|Length)$/i) {
946 my($DepthLimit);
947
948 $DepthLimit = $Length - 1;
949 $This->{TraversalType} = 'DFSWithLimit';
950 $This->{DepthLimit} = $DepthLimit;
951 }
952 else {
953 $This->{TraversalType} = 'DFS';
954 }
955 $This->{RootVertex} = $RootVertexID;
956 $This->{AllowPathCycles} = $AllowCycles;
957
958 # Traverse all paths search using DFS search...
959 $This->_TraverseAllPathsInGraph($Mode, $Length);
960
961 return $This;
962 }
963
964 # Travese all paths in graph starting from a specified root vertex...
965 #
966 sub _TraverseAllPathsInGraph {
967 my($This, $Mode, $Length) = @_;
968
969 if ($This->{TraversalMode} !~ /^AllPaths$/i) {
970 return $This;
971 }
972 my($CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath);
973
974 $CurrentVertexID = $This->{RootVertex};
975 $PredecessorVertexID = $CurrentVertexID;
976 $CurrentDepth = 0;
977 $CurrentPath = "$CurrentVertexID";
978
979 $This->_TraverseAllPaths($CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath);
980
981 if ($Mode =~ /^Length$/i) {
982 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearchWithLength($Length);
983 }
984 else {
985 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearch();
986 }
987
988 return $This;
989 }
990
991 # Traverse and collect all paths recuresively..
992 #
993 sub _TraverseAllPaths {
994 my($This, $CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath) = @_;
995
996 # Save path traversed for current vertex..
997 if (!exists $This->{VerticesPaths}{$CurrentVertexID}) {
998 @{$This->{VerticesPaths}{$CurrentVertexID}} = ();
999 $This->{VerticesDepth}{$CurrentVertexID} = 0;
1000 }
1001 push @{$This->{VerticesPaths}{$CurrentVertexID}}, $CurrentPath;
1002 $This->{VerticesDepth}{$CurrentVertexID} = $CurrentDepth;
1003
1004 $CurrentDepth++;
1005 if (exists $This->{DepthLimit}) {
1006 if ($CurrentDepth > $This->{DepthLimit}) {
1007 # Nothing more to do...
1008 return $This;
1009 }
1010 }
1011 my($NeighborVertexID, $NewPath);
1012
1013 NEIGHBOR: for $NeighborVertexID ($This->{Graph}->GetNeighbors($CurrentVertexID)) {
1014 if ($NeighborVertexID == $PredecessorVertexID) {
1015 next NEIGHBOR;
1016 }
1017 if ($This->_IsVertexInTraversedPath($NeighborVertexID, $CurrentPath)) {
1018 # It's a cycle...
1019 if ($This->{AllowPathCycles}) {
1020 $NewPath = "${CurrentPath}-${NeighborVertexID}";
1021 if (!exists $This->{VerticesPaths}{$NeighborVertexID}) {
1022 @{$This->{VerticesPaths}{$NeighborVertexID}} = ();
1023 }
1024 push @{$This->{VerticesPaths}{$NeighborVertexID}}, $NewPath;
1025 }
1026 next NEIGHBOR;
1027 }
1028 $NewPath = "${CurrentPath}-${NeighborVertexID}";
1029 $This->_TraverseAllPaths($NeighborVertexID, $CurrentVertexID, $CurrentDepth, $NewPath);
1030 }
1031 return $This;
1032 }
1033
1034 # Is vertex already in traversed path?
1035 #
1036 sub _IsVertexInTraversedPath {
1037 my($This, $VertexID, $Path) = @_;
1038
1039 return ($Path =~ /-$VertexID-/ || $Path =~ /^$VertexID-/ || $Path =~ /-$VertexID$/) ? 1 : 0;
1040 }
1041
1042 # Collect all paths traversed during Path TraversalMode and sort 'em in
1043 # ascending order of lengths
1044 #
1045 sub _CollectPathsTraversedDuringPathsSearch {
1046 my($This) = @_;
1047 my($VertexID, @Paths, @SortedPaths);
1048
1049 @Paths = (); @SortedPaths = ();
1050
1051 # Create path objects from path vertex strings...
1052 for $VertexID (keys %{$This->{VerticesPaths}}) {
1053 push @Paths, map { new Graph::Path(split /-/, $_) } @{$This->{VerticesPaths}{$VertexID}};
1054 }
1055
1056 # Sort paths in ascending order of lengths...
1057 push @SortedPaths, sort { $a->GetLength() <=> $b->GetLength() } @Paths;
1058
1059 return @SortedPaths;
1060 }
1061
1062 # Collect paths traversed during Path TraversalMode with specific length...
1063 #
1064 sub _CollectPathsTraversedDuringPathsSearchWithLength {
1065 my($This, $Length) = @_;
1066 my($VertexID, $Depth, $PathString, @VertexIDs, @Paths);
1067
1068 @Paths = ();
1069 $Depth = $Length - 1;
1070
1071 # Create path objects from path vertex strings...
1072 VERTEXID: for $VertexID (keys %{$This->{VerticesPaths}}) {
1073 if ($This->{VerticesDepth}{$VertexID} != $Depth) {
1074 next VERTEXID;
1075 }
1076 # For vertices involved in cycles, the path might also contain some shorter paths. So check
1077 # the lengths before its collection...
1078 PATHSTRING: for $PathString (@{$This->{VerticesPaths}{$VertexID}}) {
1079 @VertexIDs = split /-/, $PathString;
1080 if ($Length != @VertexIDs) {
1081 next PATHSTRING;
1082 }
1083 push @Paths, new Graph::Path(@VertexIDs);
1084 }
1085 }
1086 return @Paths;
1087 }
1088
1089 # Collect paths traversed during Vertex TraversalMode...
1090 #
1091 sub _CollectPathsTraversedDuringVertexSearch {
1092 my($This, $RootVertexID) = @_;
1093 my($Depth, @Paths, @VerticesAtDepth);
1094 @Paths = ();
1095
1096 # Get vertices at specific depths...
1097 @VerticesAtDepth = ();
1098 @VerticesAtDepth = $This->_CollectVerticesAtSpecificDepths();
1099 if (!@VerticesAtDepth) {
1100 return @Paths;
1101 }
1102
1103 # Make sure search found only one root vertex and it corresponds to
1104 # what was specified...
1105 $Depth = 0;
1106 if ((@{$VerticesAtDepth[$Depth]} > 1) || ($VerticesAtDepth[$Depth][0] != $RootVertexID)) {
1107 carp "Warning: ${ClassName}->_PerformPathsSearch: No paths found: Root vertex, $VerticesAtDepth[$Depth][0], identified by paths traversal doen't match specified root vertex $RootVertexID...";
1108 return @Paths;
1109 }
1110
1111 # Setup root vertex at depth 0. And set its path...
1112 my($Path, $VertexID, $SuccessorVertexID, @VertexIDs, %PathAtVertex);
1113 %PathAtVertex = ();
1114 $PathAtVertex{$RootVertexID} = new Graph::Path($RootVertexID);
1115
1116 for $Depth (0 .. $#VerticesAtDepth) {
1117 # Go over all vertices at current depth...
1118 VERTEX: for $VertexID (@{$VerticesAtDepth[$Depth]}) {
1119 if (!exists $This->{VerticesSuccessors}{$VertexID}) {
1120 next VERTEX;
1121 }
1122 # Get vertices for current path...
1123 @VertexIDs = ();
1124 push @VertexIDs, $PathAtVertex{$VertexID}->GetVertices;
1125
1126 # Expand path to successor vertex found during traversal...
1127 for $SuccessorVertexID (@{$This->{VerticesSuccessors}{$VertexID}}) {
1128 $Path = new Graph::Path(@VertexIDs);
1129 $Path->AddVertex($SuccessorVertexID);
1130 $PathAtVertex{$SuccessorVertexID} = $Path;
1131 }
1132 }
1133 }
1134 # Sort paths in ascending order of lengths...
1135 push @Paths, sort { $a->GetLength() <=> $b->GetLength() } values %PathAtVertex;
1136
1137 return @Paths;
1138 }
1139
1140 # Collect vertices at specific depths. Depth values start from 0...
1141 #
1142 sub _CollectVerticesAtSpecificDepths {
1143 my($This) = @_;
1144 my($VertexID, $Depth, @VerticesAtDepth);
1145
1146 @VerticesAtDepth = ();
1147 while (($VertexID, $Depth) = each %{$This->{VerticesDepth}}) {
1148 push @{$VerticesAtDepth[$Depth]}, $VertexID;
1149 }
1150 return @VerticesAtDepth;
1151 }
1152
1153 # Collect vertices, along with their successors, at specific depths and return a list containing references to
1154 # lists with first value corresponding to vertex ID and second value a reference to a list containing
1155 # its successors.
1156 #
1157 # Depth values start from 0...
1158 #
1159 sub _CollectVerticesWithSuccessorsAtSpecificDepths {
1160 my($This) = @_;
1161 my($VertexID, $Depth, @VerticesWithSuccessorsAtDepth);
1162
1163 @VerticesWithSuccessorsAtDepth = ();
1164 while (($VertexID, $Depth) = each %{$This->{VerticesDepth}}) {
1165 my(@VertexWithSuccessors, @VertexSuccessors);
1166
1167 @VertexWithSuccessors = (); @VertexSuccessors = ();
1168 if (exists $This->{VerticesSuccessors}{$VertexID}) {
1169 push @VertexSuccessors, @{$This->{VerticesSuccessors}{$VertexID}};
1170 }
1171 push @VertexWithSuccessors, ($VertexID, \@VertexSuccessors);
1172 # Multiple entries for a vertex and its successors could be present at a specific depth...
1173 push @{$VerticesWithSuccessorsAtDepth[$Depth]}, \@VertexWithSuccessors;
1174 }
1175 return @VerticesWithSuccessorsAtDepth;
1176 }
1177
1178 # Search paths between two vertices...
1179 #
1180 sub _PerformPathsSearchBetween {
1181 my($This, $RootVertexID, $TargetVertexID) = @_;
1182 my($DepthLimit);
1183
1184 # Perform a targeted DFS search...
1185 $DepthLimit = undef;
1186 $This->_PerformVertexSearch("DFS", $RootVertexID, $DepthLimit, $TargetVertexID);
1187
1188 my($Path);
1189 $Path = $This->_CollectPathBetween($RootVertexID, $TargetVertexID);
1190
1191 if (defined $Path) {
1192 push @{$This->{Paths}}, $Path;
1193 }
1194 return $This;
1195 }
1196
1197 # Collect path between root and target vertex after the search...
1198 #
1199 sub _CollectPathBetween {
1200 my($This, $RootVertexID, $TargetVertexID) = @_;
1201
1202 # Does a path from root to target vertex exist?
1203 if (!(exists($This->{VerticesRoots}{$TargetVertexID}) && ($This->{VerticesRoots}{$TargetVertexID} == $RootVertexID))) {
1204 return undef;
1205 }
1206
1207 # Add target vertex ID path vertices...
1208 my($VertexID, $Path, @VertexIDs);
1209 @VertexIDs = ();
1210 $VertexID = $TargetVertexID;
1211 push @VertexIDs, $VertexID;
1212
1213 # Backtrack to root vertex ID...
1214 while ($This->{VerticesPredecessors}{$VertexID} != $VertexID) {
1215 $VertexID = $This->{VerticesPredecessors}{$VertexID};
1216 push @VertexIDs, $VertexID;
1217 }
1218
1219 # Create path from target to root and reverse it...
1220 $Path = new Graph::Path(@VertexIDs);
1221 $Path->Reverse();
1222
1223 return $Path;
1224 }
1225
1226 # Search vertices around specified root vertex with in specific neighborhood radius...
1227 #
1228 sub PerformNeighborhoodVerticesSearchWithRadiusUpto {
1229 my($This, $StartVertexID, $Radius) = @_;
1230
1231 # Make sure both start vertex and radius are defined...
1232 if (!defined $StartVertexID) {
1233 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Start vertex must be specified...";
1234 return undef;
1235 }
1236 if (!defined $Radius) {
1237 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Radius must be specified...";
1238 return undef;
1239 }
1240
1241 # Make sure both start vertex and length are valid...
1242 if (!$This->{Graph}->HasVertex($StartVertexID)) {
1243 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Vertex $StartVertexID doesn't exist...";
1244 return undef;
1245 }
1246 if ($Radius < 0) {
1247 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Specified radius, $Radius, must be a positive integer...";
1248 return undef;
1249 }
1250
1251 # Perform vertices search...
1252 return $This->_PerformNeighborhoodVerticesSearch("RadiusUpto", $StartVertexID, $Radius);
1253 }
1254
1255 # Search vertices around specified root vertex...
1256 #
1257 sub PerformNeighborhoodVerticesSearch {
1258 my($This, $StartVertexID) = @_;
1259
1260 # Make sure start vertex is defined...
1261 if (!defined $StartVertexID) {
1262 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Start vertex must be specified...";
1263 return undef;
1264 }
1265
1266 # Make sure start vertex is valid...
1267 if (!$This->{Graph}->HasVertex($StartVertexID)) {
1268 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Vertex $StartVertexID doesn't exist...";
1269 return undef;
1270 }
1271 # Perform vertices search...
1272 return $This->_PerformNeighborhoodVerticesSearch("AllRadii", $StartVertexID);
1273 }
1274
1275 # Search vertices around specified root vertex with in specific neighborhood radius along with
1276 # identification of successors of each vertex found during the search...
1277 #
1278 sub PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto {
1279 my($This, $StartVertexID, $Radius) = @_;
1280
1281 # Make sure both start vertex and radius are defined...
1282 if (!defined $StartVertexID) {
1283 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Start vertex must be specified...";
1284 return undef;
1285 }
1286 if (!defined $Radius) {
1287 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Radius must be specified...";
1288 return undef;
1289 }
1290
1291 # Make sure both start vertex and length are valid...
1292 if (!$This->{Graph}->HasVertex($StartVertexID)) {
1293 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Vertex $StartVertexID doesn't exist...";
1294 return undef;
1295 }
1296 if ($Radius < 0) {
1297 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Specified radius, $Radius, must be a positive integer...";
1298 return undef;
1299 }
1300
1301 # Perform vertices search...
1302 return $This->_PerformNeighborhoodVerticesSearch("WithSuccessorsAndRadiusUpto", $StartVertexID, $Radius);
1303 }
1304
1305 # Search vertices around specified root vertex along with identification of
1306 # successors of each vertex found during the search...
1307 #
1308 sub PerformNeighborhoodVerticesSearchWithSuccessors {
1309 my($This, $StartVertexID) = @_;
1310
1311 # Make sure start vertex is defined...
1312 if (!defined $StartVertexID) {
1313 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessors: No vertices search performed: Start vertex must be specified...";
1314 return undef;
1315 }
1316
1317 # Make sure start vertex is valid...
1318 if (!$This->{Graph}->HasVertex($StartVertexID)) {
1319 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessors: No vertices search performed: Vertex $StartVertexID doesn't exist...";
1320 return undef;
1321 }
1322 # Perform vertices search...
1323 return $This->_PerformNeighborhoodVerticesSearch("WithSuccessorsAndAllRadii", $StartVertexID);
1324 }
1325
1326 # Search vertices at successive neighborhood radii levels...
1327 #
1328 sub _PerformNeighborhoodVerticesSearch {
1329 my($This, $Mode, $RootVertexID, $Radius) = @_;
1330 my($DepthLimit, $AllowCycles);
1331
1332 $DepthLimit = defined $Radius ? $Radius : undef;
1333 $AllowCycles = undef;
1334
1335 # Perform BFS search...
1336 if ($Mode =~ /^RadiusUpto$/i) {
1337 $This->_PerformVertexNeighborhoodSearch("BFSWithLimit", $RootVertexID, $DepthLimit);
1338 }
1339 elsif ($Mode =~ /^(AllRadii)$/i) {
1340 $This->_PerformVertexNeighborhoodSearch("BFS", $RootVertexID);
1341 }
1342 elsif ($Mode =~ /^WithSuccessorsAndRadiusUpto$/i) {
1343 $AllowCycles = 1;
1344 $This->_PerformVertexNeighborhoodSearch("BFSWithLimit", $RootVertexID, $DepthLimit, $AllowCycles);
1345 }
1346 elsif ($Mode =~ /^WithSuccessorsAndAllRadii$/i) {
1347 $AllowCycles = 1;
1348 $This->_PerformVertexNeighborhoodSearch("BFSWithLimit", $RootVertexID, $DepthLimit, $AllowCycles);
1349 }
1350
1351 # Make sure traversal did get the root vertex...
1352 if (!exists $This->{VerticesDepth}{$RootVertexID}) {
1353 return $This;
1354 }
1355
1356 if ($Mode =~ /^(RadiusUpto|AllRadii)$/i) {
1357 push @{$This->{VerticesNeighborhoods}}, $This->_CollectVerticesAtSpecificDepths();
1358 }
1359 elsif ($Mode =~ /^(WithSuccessorsAndRadiusUpto|WithSuccessorsAndAllRadii)$/i) {
1360 push @{$This->{VerticesNeighborhoodsWithSuccessors}}, $This->_CollectVerticesWithSuccessorsAtSpecificDepths();
1361 }
1362
1363 return $This;
1364 }
1365
1366 # Perform appropriate vertex search...
1367 #
1368 sub _PerformVertexNeighborhoodSearch {
1369 my($This, $SearchType, $RootVertexID, $DepthLimit, $AllowCycles) = @_;
1370
1371 # Setup search...
1372 $This->{TraversalMode} = 'VertexNeighborhood';
1373 $This->{TraversalType} = $SearchType;
1374
1375 if (defined $RootVertexID) {
1376 $This->{RootVertex} = $RootVertexID;
1377 }
1378 if (defined $DepthLimit) {
1379 $This->{DepthLimit} = $DepthLimit;
1380 }
1381 if (defined $AllowCycles) {
1382 $This->{AllowVertexCycles} = $AllowCycles;
1383 }
1384
1385 # Perform search...
1386 return $This->_TraverseGraph();
1387 }
1388
1389 # Get orderded list of vertices after DFS/BFS search...
1390 #
1391 sub GetVertices {
1392 my($This) = @_;
1393
1394 return wantarray ? @{$This->{Vertices}} : scalar @{$This->{Vertices}};
1395 }
1396
1397 # Get a hash list containing vertex and root vertex as key/value pair for all vertices
1398 # ordered using DFS/BFS search available via GetVertices method...
1399 #
1400 sub GetVerticesRoots {
1401 my($This) = @_;
1402
1403 return %{$This->{VerticesRoots}};
1404 }
1405
1406 # Get a list containing lists of vertices in connected components of graph after DFS/BFS
1407 # search...
1408 #
1409 # Note:
1410 # . List is sorted in descending order of number of vertices in each connected component.
1411 #
1412 sub GetConnectedComponentsVertices {
1413 my($This) = @_;
1414 my($VertexID, $VertexRoot, @ConnectedVertices, %VerticesAtRoot);
1415
1416 @ConnectedVertices = ();
1417 %VerticesAtRoot = ();
1418 for $VertexID (@{$This->{Vertices}}) {
1419 $VertexRoot = $This->{VerticesRoots}{$VertexID};
1420 if (!exists $VerticesAtRoot{$VertexRoot}) {
1421 @{$VerticesAtRoot{$VertexRoot}} = ();
1422 }
1423 push @{$VerticesAtRoot{$VertexRoot}}, $VertexID;
1424 }
1425 push @ConnectedVertices, sort { @{$b} <=> @{$a} } values %VerticesAtRoot;
1426
1427 return wantarray ? @ConnectedVertices : scalar @ConnectedVertices;
1428 }
1429
1430 # Get predecessor vertices...
1431 #
1432 sub GetVerticesPredecessors {
1433 my($This) = @_;
1434
1435 return %{$This->{VerticesPredecessors}};
1436 }
1437
1438 # Get a hash list containing vertex and depth from root vertex as key/value pair for all vertices
1439 # ordered using DFS/BFS search available via GetVertices method...
1440 #
1441 sub GetVerticesDepth {
1442 my($This) = @_;
1443
1444 return %{$This->{VerticesDepth}};
1445 }
1446
1447 # Get paths found during paths search...
1448 #
1449 sub GetPaths {
1450 my($This) = @_;
1451
1452 return wantarray ? @{$This->{Paths}} : scalar @{$This->{Paths}};
1453 }
1454
1455 # Get vertices collected at various neighborhood radii...
1456 #
1457 sub GetVerticesNeighborhoods {
1458 my($This) = @_;
1459
1460 return wantarray ? @{$This->{VerticesNeighborhoods}} : scalar @{$This->{VerticesNeighborhoods}};
1461 }
1462
1463 # Get vertices, along with their successor vertices, collected at various neighborhood radii as
1464 # a list containing references to lists with first value corresponding to vertex ID and second value
1465 # a reference to a list containing its successors.
1466 #
1467 sub GetVerticesNeighborhoodsWithSuccessors {
1468 my($This) = @_;
1469
1470 return wantarray ? @{$This->{VerticesNeighborhoodsWithSuccessors}} : scalar @{$This->{VerticesNeighborhoodsWithSuccessors}};
1471 }
1472
1473 # Return a string containg data for PathsTraversal object...
1474 sub StringifyPathsTraversal {
1475 my($This) = @_;
1476 my($PathsTraversalString);
1477
1478 $PathsTraversalString = "PathsTraversalMode: " . $This->{TraversalMode};
1479 $PathsTraversalString .= "; PathsTraversalType: " . $This->{TraversalType};
1480
1481 # Vertices ordered by traversal...
1482 $PathsTraversalString .= "; Vertices: " . join(' ', @{$This->{Vertices}});
1483
1484 # Stringify depths of vertices...
1485 $PathsTraversalString .= "; " . $This->StringifyVerticesDepth();
1486
1487 # Stringify roots of vertices...
1488 $PathsTraversalString .= "; " . $This->StringifyVerticesRoots();
1489
1490 # Stringify predecessor of vertices...
1491 $PathsTraversalString .= "; " . $This->StringifyVerticesPredecessors();
1492
1493 # Stringify successor vertices...
1494 $PathsTraversalString .= "; " . $This->StringifyVerticesSuccessors();
1495
1496 # Stringify paths...
1497 $PathsTraversalString .= "; " . $This->StringifyPaths();
1498
1499 # Stringify vertices neighborhoods...
1500 $PathsTraversalString .= "; " . $This->StringifyVerticesNeighborhoods();
1501
1502 # Stringify vertices neighborhoods with successors...
1503 $PathsTraversalString .= "; " . $This->StringifyVerticesNeighborhoodsWithSuccessors();
1504
1505 return $PathsTraversalString;
1506 }
1507
1508 # Stringify vertices depth...
1509 #
1510 sub StringifyVerticesDepth {
1511 my($This) = @_;
1512 my($VertexID, $VertexDepth, $DepthString);
1513
1514 if (!@{$This->{Vertices}}) {
1515 $DepthString = "<Vertex-Depth>: None";
1516 return $DepthString;
1517 }
1518
1519 $DepthString = "<Vertex-Depth>: ";
1520 for $VertexID (@{$This->{Vertices}}) {
1521 $VertexDepth = $This->{VerticesDepth}{$VertexID};
1522 $DepthString .= " <$VertexID-$VertexDepth>";
1523 }
1524 return $DepthString;
1525 }
1526
1527 # Stringify roots of vertices...
1528 #
1529 sub StringifyVerticesRoots {
1530 my($This) = @_;
1531 my($VertexID, $RootVertexID, $RootsString);
1532
1533 if (!@{$This->{Vertices}}) {
1534 $RootsString = "<Vertex-RootVertex>: None";
1535 return $RootsString;
1536 }
1537
1538 $RootsString = "<Vertex-RootVertex>: ";
1539 for $VertexID (@{$This->{Vertices}}) {
1540 $RootVertexID = $This->{VerticesRoots}{$VertexID};
1541 $RootsString .= " <$VertexID-$RootVertexID>";
1542 }
1543 return $RootsString;
1544 }
1545
1546 # Stringify predecessor of vertices...
1547 #
1548 sub StringifyVerticesPredecessors {
1549 my($This) = @_;
1550 my($VertexID, $PredecessorVertexID, $PredecessorString);
1551
1552 if (!@{$This->{Vertices}}) {
1553 $PredecessorString = "<Vertex-PredecessorVertex>: None";
1554 return $PredecessorString;
1555 }
1556
1557 $PredecessorString = "<Vertex-PredecessorVertex>: ";
1558 for $VertexID (@{$This->{Vertices}}) {
1559 $PredecessorVertexID = $This->{VerticesPredecessors}{$VertexID};
1560 $PredecessorString .= " <$VertexID-$PredecessorVertexID>";
1561 }
1562 return $PredecessorString;
1563 }
1564
1565 # Stringify successor vertices...
1566 #
1567 sub StringifyVerticesSuccessors {
1568 my($This) = @_;
1569 my($VertexID, $SuccessorString, $VerticesSuccessorsString);
1570
1571 if (!@{$This->{Vertices}}) {
1572 $SuccessorString = "<Vertex-VerticesSuccessorsList>: None";
1573 return $SuccessorString;
1574 }
1575
1576 $SuccessorString = "<Vertex-VerticesSuccessorsList>: ";
1577 for $VertexID (@{$This->{Vertices}}) {
1578 if (exists($This->{VerticesSuccessors}{$VertexID}) && @{$This->{VerticesSuccessors}{$VertexID}}) {
1579 $VerticesSuccessorsString = join(',', @{$This->{VerticesSuccessors}{$VertexID}});
1580 }
1581 else {
1582 $VerticesSuccessorsString = "None";
1583 }
1584 $SuccessorString .= " <$VertexID-$VerticesSuccessorsString>";
1585 }
1586 return $SuccessorString;
1587 }
1588
1589 # Strinigify paths...
1590 #
1591 sub StringifyPaths {
1592 my($This) = @_;
1593 my($PathsString, $Path);
1594
1595 if (!@{$This->{Paths}}) {
1596 $PathsString = "Paths: None";
1597 return $PathsString;
1598 }
1599
1600 my($FirstPath);
1601 $PathsString = "Paths: ";
1602 $FirstPath = 1;
1603 for $Path (@{$This->{Paths}}) {
1604 if ($FirstPath) {
1605 $FirstPath = 0;
1606 }
1607 else {
1608 $PathsString .= " ";
1609 }
1610 $PathsString .= "<" . join('-', $Path->GetVertices()) . ">";
1611 }
1612 return $PathsString;
1613 }
1614
1615 # Strinigify vertices neighborhoods...
1616 #
1617 sub StringifyVerticesNeighborhoods {
1618 my($This) = @_;
1619 my($NeighborhoodsString, $NeighborhoodVerticesString, $Radius);
1620
1621 if (!@{$This->{VerticesNeighborhoods}}) {
1622 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVerticesList>: None";
1623 return $NeighborhoodsString;
1624 }
1625 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVerticesList>:";
1626 for $Radius (0 .. $#{$This->{VerticesNeighborhoods}}) {
1627 $NeighborhoodVerticesString = join(',', @{$This->{VerticesNeighborhoods}[$Radius]});
1628 $NeighborhoodsString .= " <$Radius-$NeighborhoodVerticesString>";
1629 }
1630
1631 return $NeighborhoodsString;
1632 }
1633
1634 # Strinigify vertices neighborhoods...
1635 #
1636 sub StringifyVerticesNeighborhoodsWithSuccessors {
1637 my($This) = @_;
1638 my($NeighborhoodsString, $NeighborhoodVertexSuccessorsString, $Radius, $NeighborhoodVertericesWithSuccessorsRef, $NeighborhoodVertexWithSuccessorsRef, $VertexID, $NeighborhoodVertexSuccessorsRef);
1639
1640 if (!@{$This->{VerticesNeighborhoodsWithSuccessors}}) {
1641 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None";
1642 return $NeighborhoodsString;
1643 }
1644 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None";
1645
1646 $Radius = 0;
1647 for $NeighborhoodVertericesWithSuccessorsRef (@{$This->{VerticesNeighborhoodsWithSuccessors}}) {
1648 for $NeighborhoodVertexWithSuccessorsRef (@{$NeighborhoodVertericesWithSuccessorsRef}) {
1649 ($VertexID, $NeighborhoodVertexSuccessorsRef) = @{$NeighborhoodVertexWithSuccessorsRef};
1650 $NeighborhoodVertexSuccessorsString = 'None';
1651 if (@{$NeighborhoodVertexSuccessorsRef}) {
1652 $NeighborhoodVertexSuccessorsString = join(',', @{$NeighborhoodVertexSuccessorsRef});
1653 }
1654 $NeighborhoodsString .= " <$Radius-$VertexID-$NeighborhoodVertexSuccessorsString>";
1655 }
1656 $Radius++;
1657 }
1658 return $NeighborhoodsString;
1659 }
1660
1661 # Return a reference to new paths traversal object...
1662 sub Copy {
1663 my($This) = @_;
1664 my($NewPathsTraversal);
1665
1666 $NewPathsTraversal = Storable::dclone($This);
1667
1668 return $NewPathsTraversal;
1669 }
1670
1671 1;
1672
1673 __END__
1674
1675 =head1 NAME
1676
1677 PathsTraversal
1678
1679 =head1 SYNOPSIS
1680
1681 use Graph::PathsTraversal;
1682
1683 use Graph::PathsTraversal qw(:all);
1684
1685 =head1 DESCRIPTION
1686
1687 B<PathsTraversal> class provides the following methods:
1688
1689 new, Copy, GetConnectedComponentsVertices, GetPaths, GetVertices,
1690 GetVerticesDepth, GetVerticesNeighborhoods,
1691 GetVerticesNeighborhoodsWithSuccessors, GetVerticesPredecessors, GetVerticesRoots,
1692 PerformAllPathsSearch, PerformAllPathsSearchWithLength,
1693 PerformAllPathsSearchWithLengthUpto, PerformBreadthFirstSearch,
1694 PerformBreadthFirstSearchWithLimit, PerformDepthFirstSearch,
1695 PerformDepthFirstSearchWithLimit, PerformNeighborhoodVerticesSearch,
1696 PerformNeighborhoodVerticesSearchWithRadiusUpto,
1697 PerformNeighborhoodVerticesSearchWithSuccessors,
1698 PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto, PerformPathsSearch,
1699 PerformPathsSearchBetween, PerformPathsSearchWithLength,
1700 PerformPathsSearchWithLengthUpto, StringifyPaths, StringifyPathsTraversal,
1701 StringifyVerticesDepth, StringifyVerticesNeighborhoods,
1702 StringifyVerticesNeighborhoodsWithSuccessors, StringifyVerticesPredecessors,
1703 StringifyVerticesRoots, StringifyVerticesSuccessors
1704
1705 =head2 METHODS
1706
1707 =over 4
1708
1709 =item B<new>
1710
1711 $PathsTraversal = new Graph::PathsTraversal($Graph);
1712
1713 Using specified I<Graph>, B<new> method creates a new B<PathsTraversal> object and returns
1714 newly created B<PathsTraversal> object.
1715
1716 =item B<Copy>
1717
1718 $PathsTraversal = $PathsTraversal->Copy();
1719
1720 Copies I<PathsTraversal> and its associated data using B<Storable::dclone> and returns a new
1721 B<PathsTraversal> object.
1722
1723 =item B<GetConnectedComponentsVertices>
1724
1725 @Components = $PathsTraversal->GetConnectedComponentsVertices();
1726 $NumOfComponents = $PathsTraversal->GetConnectedComponentsVertices();
1727
1728 Returns an array of B<Components> containing references to arrays of vertex IDs corresponding
1729 to connected components of graph after a search. In scalar context, the number of connected
1730 components is returned.
1731
1732 Connected B<Components> is sorted in descending order of number of vertices in each
1733 connected component.
1734
1735 =item B<GetPaths>
1736
1737 @Paths = $PathsTraversal->GetPaths();
1738 $NumOfPaths = $PathsTraversal->GetPaths();
1739
1740 Returns an array of B<Paths> containing references to arrays of vertex IDs corresponding to
1741 to paths traversed in a graph after a search. In scalar context, number of paths is returned.
1742
1743 B<Paths> array is sorted in ascending order of path lengths.
1744
1745 =item B<GetVertices>
1746
1747 @Vertices = $PathsTraversal->GetVertices();
1748 $NumOfVertices = $PathsTraversal->GetVertices();
1749
1750 Returns an array containing an ordered list of vertex IDs traversed during a search. In
1751 scalar context, the number of vertices is returned.
1752
1753 =item B<GetVerticesDepth>
1754
1755 %VerticesDepth = $PathsTraversal->GetVerticesDepth();
1756
1757 Returns a hash I<VerticesDepth> containing vertex ID and depth from root vertex as a key and
1758 value pair for all vertices traversed during a search.
1759
1760 =item B<GetVerticesNeighborhoods>
1761
1762 @VerticesNeighborhoods =
1763 $PathsTraversal->GetVerticesNeighborhoods();
1764 $NumOfVerticesNeighborhoods =
1765 $PathsTraversal->GetVerticesNeighborhoods();
1766
1767 Returns an array I<VerticesNeighborhoods> containing references to arrays corresponding
1768 to vertices collected at various neighborhood radii around a specified vertex during a vertex
1769 neighborhood search. In scalar context, the number of neighborhoods is returned.
1770
1771 =item B<GetVerticesNeighborhoodsWithSuccessors>
1772
1773 @VerticesNeighborhoodsWithSucceessors =
1774 $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
1775 $NumOfVerticesNeighborhoodsWithSucceessors =
1776 $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
1777
1778 Returns an array I<VerticesNeighborhoodsWithSucceessors> containing references to arrays
1779 with first value corresponding to vertex IDs corresponding to a vertex at a specific neighborhood
1780 radius level and second value a reference to an arraty containing its successors.
1781
1782 =item B<GetVerticesPredecessors>
1783
1784 %VerticesPredecessors = $PathsTraversal->GetVerticesPredecessors();
1785
1786 Returns a hash I<VerticesPredecessors> containing vertex ID and predecessor vertex ID as key
1787 and value pair for all vertices traversed during a search.
1788
1789 =item B<GetVerticesRoots>
1790
1791 %VerticesRoots = $PathsTraversal->GetVerticesRoots();
1792
1793 Returns a hash I<VerticesPredecessors> containing vertex ID and root vertex ID as a key
1794 and value pair for all vertices traversed during a search.
1795
1796 =item B<PerformAllPathsSearch>
1797
1798 $PathsTraversal->PerformAllPathsSearch($StartVertexID, [$AllowCycles]);
1799
1800 Searches all paths starting from a I<StartVertexID> with sharing of edges in paths traversed and
1801 returns I<PathsTraversal>.
1802
1803 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
1804 completing the cycle.
1805
1806 =item B<PerformAllPathsSearchWithLength>
1807
1808 $PathsTraversal->PerformAllPathsSearchWithLength($StartVertexID,
1809 $Length, [$AllowCycles]);
1810
1811 Searches all paths starting from I<StartVertexID> of specific I<Length> with sharing of
1812 edges in paths traversed and returns I<PathsTraversal>.
1813
1814 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
1815 completing the cycle.
1816
1817 =item B<PerformAllPathsSearchWithLengthUpto>
1818
1819 $PathsTraversal->PerformAllPathsSearchWithLengthUpto($StartVertexID,
1820 $Length, [$AllowCycles]);
1821
1822 Searches all paths starting from I<StartVertexID> of length upto a I<Length> with sharing of
1823 edges in paths traversed and returns I<PathsTraversal>.
1824
1825 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
1826 completing the cycle.
1827
1828 =item B<PerformBreadthFirstSearch>
1829
1830 $PathsTraversal->PerformBreadthFirstSearch();
1831
1832 Performs Breadth First Search (BFS) and returns I<PathsTraversal>.
1833
1834 =item B<PerformBreadthFirstSearchWithLimit>
1835
1836 $PathsTraversal->PerformBreadthFirstSearchWithLimit($DepthLimit,
1837 [$RootVertexID]);
1838
1839 Performs BFS with depth up to I<DepthLimit> starting at I<RootVertexID> and returns
1840 I<PathsTraversal>. By default, root vertex ID corresponds to an arbitrary vertex.
1841
1842 =item B<PerformDepthFirstSearch>
1843
1844 $Return = $PathsTraversal->PerformDepthFirstSearch();
1845
1846 Performs Depth First Search (DFS) and returns I<PathsTraversal>.
1847
1848 =item B<PerformDepthFirstSearchWithLimit>
1849
1850 $PathsTraversal->PerformDepthFirstSearchWithLimit($DepthLimit,
1851 [$RootVertexID]);
1852
1853 Performs DFS with depth up to I<DepthLimit> starting at I<RootVertexID> and returns
1854 I<PathsTraversal>. By default, root vertex ID corresponds to an arbitrary vertex.
1855
1856 =item B<PerformNeighborhoodVerticesSearch>
1857
1858 $PathsTraversal->PerformNeighborhoodVerticesSearch($StartVertexID);
1859
1860 Searches vertices around I<StartVertexID> at all neighborhood radii and returns
1861 I<PathsTraversal> object.
1862
1863 =item B<PerformNeighborhoodVerticesSearchWithRadiusUpto>
1864
1865 $PathsTraversal->PerformNeighborhoodVerticesSearchWithRadiusUpto(
1866 $StartVertexID, $Radius);
1867
1868 Searches vertices around I<StartVertexID> with neighborhood radius up to I<Radius> and returns
1869 I<PathsTraversal> object.
1870
1871 =item B<PerformNeighborhoodVerticesSearchWithSuccessors>
1872
1873 $PathsTraversal->PerformNeighborhoodVerticesSearchWithSuccessors(
1874 $StartVertexID);
1875
1876 Searches vertices around I<StartVertexID> at all neighborhood radii along with identification of
1877 successor vertices for each vertex found during the traversal and returns I<PathsTraversal>.
1878
1879 =item B<PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto>
1880
1881 $PathsTraversal->
1882 PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto(
1883 $StartVertexID, $Radius);
1884
1885 Searches vertices around I<StartVertexID> with neighborhood radius upto I<Radius> along with
1886 identification of successor vertices for each vertex found during the traversal and returns
1887 I<PathsTraversal>.
1888
1889 =item B<PerformPathsSearch>
1890
1891 $PathsTraversal->PerformPathsSearch($StartVertexID, [$AllowCycles]);
1892
1893 Searches paths starting from I<StartVertexID> with no sharing of edges in paths traversed and
1894 returns I<PathsTraversal>.
1895
1896 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
1897 completing the cycle.
1898
1899 =item B<PerformPathsSearchBetween>
1900
1901 $PathsTraversal->PerformPathsSearchBetween($StartVertexID, $EndVertexID);
1902
1903 Searches paths between I<StartVertexID> and I<EndVertexID> and returns I<PathsTraversal>
1904
1905 =item B<PerformPathsSearchWithLength>
1906
1907 $PathsTraversal->PerformPathsSearchWithLength($StartVertexID, $Length,
1908 [$AllowCycles]);
1909
1910 Searches paths starting from I<StartVertexID> with length I<Length> with no sharing of
1911 edges in paths traversed and returns I<PathsTraversal>.
1912
1913 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
1914 completing the cycle.
1915
1916 =item B<PerformPathsSearchWithLengthUpto>
1917
1918 $PathsTraversal->PerformPathsSearchWithLengthUpto($StartVertexID, $Length,
1919 [$AllowCycles]);
1920
1921 Searches paths starting from I<StartVertexID> with length upto I<Length> with no sharing of
1922 edges in paths traversed and returns I<PathsTraversal>.
1923
1924 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
1925 completing the cycle.
1926
1927 =item B<StringifyPaths>
1928
1929 $String = $PathsTraversal->StringifyPaths();
1930
1931 Returns a string containing information about traversed paths in I<PathsTraversal> object
1932
1933 =item B<StringifyPathsTraversal>
1934
1935 $String = $PathsTraversal->StringifyPathsTraversal();
1936
1937 Returns a string containing information about I<PathsTraversal> object.
1938
1939 =item B<StringifyVerticesDepth>
1940
1941 $String = $PathsTraversal->StringifyVerticesDepth();
1942
1943 Returns a string containing information about depth of vertices found during search by
1944 I<PathsTraversal> object.
1945
1946 =item B<StringifyVerticesNeighborhoods>
1947
1948 $String = $PathsTraversal->StringifyVerticesNeighborhoods();
1949
1950 Returns a string containing information about neighborhoods of vertices found during search by
1951 I<PathsTraversal> object.
1952
1953 =item B<StringifyVerticesNeighborhoodsWithSuccessors>
1954
1955 $String = $PathsTraversal->StringifyVerticesNeighborhoodsWithSuccessors();
1956
1957 Returns a string containing information about neighborhoods of vertices along with their successors
1958 found during search by I<PathsTraversal> object.
1959
1960 =item B<StringifyVerticesPredecessors>
1961
1962 $String = $PathsTraversal->StringifyVerticesPredecessors();
1963
1964 Returns a string containing information about predecessors of vertices found during search by
1965 I<PathsTraversal> object.
1966
1967 =item B<StringifyVerticesRoots>
1968
1969 $String = $PathsTraversal->StringifyVerticesRoots();
1970
1971 Returns a string containing information about roots of vertices found during search by
1972 I<PathsTraversal> object.
1973
1974 =item B<StringifyVerticesSuccessors>
1975
1976 $String = $PathsTraversal->StringifyVerticesSuccessors();
1977
1978 Returns a string containing information about successors of vertices found during search by
1979 I<PathsTraversal> object.
1980
1981 =back
1982
1983 =head1 AUTHOR
1984
1985 Manish Sud <msud@san.rr.com>
1986
1987 =head1 SEE ALSO
1988
1989 Graph.pm, Path.pm
1990
1991 =head1 COPYRIGHT
1992
1993 Copyright (C) 2015 Manish Sud. All rights reserved.
1994
1995 This file is part of MayaChemTools.
1996
1997 MayaChemTools is free software; you can redistribute it and/or modify it under
1998 the terms of the GNU Lesser General Public License as published by the Free
1999 Software Foundation; either version 3 of the License, or (at your option)
2000 any later version.
2001
2002 =cut