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