1 package PathsTraversal;
   2 #
   3 # $RCSfile: PathsTraversal.pm,v $
   4 # $Date: 2008/04/19 16:11:49 $
   5 # $Revision: 1.12 $
   6 #
   7 # Author: Manish Sud <msud@san.rr.com>
   8 #
   9 # Copyright (C) 2004-2008 Manish Sud. All rights reserved.
  10 #
  11 # This file is part of MayaChemTools.
  12 #
  13 # MayaChemTools is free software; you can redistribute it and/or modify it under
  14 # the terms of the GNU Lesser General Public License as published by the Free
  15 # Software Foundation; either version 3 of the License, or (at your option) any
  16 # later version.
  17 #
  18 # MayaChemTools is distributed in the hope that it will be useful, but without
  19 # any warranty; without even the implied warranty of merchantability of fitness
  20 # for a particular purpose.  See the GNU Lesser General Public License for more
  21 # details.
  22 #
  23 # You should have received a copy of the GNU Lesser General Public License
  24 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
  25 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
  26 # Boston, MA, 02111-1307, USA.
  27 #
  28 use 5.006;
  29 use strict;
  30 use Carp;
  31 use Exporter;
  32 use Graph;
  33 use Graph::Path;
  34 
  35 use vars qw($VERSION @ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
  36 
  37 $VERSION = '1.00';
  38 @ISA = qw(Exporter);
  39 @EXPORT = qw();
  40 @EXPORT_OK = qw();
  41 
  42 %EXPORT_TAGS = (all  => [@EXPORT, @EXPORT_OK]);
  43 
  44 # Setup class variables...
  45 my($ClassName);
  46 _InitializeClass();
  47 
  48 # Overload Perl functions...
  49 use overload '""' => 'StringifyPathsTraversal';
  50 
  51 # Class constructor...
  52 sub new {
  53   my($Class, $Graph) = @_;
  54 
  55   # Initialize object...
  56   my $This = {};
  57   bless $This, ref($Class) || $Class;
  58   $This->_InitializePathsTraversal($Graph);
  59 
  60   return $This;
  61 }
  62 
  63 # Initialize object data...
  64 sub _InitializePathsTraversal {
  65   my($This, $Graph) = @_;
  66 
  67   # Graph object...
  68   $This->{Graph} = $Graph;
  69 
  70   # Traversal mode: Vertex or Path
  71   $This->{TraversalMode} = '';
  72 
  73   # Traversal type: DFS, DFSWithLimit, BFS, BFSWithLimit...
  74   $This->{TraversalType} = '';
  75 
  76   # For finding root vertex and controlling search...
  77   my(@VertexIDs);
  78   @VertexIDs = $This->{Graph}->GetVertices();
  79   %{$This->{VerticesToVisit}} = ();
  80   @{$This->{VerticesToVisit}}{ @VertexIDs } = @VertexIDs;
  81 
  82   # Root vertex of all visited vertices...
  83   %{$This->{VerticesRoots}} = ();
  84 
  85   # Visited vertices...
  86   %{$This->{VisitedVertices}} = ();
  87 
  88   # Finished vertices...
  89   %{$This->{FinishedVertices}} = ();
  90 
  91   # List of active vertices during DFS/BFS search...
  92   @{$This->{ActiveVertices}} = ();
  93 
  94   # List of ordered vertices traversed during DFS/BFS search...
  95   @{$This->{Vertices}} = ();
  96 
  97   # Vertex neighbors during traversal...
  98   %{$This->{VerticesNeighbors}} = ();
  99 
 100   # Vertices depth from root...
 101   %{$This->{VerticesDepth}} = ();
 102 
 103   # Predecessor of each vertex during vertex traversal. For root vertex, it's root itself...
 104   %{$This->{VerticesPredecessors}} = ();
 105 
 106   # Successors of each vertex during vertex traversal...
 107   %{$This->{VerticesSuccessors}} = ();
 108 
 109   # Vertices at different neighborhood levels during vertex traversal...
 110   @{$This->{VerticesNeighborhoods}} = ();
 111 
 112   # Visited edges during Path TraversalMode...
 113   %{$This->{VisitedEdges}} = ();
 114   %{$This->{VisitedEdges}->{From}} = ();
 115   %{$This->{VisitedEdges}->{To}} = ();
 116 
 117   # Vertex path during Path TraversalMode...
 118   %{$This->{VerticesPaths}} = ();
 119 
 120   # Allow cycles in paths during Path TraversalMode...
 121   $This->{AllowPathCycles} = 1;
 122 
 123   # Cycle closure vertices during Path TraversalMode...
 124   %{$This->{CycleClosureVertices}} = ();
 125 
 126   # Paths traversed during search...
 127   @{$This->{Paths}} = ();
 128 
 129   return $This;
 130 }
 131 
 132 # Initialize class ...
 133 sub _InitializeClass {
 134   #Class name...
 135   $ClassName = __PACKAGE__;
 136 }
 137 
 138 # Perform a depth first search (DFS)...
 139 #
 140 sub PerformDepthFirstSearch {
 141   my($This, $RootVertexID) = @_;
 142 
 143   if (defined $RootVertexID) {
 144     if (!$This->{Graph}->HasVertex($RootVertexID)) {
 145       carp "Warning: ${ClassName}->PerformDepthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist...";
 146       return undef;
 147     }
 148   }
 149   return $This->_PerformVertexSearch("DFS", $RootVertexID);
 150 }
 151 
 152 # Perform a depth first search (DFS) with limit on depth...
 153 #
 154 sub PerformDepthFirstSearchWithLimit {
 155   my($This, $DepthLimit, $RootVertexID) = @_;
 156 
 157   if (!defined $DepthLimit) {
 158       carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Depth limit must be specified...";
 159       return undef;
 160   }
 161   if ($DepthLimit < 0) {
 162     carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer...";
 163     return undef;
 164   }
 165   if (defined $RootVertexID) {
 166     if (!$This->{Graph}->HasVertex($RootVertexID)) {
 167       carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist...";
 168       return undef;
 169     }
 170   }
 171   return $This->_PerformVertexSearch("DFSWithLimit", $RootVertexID, $DepthLimit);
 172 }
 173 
 174 # Perform a breadth first search (BFS)...
 175 #
 176 sub PerformBreadthFirstSearch {
 177   my($This, $RootVertexID) = @_;
 178 
 179   if (defined $RootVertexID) {
 180     if (!$This->{Graph}->HasVertex($RootVertexID)) {
 181       carp "Warning: ${ClassName}->PerformBreadthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist...";
 182       return undef;
 183     }
 184   }
 185   return $This->_PerformVertexSearch("BFS", $RootVertexID);
 186 }
 187 
 188 # Perform a breadth first search (BFS) with limit...
 189 #
 190 sub PerformBreadthFirstSearchWithLimit {
 191   my($This, $DepthLimit, $RootVertexID) = @_;
 192 
 193   if (!defined $DepthLimit) {
 194       carp "Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Depth limit must be specified...";
 195       return undef;
 196   }
 197   if ($DepthLimit < 0) {
 198     carp "Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer...";
 199     return undef;
 200   }
 201   if (defined $RootVertexID) {
 202     if (!$This->{Graph}->HasVertex($RootVertexID)) {
 203       carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist...";
 204       return undef;
 205     }
 206   }
 207   return $This->_PerformVertexSearch("BFSWithLimit", $RootVertexID, $DepthLimit);
 208 }
 209 
 210 # Perform appropriate vertex search...
 211 #
 212 sub _PerformVertexSearch {
 213   my($This, $SearchType, $RootVertexID, $DepthLimit, $TargetVertexID) = @_;
 214 
 215   # Setup search...
 216   $This->{TraversalMode} = 'Vertex';
 217   $This->{TraversalType} = $SearchType;
 218 
 219   if (defined $RootVertexID) {
 220     $This->{RootVertex} = $RootVertexID;
 221   }
 222   if (defined $DepthLimit) {
 223     $This->{DepthLimit} = $DepthLimit;
 224   }
 225   if (defined $TargetVertexID) {
 226     $This->{TargetVertex} = $TargetVertexID;
 227   }
 228 
 229   # Perform search...
 230   return $This->_TraverseGraph();
 231 }
 232 
 233 # Perform DFS or BFS traversal with or without any limits...
 234 #
 235 sub _TraverseGraph {
 236   my($This) = @_;
 237   my($ProcessingVertices, $CurrentVertexID, $NeighborVertexID, $VertexID);
 238 
 239   if ($This->{TraversalMode} !~ /^(Vertex|Path)$/i) {
 240     return $This;
 241   }
 242 
 243   $ProcessingVertices = 1;
 244 
 245   VERTICES: while ($ProcessingVertices) {
 246     # Set root vertex...
 247     if (!@{$This->{ActiveVertices}}) {
 248       my($RootVertexID);
 249 
 250       $RootVertexID = $This->_GetRootVertex();
 251       if (!defined $RootVertexID) {
 252 	$ProcessingVertices = 0; next VERTICES;
 253       }
 254       $This->_ProcessVisitedVertex($RootVertexID, $RootVertexID);
 255     }
 256 
 257     # Get current active vertex...
 258     $CurrentVertexID = $This->_GetActiveVertex();
 259     if (!defined $CurrentVertexID) {
 260       $ProcessingVertices = 0; next VERTICES;
 261     }
 262 
 263     # Get next available neighbor of current vertex...
 264     #
 265     $NeighborVertexID = $This->_GetNeighborVertex($CurrentVertexID);
 266 
 267     # Process neighbor or current vertex...
 268     if (defined $NeighborVertexID) {
 269       $This->_ProcessVisitedVertex($NeighborVertexID, $CurrentVertexID);
 270     }
 271     else {
 272       # Finished with all neighbors for current vertex...
 273       $This->_ProcessFinishedVertex($CurrentVertexID);
 274     }
 275   }
 276   return $This;
 277 }
 278 
 279 # Get root vertex to start the search...
 280 #
 281 # Notes:
 282 #   . User specification of root vertex forces traversal in a specific connected component
 283 #     of graph; To traverse find all connected components, perform traversal without specification of
 284 #     a root vertex.
 285 #
 286 sub _GetRootVertex {
 287   my($This) = @_;
 288   my($RootVertexID);
 289 
 290   # Check for specified root vertex and constrain traversal to specific connected
 291   # component by setting root limit...
 292   if (exists $This->{RootVertex}) {
 293     $RootVertexID = $This->{RootVertex};
 294     delete $This->{RootVertex};
 295     $This->{RootVertexSpecified} = 1;
 296 
 297     return $RootVertexID;
 298   }
 299   # Traversal limited to connected component containing specified root vertex...
 300   if (exists $This->{RootVertexSpecified}) {
 301     return undef;
 302   }
 303 
 304   # Use first vertex in sorted available vertices list to get root vertex. Vertex
 305   # with largest degree could also be used as root vertex. However, for all
 306   # practical purposes, any arbitrary vertex can be used as root vertex to
 307   # start search for another disconnected component of the graph.
 308   #
 309   my(@VerticesToVisit);
 310 
 311   $RootVertexID = undef; @VerticesToVisit = ();
 312   @VerticesToVisit = sort { $a <=> $b } keys %{$This->{VerticesToVisit}};
 313   if (@VerticesToVisit) {
 314     $RootVertexID = $VerticesToVisit[0];
 315   }
 316   return $RootVertexID;
 317 }
 318 
 319 # Get current or new active vertex for DFS/BFS traversals...
 320 #
 321 sub _GetActiveVertex {
 322   my($This) = @_;
 323   my($ActiveVertexID);
 324 
 325   $ActiveVertexID = undef;
 326   if ($This->{TraversalType} =~ /^(DFS|DFSWithLimit)$/i) {
 327     # For DFS, it's last vertex in  LIFO queue...
 328     $ActiveVertexID = $This->{ActiveVertices}[-1];
 329   }
 330   elsif ($This->{TraversalType} =~ /^(BFS|BFSWithLimit)$/i) {
 331     # For BFS, it's first vertex in FIFO queue...
 332     $ActiveVertexID = $This->{ActiveVertices}[0];
 333   }
 334   return $ActiveVertexID;
 335 }
 336 
 337 # Get available neigbor of specified vertex...
 338 #
 339 sub _GetNeighborVertex {
 340   my($This, $VertexID) = @_;
 341 
 342   # Retrieve neighbors for vertex...
 343   if (!exists $This->{VerticesNeighbors}{$VertexID}) {
 344     @{$This->{VerticesNeighbors}{$VertexID}}  = ();
 345 
 346     if (exists $This->{DepthLimit}) {
 347       # Only collect neighbors to visit below specified depth limit...
 348       if ($This->{VerticesDepth}{$VertexID} < $This->{DepthLimit}) {
 349 	push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
 350       }
 351       else {
 352 	if (!exists $This->{RootVertexSpecified}) {
 353 	  # Mark all other downstream neighbor vertices to be ignored from any further
 354 	  # processing and avoid selection of a new root...
 355 	  $This->_IgnoreDownstreamNeighbors($VertexID);
 356 	}
 357       }
 358     }
 359     elsif (exists $This->{TargetVertex}) {
 360       if ($VertexID != $This->{TargetVertex}) {
 361 	push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
 362       }
 363     }
 364     else {
 365       push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
 366     }
 367   }
 368 
 369   if ($This->{TraversalMode} =~ /^Path$/i) {
 370     # Get available neighbor for path search...
 371     return $This->_GetNeighborVertexDuringPathTraversal($VertexID);
 372   }
 373   elsif ($This->{TraversalMode} =~ /^Vertex$/i) {
 374     # Get unvisited neighbor for vertex search...
 375     return $This->_GetNeighborVertexDuringVertexTraversal($VertexID);
 376   }
 377   return undef;
 378 }
 379 
 380 # Get unvisited neigbor of specified vertex during vertex traversal...
 381 #
 382 sub _GetNeighborVertexDuringVertexTraversal {
 383   my($This, $VertexID) = @_;
 384   my($NeighborVertexID, $UnvisitedNeighborVertexID);
 385 
 386   # Get unvisited neighbor...
 387   $UnvisitedNeighborVertexID = undef;
 388   NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
 389     if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
 390       $UnvisitedNeighborVertexID = $NeighborVertexID;
 391       last NEIGHBOR;
 392     }
 393   }
 394   return $UnvisitedNeighborVertexID;
 395 }
 396 
 397 # Get available neigbor of specified vertex during path traversal...
 398 #
 399 sub _GetNeighborVertexDuringPathTraversal {
 400   my($This, $VertexID) = @_;
 401   my($NeighborVertexID, $UnvisitedNeighborVertexID);
 402 
 403   # Get unvisited neighbor...
 404   $UnvisitedNeighborVertexID = undef;
 405   NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
 406     if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
 407       # An unvisited vertex...
 408       $UnvisitedNeighborVertexID = $NeighborVertexID;
 409       last NEIGHBOR;
 410     }
 411     # Look for any unvisited edge back to visited vertex...
 412     if ($This->_IsVisitedEdge($VertexID, $NeighborVertexID) || $This->_IsVisitedEdge($NeighborVertexID, $VertexID)) {
 413       next NEIGHBOR;
 414     }
 415     # Check its depth...
 416     if (exists $This->{DepthLimit}) {
 417       if (($This->{VerticesDepth}{$VertexID} + 1) >= $This->{DepthLimit}) {
 418     	next NEIGHBOR;
 419       }
 420     }
 421 
 422     # It's the edge final edge of a cycle in case $NeighborVertexID is already in the path; otherwise, it's
 423     # part of the path from a different direction in a cycle or a left over vertex during Limit search.
 424     #
 425     # Allow cycle or edge selection based on cycles and shared edges parameters...
 426     #
 427     if ($This->_IsCycleClosureEdge($VertexID, $NeighborVertexID)) {
 428       if ($This->{AllowPathCycles}) {
 429 	$This->{CycleClosureVertices}{$NeighborVertexID} = 1;
 430 	$UnvisitedNeighborVertexID = $NeighborVertexID;
 431 	last NEIGHBOR;
 432       }
 433     }
 434     else {
 435       $UnvisitedNeighborVertexID = $NeighborVertexID;
 436       last NEIGHBOR;
 437     }
 438   }
 439   return $UnvisitedNeighborVertexID;
 440 }
 441 
 442 # Process visited vertex...
 443 #
 444 sub _ProcessVisitedVertex {
 445   my($This, $VertexID, $PredecessorVertexID) = @_;
 446 
 447   if (!exists $This->{VisitedVertices}{$VertexID}) {
 448     # Add it to active vertices list...
 449     push @{$This->{ActiveVertices}}, $VertexID;
 450 
 451     # Mark vertex as visited vertex and take it out from the list of vertices to visit...
 452     $This->{VisitedVertices}{$VertexID} = 1;
 453     delete $This->{VerticesToVisit}{$VertexID};
 454   }
 455 
 456   # Set up root vertex, predecessor vertex and distance from root...
 457   if ($VertexID == $PredecessorVertexID) {
 458     $This->{VerticesRoots}{$VertexID} = $VertexID;
 459 
 460     $This->{VerticesPredecessors}{$VertexID} = $VertexID;
 461     if (!exists $This->{VerticesSuccessors}{$VertexID}) {
 462       @{$This->{VerticesSuccessors}{$VertexID}} = ();
 463     }
 464 
 465     $This->{VerticesDepth}{$VertexID} = 0;
 466 
 467     if ($This->{TraversalMode} =~ /^Path$/i) {
 468       $This->_ProcessVisitedPath($VertexID, $PredecessorVertexID);
 469     }
 470   }
 471   else {
 472     $This->{VerticesRoots}{$VertexID} = $This->{VerticesRoots}{$PredecessorVertexID};
 473 
 474     $This->{VerticesPredecessors}{$VertexID} = $PredecessorVertexID;
 475     if (!exists $This->{VerticesSuccessors}{$PredecessorVertexID}) {
 476       @{$This->{VerticesSuccessors}{$PredecessorVertexID}} = ();
 477     }
 478     push @{$This->{VerticesSuccessors}{$PredecessorVertexID}}, $VertexID;
 479 
 480     if (!exists $This->{VerticesDepth}{$VertexID}) {
 481       $This->{VerticesDepth}{$VertexID} = $This->{VerticesDepth}{$PredecessorVertexID} + 1;
 482     }
 483 
 484     if ($This->{TraversalMode} =~ /^Path$/i) {
 485       $This->_ProcessVisitedPath($VertexID, $PredecessorVertexID);
 486       $This->_ProcessVisitedEdge($PredecessorVertexID, $VertexID);
 487     }
 488   }
 489   return $This;
 490 }
 491 
 492 # Process visited path...
 493 #
 494 sub _ProcessVisitedPath {
 495   my($This, $VertexID, $PredecessorVertexID) = @_;
 496 
 497   # Initialize VerticesPath...
 498   if (!exists $This->{VerticesPaths}{$VertexID}) {
 499     @{$This->{VerticesPaths}{$VertexID}} = ();
 500   }
 501 
 502   if ($VertexID == $PredecessorVertexID) {
 503     # Starting of a path from root...
 504     push @{$This->{VerticesPaths}{$VertexID}}, $VertexID;
 505   }
 506   else {
 507     # Setup path for a vertex using path information from predecessor vertex...
 508     if (exists $This->{CycleClosureVertices}{$PredecessorVertexID}) {
 509       # Start of a new path from predecessor vertex...
 510       push @{$This->{VerticesPaths}{$VertexID}}, "${PredecessorVertexID}-${VertexID}";
 511     }
 512     else {
 513       my($PredecessorVertexPath);
 514       for $PredecessorVertexPath (@{$This->{VerticesPaths}{$PredecessorVertexID}}) {
 515 	push @{$This->{VerticesPaths}{$VertexID}}, "${PredecessorVertexPath}-${VertexID}";
 516       }
 517     }
 518   }
 519   return $This;
 520 }
 521 
 522 # Process visited edge...
 523 #
 524 sub _ProcessVisitedEdge {
 525   my($This, $VertexID1, $VertexID2) = @_;
 526 
 527   if (!exists $This->{VisitedEdges}->{From}->{$VertexID1}) {
 528     %{$This->{VisitedEdges}->{From}->{$VertexID1}} = ();
 529   }
 530   $This->{VisitedEdges}->{From}->{$VertexID1}->{$VertexID2} = $VertexID2;
 531 
 532   if (!exists $This->{VisitedEdges}->{To}->{$VertexID2}) {
 533     %{$This->{VisitedEdges}->{To}->{$VertexID2}} = ();
 534   }
 535   $This->{VisitedEdges}->{To}->{$VertexID2}->{$VertexID1} = $VertexID1;
 536 
 537   return $This;
 538 }
 539 
 540 # Finished processing active vertex...
 541 #
 542 sub _ProcessFinishedVertex {
 543   my($This, $VertexID) = @_;
 544 
 545   if (!exists $This->{FinishedVertices}{$VertexID}) {
 546     $This->{FinishedVertices}{$VertexID} = $VertexID;
 547     # Add vertex to list of vertices found by traversal...
 548     push @{$This->{Vertices}}, $VertexID;
 549   }
 550 
 551   # Any active vertices left...
 552   if (!@{$This->{ActiveVertices}}) {
 553     return $This;
 554   }
 555 
 556   # Take it off active vertices list...
 557   if ($This->{TraversalType} =~ /^(DFS|DFSWithLimit)$/i) {
 558     # For DFS, it's last vertex in LIFO queue...
 559     pop @{$This->{ActiveVertices}};
 560   }
 561   elsif ($This->{TraversalType} =~ /^(BFS|BFSWithLimit)$/i) {
 562     # For BFS, it's first vertex in  FIFO queue...
 563     shift @{$This->{ActiveVertices}};
 564   }
 565   return $This;
 566 }
 567 
 568 # Mark all other downstream neighbor vertices to be ignored from any further
 569 # processing...
 570 #
 571 sub _IgnoreDownstreamNeighbors {
 572   my($This, $VertexID, $PredecessorVertexID) = @_;
 573 
 574   if (exists $This->{VerticesToVisit}{$VertexID}) {
 575     # Mark vertex as visited vertex and take it out from the list of vertices to visit...
 576     $This->{VisitedVertices}{$VertexID} = 1;
 577     delete $This->{VerticesToVisit}{$VertexID};
 578 
 579     if (defined($PredecessorVertexID) && $This->{TraversalMode} =~ /^Path$/i) {
 580       $This->_ProcessVisitedEdge($VertexID, $PredecessorVertexID);
 581     }
 582   }
 583   my($NeighborVertexID, @NeighborsVertexIDs);
 584 
 585   @NeighborsVertexIDs = ();
 586   @NeighborsVertexIDs = $This->{Graph}->GetNeighbors($VertexID);
 587   NEIGHBOR: for $NeighborVertexID (@NeighborsVertexIDs) {
 588     if (!exists $This->{VerticesToVisit}{$NeighborVertexID}) {
 589       # Avoid going back to predecessor vertex which has already been ignored...
 590       next NEIGHBOR;
 591     }
 592     $This->_IgnoreDownstreamNeighbors($NeighborVertexID, $VertexID);
 593   }
 594   return $This;
 595 }
 596 
 597 # Is it a visited edge?
 598 #
 599 sub _IsVisitedEdge {
 600   my($This, $VertexID1, $VertexID2) = @_;
 601 
 602   if (exists $This->{VisitedEdges}->{From}->{$VertexID1}) {
 603     if (exists $This->{VisitedEdges}->{From}->{$VertexID1}->{$VertexID2}) {
 604       return 1;
 605     }
 606   }
 607   elsif (exists $This->{VisitedEdges}->{To}->{$VertexID2}) {
 608     if (exists $This->{VisitedEdges}->{To}->{$VertexID2}->{$VertexID1}) {
 609       return 1;
 610     }
 611   }
 612   return 0;
 613 }
 614 
 615 # Is it a cycle closure edge?
 616 #
 617 # Notes:
 618 #   . Presence of VertexID2 in DFS path traversed for VertexID1 make it a cycle
 619 #     closure edge...
 620 #
 621 sub _IsCycleClosureEdge {
 622   my($This, $VertexID1, $VertexID2) = @_;
 623 
 624   if (!exists $This->{VerticesPaths}{$VertexID1}) {
 625     return 0;
 626   }
 627   my($Path);
 628   for $Path (@{$This->{VerticesPaths}{$VertexID1}}) {
 629     if (($Path =~ /-$VertexID2-/ || $Path =~ /^$VertexID2-/ || $Path =~ /-$VertexID2$/)) {
 630       return 1;
 631     }
 632   }
 633   return 0;
 634 }
 635 
 636 # Search paths starting from a specified vertex with no sharing of edges in paths traversed.
 637 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
 638 # completing the cycle.
 639 #
 640 sub PerformPathsSearch {
 641   my($This, $StartVertexID, $AllowCycles) = @_;
 642 
 643   # Make sure start vertex is defined...
 644   if (!defined $StartVertexID) {
 645     carp "Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Start vertex  must be specified...";
 646     return undef;
 647   }
 648 
 649   # Make sure start vertex is valid...
 650   if (!$This->{Graph}->HasVertex($StartVertexID)) {
 651     carp "Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist...";
 652     return undef;
 653   }
 654 
 655   if (!defined $AllowCycles) {
 656     $AllowCycles = 1;
 657   }
 658 
 659   # Perform paths search...
 660   return $This->_PerformPathsSearch("AllLengths", $StartVertexID, $AllowCycles);
 661 }
 662 
 663 # Search paths starting from a specified vertex with length upto a specified length
 664 # with no sharing of edges in paths traversed...
 665 #
 666 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
 667 # completing the cycle.
 668 #
 669 sub PerformPathsSearchWithLengthUpto {
 670   my($This, $StartVertexID, $Length, $AllowCycles) = @_;
 671 
 672   # Make sure both start vertex and length are defined...
 673   if (!defined $StartVertexID) {
 674     carp "Warning: ${ClassName}->PerformPathsSearchWithLengthUpto: No paths search performed: Start vertex  must be specified...";
 675     return undef;
 676   }
 677   if (!defined $Length) {
 678     carp "Warning: ${ClassName}->PerformPathsSearchWithLengthUpto: No paths search performed: Length must be specified...";
 679     return undef;
 680   }
 681 
 682   if (!defined $AllowCycles) {
 683     $AllowCycles = 1;
 684   }
 685 
 686   # Make sure both start vertex and length are valid...
 687   if (!$This->{Graph}->HasVertex($StartVertexID)) {
 688     carp "Warning: ${ClassName}->PerformPathsSearchWithLengthUpto: No paths search performed: Vertex $StartVertexID doesn't exist...";
 689     return undef;
 690   }
 691 
 692   if ($Length < 1) {
 693     carp "Warning: ${ClassName}->PerformPathsSearchWithLengthUpto: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1...";
 694     return undef;
 695   }
 696 
 697   # Perform paths search...
 698   return $This->_PerformPathsSearch("LengthUpto", $StartVertexID, $AllowCycles, $Length);
 699 }
 700 
 701 # Search all paths starting from a specified vertex with sharing of edges in paths traversed...
 702 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
 703 # completing the cycle.
 704 #
 705 sub PerformAllPathsSearch {
 706   my($This, $StartVertexID, $AllowCycles) = @_;
 707 
 708   # Make sure start vertex is defined...
 709   if (!defined $StartVertexID) {
 710     carp "Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Start vertex  must be specified...";
 711     return undef;
 712   }
 713 
 714   # Make sure start vertex is valid...
 715   if (!$This->{Graph}->HasVertex($StartVertexID)) {
 716     carp "Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist...";
 717     return undef;
 718   }
 719 
 720   if (!defined $AllowCycles) {
 721     $AllowCycles = 1;
 722   }
 723 
 724   # Perform paths search...
 725   return $This->_PerformAllPathsSearch("AllLengths", $StartVertexID, $AllowCycles);
 726 }
 727 
 728 # Search all paths starting from a specified vertex with length upto a specified length with sharing of
 729 # edges in paths traversed.
 730 #
 731 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
 732 # completing the cycle.
 733 #
 734 sub PerformAllPathsSearchWithLengthUpto {
 735   my($This, $StartVertexID, $Length, $AllowCycles) = @_;
 736 
 737   # Make sure both start vertex and length are defined...
 738   if (!defined $StartVertexID) {
 739     carp "Warning: ${ClassName}->PerformAllPathsSearchWithLengthUpto: No paths search performed: Start vertex  must be specified...";
 740     return undef;
 741   }
 742   if (!defined $Length) {
 743     carp "Warning: ${ClassName}->PerformAllPathsSearchWithLengthUpto: No paths search performed: Length must be specified...";
 744     return undef;
 745   }
 746 
 747   if (!defined $AllowCycles) {
 748     $AllowCycles = 1;
 749   }
 750 
 751   # Make sure both start vertex and length are valid...
 752   if (!$This->{Graph}->HasVertex($StartVertexID)) {
 753     carp "Warning: ${ClassName}->PerformAllPathsSearchWithLengthUpto: No paths search performed: Vertex $StartVertexID doesn't exist...";
 754     return undef;
 755   }
 756 
 757   if ($Length < 1) {
 758     carp "Warning: ${ClassName}->PerformAllPathsSearchWithLengthUpto: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1...";
 759     return undef;
 760   }
 761 
 762   # Perform paths search...
 763   return $This->_PerformAllPathsSearch("LengthUpto", $StartVertexID, $AllowCycles, $Length);
 764 }
 765 
 766 # Search paths between two vertices...
 767 #
 768 sub PerformPathsSearchBetween {
 769   my($This, $StartVertexID, $EndVertexID) = @_;
 770 
 771   # Make sure start and end vertices are defined...
 772   if (!defined $StartVertexID) {
 773     carp "Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: Start vertex  must be specified...";
 774     return undef;
 775   }
 776   if (!defined $EndVertexID) {
 777     carp "Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: EndVertex vertex  must be specified...";
 778     return undef;
 779   }
 780   # Make sure start and end vertices are valid...
 781   if (!$This->{Graph}->HasVertex($StartVertexID)) {
 782     carp "Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $StartVertexID doesn't exist...";
 783     return undef;
 784   }
 785   if (!$This->{Graph}->HasVertex($EndVertexID)) {
 786     carp "Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $EndVertexID doesn't exist...";
 787     return undef;
 788   }
 789 
 790   # Perform paths search...
 791   return $This->_PerformPathsSearchBetween($StartVertexID, $EndVertexID);
 792 }
 793 
 794 # Search paths starting from root vertex with no sharing of edges...
 795 #
 796 # Notes:
 797 #   . Possible paths searche modes are: DFSPathsWithLimit, DFSPaths. And each
 798 #     of these modes supports any combination of two options: CommonEdges, Cycles.
 799 #     Default for CommonEdges - No; Cycles - No.
 800 #
 801 sub _PerformPathsSearch {
 802   my($This, $Mode, $RootVertexID, $AllowCycles, $Length) = @_;
 803 
 804   # Perform DFS path search...
 805 
 806   $This->{TraversalMode} = 'Path';
 807 
 808   if ($Mode =~ /^LengthUpto$/i) {
 809     my($DepthLimit);
 810 
 811     $DepthLimit = $Length - 1;
 812     $This->{TraversalType} = 'DFSWithLimit';
 813     $This->{DepthLimit} = $DepthLimit;
 814   }
 815   else {
 816     $This->{TraversalType} = 'DFS';
 817   }
 818   if (defined $RootVertexID) {
 819     $This->{RootVertex} = $RootVertexID;
 820   }
 821 
 822   $This->{AllowPathCycles} = $AllowCycles;
 823 
 824   # Perform search...
 825   $This->_TraverseGraph();
 826 
 827   # Make sure traversal did get the root vertex...
 828   if (!exists $This->{VerticesDepth}{$RootVertexID}) {
 829     return $This;
 830   }
 831   push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearch();
 832 
 833   return $This;
 834 }
 835 
 836 # Search all paths starting from root vertex with sharing of edges...
 837 #
 838 sub _PerformAllPathsSearch {
 839   my($This, $Mode, $RootVertexID, $AllowCycles, $Length) = @_;
 840 
 841   # Perform DFS path search...
 842 
 843   $This->{TraversalMode} = 'AllPaths';
 844 
 845   if ($Mode =~ /^LengthUpto$/i) {
 846     my($DepthLimit);
 847 
 848     $DepthLimit = $Length - 1;
 849     $This->{TraversalType} = 'DFSWithLimit';
 850     $This->{DepthLimit} = $DepthLimit;
 851   }
 852   else {
 853     $This->{TraversalType} = 'DFS';
 854   }
 855   $This->{RootVertex} = $RootVertexID;
 856   $This->{AllowPathCycles} = $AllowCycles;
 857 
 858   # Traverse all paths search using DFS search...
 859   $This->_TraverseAllPathsInGraph();
 860 
 861   return $This;
 862 }
 863 
 864 # Travese all paths in graph starting from a specified root vertex...
 865 #
 866 sub _TraverseAllPathsInGraph {
 867   my($This) = @_;
 868 
 869   if ($This->{TraversalMode} !~ /^AllPaths$/i) {
 870     return $This;
 871   }
 872   my($CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath);
 873 
 874   $CurrentVertexID = $This->{RootVertex};
 875   $PredecessorVertexID = $CurrentVertexID;
 876   $CurrentDepth = 0;
 877   $CurrentPath = "$CurrentVertexID";
 878 
 879   $This->_TraverseAllPaths($CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath);
 880 
 881   push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearch();
 882 
 883   return $This;
 884 }
 885 
 886 # Traverse and collect all paths recuresively..
 887 #
 888 sub _TraverseAllPaths {
 889   my($This, $CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath) = @_;
 890 
 891   # Save path traversed for current vertex..
 892   if (!exists $This->{VerticesPaths}{$CurrentVertexID}) {
 893     @{$This->{VerticesPaths}{$CurrentVertexID}} = ();
 894   }
 895   push @{$This->{VerticesPaths}{$CurrentVertexID}}, $CurrentPath;
 896 
 897   $CurrentDepth++;
 898   if (exists $This->{DepthLimit}) {
 899     if ($CurrentDepth > $This->{DepthLimit}) {
 900       # Nothing more to do...
 901       return $This;
 902     }
 903   }
 904   my($NeighborVertexID, $NewPath);
 905 
 906   NEIGHBOR: for $NeighborVertexID ($This->{Graph}->GetNeighbors($CurrentVertexID)) {
 907     if ($NeighborVertexID == $PredecessorVertexID) {
 908       next NEIGHBOR;
 909     }
 910     if ($This->_IsVertexInTraversedPath($NeighborVertexID, $CurrentPath)) {
 911       # It's a cycle...
 912       if ($This->{AllowPathCycles}) {
 913 	$NewPath = "${CurrentPath}-${NeighborVertexID}";
 914 	if (!exists $This->{VerticesPaths}{$NeighborVertexID}) {
 915 	  @{$This->{VerticesPaths}{$NeighborVertexID}} = ();
 916 	}
 917 	push @{$This->{VerticesPaths}{$NeighborVertexID}}, $NewPath;
 918       }
 919       next NEIGHBOR;
 920     }
 921     $NewPath = "${CurrentPath}-${NeighborVertexID}";
 922     $This->_TraverseAllPaths($NeighborVertexID, $CurrentVertexID, $CurrentDepth, $NewPath);
 923   }
 924   return $This;
 925 }
 926 
 927 # Is vertex already in traversed path?
 928 #
 929 sub _IsVertexInTraversedPath {
 930   my($This, $VertexID, $Path) = @_;
 931 
 932   return ($Path =~ /-$VertexID-/ || $Path =~ /^$VertexID-/ || $Path =~ /-$VertexID$/) ? 1 : 0;
 933 }
 934 
 935 # Collect paths traversed during Path TraversalMode...
 936 #
 937 sub _CollectPathsTraversedDuringPathsSearch {
 938   my($This) = @_;
 939   my($VertexID, @Paths, @SortedPaths);
 940 
 941   @Paths = (); @SortedPaths = ();
 942 
 943   # Create path objects from path vertex strings...
 944   for $VertexID (keys %{$This->{VerticesPaths}}) {
 945     push @Paths, map { new Path(split /-/, $_) } @{$This->{VerticesPaths}{$VertexID}};
 946   }
 947 
 948   # Sort paths in ascending order of lengths...
 949   push @SortedPaths, sort { $a->GetLength() <=> $b->GetLength() } @Paths;
 950 
 951   return @SortedPaths;
 952 }
 953 
 954 # Collect paths...
 955 #
 956 sub _CollectPathsTraversedDuringVertexSearch {
 957   my($This, $RootVertexID) = @_;
 958   my($Depth, @Paths, @VerticesAtDepth);
 959   @Paths = ();
 960 
 961   # Get vertices at specific depths...
 962   @VerticesAtDepth = ();
 963   @VerticesAtDepth = $This->_CollectVerticesAtSpecificDepths();
 964   if (!@VerticesAtDepth) {
 965     return @Paths;
 966   }
 967 
 968   # Make sure search found only one root vertex and it corresponds to
 969   # what was specified...
 970   $Depth = 0;
 971   if ((@{$VerticesAtDepth[$Depth]} > 1) || ($VerticesAtDepth[$Depth][0] != $RootVertexID)) {
 972     carp "Warning: ${ClassName}->_PerformPathsSearch: No paths found: Root vertex, $VerticesAtDepth[$Depth][0], identified by paths traversal doen't match specified root vertex $RootVertexID...";
 973     return @Paths;
 974   }
 975 
 976   # Setup root vertex at depth 0. And set its path...
 977   my($Path, $VertexID, $SuccessorVertexID, @VertexIDs, %PathAtVertex);
 978   %PathAtVertex = ();
 979   $PathAtVertex{$RootVertexID} = new Path($RootVertexID);
 980 
 981   for $Depth (0 .. $#VerticesAtDepth) {
 982     # Go over all vertices at current depth...
 983     VERTEX: for $VertexID (@{$VerticesAtDepth[$Depth]}) {
 984       if (!exists $This->{VerticesSuccessors}{$VertexID}) {
 985 	next VERTEX;
 986       }
 987       # Get vertices for current path...
 988       @VertexIDs = ();
 989       push @VertexIDs, $PathAtVertex{$VertexID}->GetVertices;
 990 
 991       # Expand path to successor vertex found during traversal...
 992       for $SuccessorVertexID (@{$This->{VerticesSuccessors}{$VertexID}}) {
 993 	$Path = new Path(@VertexIDs);
 994 	$Path->AddVertex($SuccessorVertexID);
 995 	$PathAtVertex{$SuccessorVertexID} = $Path;
 996       }
 997     }
 998   }
 999   # Sort paths in ascending order of lengths...
1000   push @Paths, sort { $a->GetLength() <=> $b->GetLength() } values %PathAtVertex;
1001 
1002   return @Paths;
1003 }
1004 
1005 # Collect vertices at specific depths. Depth values start from 0...
1006 #
1007 sub _CollectVerticesAtSpecificDepths {
1008   my($This) = @_;
1009   my($VertexID, $Depth, @VerticesAtDepth);
1010 
1011   @VerticesAtDepth = ();
1012   while (($VertexID, $Depth) = each %{$This->{VerticesDepth}}) {
1013     push @{$VerticesAtDepth[$Depth]}, $VertexID;
1014   }
1015   return @VerticesAtDepth;
1016 }
1017 
1018 # Search paths between two vertices...
1019 #
1020 sub _PerformPathsSearchBetween {
1021   my($This, $RootVertexID, $TargetVertexID) = @_;
1022   my($DepthLimit);
1023 
1024   # Perform a targeted DFS search...
1025   $DepthLimit = undef;
1026   $This->_PerformVertexSearch("DFS", $RootVertexID, $DepthLimit, $TargetVertexID);
1027 
1028   my($Path);
1029   $Path = $This->_CollectPathBetween($RootVertexID, $TargetVertexID);
1030 
1031   if (defined $Path) {
1032     push  @{$This->{Paths}}, $Path;
1033   }
1034   return $This;
1035 }
1036 
1037 # Collect path between root and target vertex after the search...
1038 #
1039 sub _CollectPathBetween {
1040   my($This, $RootVertexID, $TargetVertexID) = @_;
1041 
1042   # Does a path from root to target vertex exist?
1043   if (!(exists($This->{VerticesRoots}{$TargetVertexID}) && ($This->{VerticesRoots}{$TargetVertexID} == $RootVertexID))) {
1044     return undef;
1045   }
1046 
1047   # Add target vertex ID path vertices...
1048   my($VertexID, $Path, @VertexIDs);
1049   @VertexIDs = ();
1050   $VertexID = $TargetVertexID;
1051   push @VertexIDs, $VertexID;
1052 
1053   # Backtrack to root vertex ID...
1054   while ($This->{VerticesPredecessors}{$VertexID} != $VertexID) {
1055     $VertexID = $This->{VerticesPredecessors}{$VertexID};
1056     push @VertexIDs, $VertexID;
1057   }
1058 
1059   # Create path from target to root and reverse it...
1060   $Path = new Path(@VertexIDs);
1061   $Path->Reverse();
1062 
1063   return $Path;
1064 }
1065 
1066 # Search vertices around specified root vertex with in specific neighborhood radius...
1067 #
1068 sub PerformNeighborhoodVerticesSearchWithRadiusUpto {
1069   my($This, $StartVertexID, $Radius) = @_;
1070 
1071   # Make sure both start vertex and radius are defined...
1072   if (!defined $StartVertexID) {
1073     carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Start vertex  must be specified...";
1074     return undef;
1075   }
1076   if (!defined $Radius) {
1077     carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Radius must be specified...";
1078     return undef;
1079   }
1080 
1081   # Make sure both start vertex and length are valid...
1082   if (!$This->{Graph}->HasVertex($StartVertexID)) {
1083     carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Vertex $StartVertexID doesn't exist...";
1084     return undef;
1085   }
1086   if ($Radius < 0) {
1087     carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Specified radius, $Radius, must be a positive integer...";
1088     return undef;
1089   }
1090 
1091   # Perform vertices search...
1092   return $This->_PerformNeighborhoodVerticesSearch("RadiusUpto", $StartVertexID, $Radius);
1093 }
1094 
1095 # Search vertices around specified root vertex...
1096 #
1097 sub PerformNeighborhoodVerticesSearch {
1098   my($This, $StartVertexID) = @_;
1099 
1100   # Make sure start vertex is defined...
1101   if (!defined $StartVertexID) {
1102     carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Start vertex  must be specified...";
1103     return undef;
1104   }
1105 
1106   # Make sure start vertex is valid...
1107   if (!$This->{Graph}->HasVertex($StartVertexID)) {
1108     carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Vertex $StartVertexID doesn't exist...";
1109     return undef;
1110   }
1111   # Perform vertices search...
1112   return $This->_PerformNeighborhoodVerticesSearch("AllRadii", $StartVertexID);
1113 }
1114 
1115 # Search vertices at successive neighborhood radii levels...
1116 #
1117 sub _PerformNeighborhoodVerticesSearch {
1118   my($This, $Mode, $RootVertexID, $Radius) = @_;
1119 
1120   # Perform BFS search...
1121   if ($Mode =~ /^RadiusUpto$/i) {
1122     my($DepthLimit);
1123     $DepthLimit = $Radius;
1124     $This->_PerformVertexSearch("BFSWithLimit", $RootVertexID, $DepthLimit)
1125   }
1126   elsif ($Mode =~ /^(AllRadii)$/i) {
1127     $This->_PerformVertexSearch("BFS", $RootVertexID)
1128   }
1129   # Make sure traversal did get the root vertex...
1130   if (!exists $This->{VerticesDepth}{$RootVertexID}) {
1131     return $This;
1132   }
1133   push @{$This->{VerticesNeighborhoods}}, $This->_CollectVerticesAtSpecificDepths();
1134 
1135   return $This;
1136 }
1137 
1138 # Get orderded list of vertices after DFS/BFS search...
1139 #
1140 sub GetVertices {
1141   my($This) = @_;
1142 
1143   return wantarray ? @{$This->{Vertices}} : scalar @{$This->{Vertices}};
1144 }
1145 
1146 # Get a hash list containing vertex and root vertex as key/value pair for all vertices
1147 # ordered using DFS/BFS search available via GetVertices method...
1148 #
1149 sub GetVerticesRoots {
1150   my($This) = @_;
1151 
1152   return %{$This->{VerticesRoots}};
1153 }
1154 
1155 # Get a list containing lists of vertices in connected components of graph after DFS/BFS
1156 # search...
1157 #
1158 # Note:
1159 #   . List is sorted in descending order of number of vertices in each connected component.
1160 #
1161 sub GetConnectedComponentsVertices {
1162   my($This) = @_;
1163   my($VertexID, $VertexRoot, @ConnectedVertices, %VerticesAtRoot);
1164 
1165   @ConnectedVertices = ();
1166   %VerticesAtRoot = ();
1167   for $VertexID (@{$This->{Vertices}}) {
1168     $VertexRoot = $This->{VerticesRoots}{$VertexID};
1169     if (!exists $VerticesAtRoot{$VertexRoot}) {
1170       @{$VerticesAtRoot{$VertexRoot}} = ();
1171     }
1172     push @{$VerticesAtRoot{$VertexRoot}}, $VertexID