       1 package Graph::PathsTraversal;
       2 #
       3 # File: PathsTraversal.pm
       4 # Author: Manish Sud <msud@san.rr.com>
       5 #
       6 # Copyright (C) 2018 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