1 package Graph::PathGraph;
   2 #
   3 # File: PathGraph.pm
   4 # Author: Manish Sud <msud@san.rr.com>
   5 #
   6 # Copyright (C) 2024 Manish Sud. All rights reserved.
   7 #
   8 # This file is part of MayaChemTools.
   9 #
  10 # MayaChemTools is free software; you can redistribute it and/or modify it under
  11 # the terms of the GNU Lesser General Public License as published by the Free
  12 # Software Foundation; either version 3 of the License, or (at your option) any
  13 # later version.
  14 #
  15 # MayaChemTools is distributed in the hope that it will be useful, but without
  16 # any warranty; without even the implied warranty of merchantability of fitness
  17 # for a particular purpose.  See the GNU Lesser General Public License for more
  18 # details.
  19 #
  20 # You should have received a copy of the GNU Lesser General Public License
  21 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
  22 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
  23 # Boston, MA, 02111-1307, USA.
  24 #
  25 
  26 use strict;
  27 use Carp;
  28 use Exporter;
  29 use Storable ();
  30 use Scalar::Util ();
  31 use Graph;
  32 use Graph::Path;
  33 
  34 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
  35 
  36 @ISA = qw(Graph Exporter);
  37 @EXPORT = qw(IsPathGraph);
  38 @EXPORT_OK = qw();
  39 
  40 %EXPORT_TAGS = (all  => [@EXPORT, @EXPORT_OK]);
  41 
  42 # Setup class variables...
  43 my($ClassName, $PathsPropertyName, $CyclicPathsPropertyName);
  44 _InitializeClass();
  45 
  46 # Overload Perl functions...
  47 use overload '""' => 'StringifyPathGraph';
  48 
  49 # Class constructor...
  50 sub new {
  51   my($Class, $Graph) = @_;
  52 
  53   # Initialize object...
  54   my $This = $Class->SUPER::new();
  55   bless $This, ref($Class) || $Class;
  56   $This->_InitializePathGraph($Graph);
  57 
  58   $This->_ConvertGraphIntoPathGraph($Graph);
  59 
  60   return $This;
  61 }
  62 
  63 # Initialize object data...
  64 sub _InitializePathGraph {
  65   my($This, $Graph) = @_;
  66 
  67   if (!(defined($Graph) && Graph::IsGraph($Graph))) {
  68     croak "Error: ${ClassName}->new: PathGraph object can't be instantiated without a Graph object...";
  69   }
  70 
  71   $This->{Graph} = $Graph;
  72 
  73   # Maximum time allowed for cycles detection during collapse vertex cycles detection
  74   # methodology in seconds...
  75   $This->{MaxAllowedTime} = 30;
  76 
  77   # Starting time for cycles detection during collapse vertex cycles detection
  78   # methodology...
  79   $This->{StartTime} = time;
  80 
  81   return $This;
  82 }
  83 
  84 # Initialize class ...
  85 sub _InitializeClass {
  86   #Class name...
  87   $ClassName = __PACKAGE__;
  88 
  89   # Path edge property name...
  90   $PathsPropertyName = 'Paths';
  91 
  92   # Cyclic path vertex property name...
  93   $CyclicPathsPropertyName = 'CyclicPaths';
  94 }
  95 
  96 # Convert graph into a path graph...
  97 #
  98 sub _ConvertGraphIntoPathGraph {
  99   my($This, $Graph) = @_;
 100 
 101   # Copy graph vertices and edges without any associated properties data
 102   # from Graph to This: Graph properties data is available using Graph object reference
 103   # store in This object...
 104   #
 105   $Graph->CopyVerticesAndEdges($This);
 106 
 107   # . Attach Path property to each edge...
 108   #
 109   my($Index, $VertexID1, $VertexID2, $Path, @EdgesVertexIDs);
 110 
 111   @EdgesVertexIDs = ();
 112   @EdgesVertexIDs = $This->GetEdges();
 113   for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) {
 114     $VertexID1 = $EdgesVertexIDs[$Index]; $VertexID2 = $EdgesVertexIDs[$Index + 1];
 115     $Path = new Graph::Path($VertexID1, $VertexID2);
 116     my(@Paths) = ();
 117     push @Paths, $Path;
 118     $This->SetEdgeProperty($PathsPropertyName, \@Paths, $VertexID1, $VertexID2);
 119   }
 120   return $This;
 121 }
 122 
 123 # Collapse paths around a specified vertex by updating paths around the vertex
 124 # and adding any resulting cyclic paths to vertices attached to specified vertex.
 125 #
 126 # Notes:
 127 #   . Path object references are stored as a list attached to Paths property on edges.
 128 #     Usage of list allows multiple paths attached to the egde between a pair of vertices;
 129 #     Graph doesn't support multiple egdes between a pair of vertices.
 130 #
 131 #   . Cyclic path object references are stored as list on vertices as CyclicPaths graph property.
 132 #     List allows multiple Loop properties attached to a vertex.
 133 #
 134 #   . For topologically complex graphs containing large number of cycles, cycles detection algorithm
 135 #     [ Ref 31 ] as implemented implemented in CollapseVertexAndCollectCyclicPathsDetectCycles
 136 #     might not be able to find all the cycles in a reasonable amount of time and is designed to
 137 #     abandon cycles detection after MaxAllowedTime. Consequently, no cycles are detected
 138 #     or assigned.
 139 #
 140 sub CollapseVertexAndCollectCyclicPaths {
 141   my($This, $VertexID) = @_;
 142 
 143   if (!$This->HasVertex($VertexID)) {
 144     carp "Warning: ${ClassName}->CollapseVertexAndCollectCyclicPaths: Didn't collapse vertex $VertexID: Vertex $VertexID doesn't exist...";
 145     return undef;
 146   }
 147   # Collect all paths around specified VertexID by going over paths associated with its edges...
 148   my($Index, $EdgePathsRef, $EdgeVertexID1, $EdgeVertexID2, @Paths, @EdgesVertexIDs);
 149 
 150   @EdgesVertexIDs = ();
 151   @EdgesVertexIDs = $This->GetEdges($VertexID);
 152 
 153   @Paths = ();
 154   for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) {
 155     ($EdgeVertexID1, $EdgeVertexID2) = ($EdgesVertexIDs[$Index], $EdgesVertexIDs[$Index + 1]);
 156     $EdgePathsRef = $This->GetEdgeProperty($PathsPropertyName, $EdgeVertexID1, $EdgeVertexID2);
 157     push @Paths, @{$EdgePathsRef};
 158   }
 159 
 160   # Go over each pair of paths around the specified vertex, join paths and associate
 161   # joined path to appropriate edge...
 162   my($Index1, $Index2, $Path1, $Path2, $JoinedPath, $JoinedPathStartVertexID, $JoinedPathEndVertexID, @CommonVertices);
 163 
 164   for ($Index1 = 0; $Index1 < $#Paths; $Index1 +=1 ) {
 165     $Path1 = $Paths[$Index1];
 166 
 167     PATH2: for ($Index2 = $Index1 + 1; $Index2 <= $#Paths; $Index2 +=1 ) {
 168       $Path2 = $Paths[$Index2];
 169 
 170       # For JoinedPath to be valid cycle, Path1 and Path2 must have exactly two vertices in common.
 171       # Otherwise, joined path contains duplicate vertices besides the terminal vertices and
 172       # indicates a path from a different direction.
 173       #
 174       # For paths leading to cycles, it only makes sense to join paths with only one common vertex;
 175       # otherwise, it wouldn't lead to a cycle and can be ignored.
 176       #
 177       @CommonVertices = $Path1->GetCommonVertices($Path2);
 178       if (!(@CommonVertices <= 2 && ($CommonVertices[0] == $VertexID || $CommonVertices[1] == $VertexID))) {
 179         next PATH2;
 180       }
 181 
 182       $JoinedPath = $Path1->JoinAtVertex($Path2, $VertexID);
 183       ($JoinedPathStartVertexID, $JoinedPathEndVertexID) = $JoinedPath->GetTerminalVertices();
 184 
 185       if (!$JoinedPath->IsIndependentPath()) {
 186         next PATH2;
 187       }
 188 
 189       # Decide whether to give up or keep going...
 190       if ($This->_IsTimeToGiveUpCyclesDetection()) {
 191         warn "Warning: ${ClassName}->CollapseVertexAndCollectCyclicPaths: Cycles detection algorithm [ Ref 31 ] as implemented in the current release of MayaChemTools didn't finish with in the maximum allowed time of $This->{MaxAllowedTime} seconds; Cycles detection has been abandoned...";
 192         return undef;
 193       }
 194 
 195       if ($JoinedPathStartVertexID == $JoinedPathEndVertexID) {
 196         # It's a cycle. Attach it to the graph as CylicPaths property...
 197         if ($This->HasGraphProperty($CyclicPathsPropertyName)) {
 198           my($ExistingCyclicPathsRef);
 199           $ExistingCyclicPathsRef = $This->GetGraphProperty($CyclicPathsPropertyName);
 200           push @{$ExistingCyclicPathsRef}, $JoinedPath;
 201         }
 202         else {
 203           my(@NewCyclicPaths) = ();
 204           push @NewCyclicPaths, $JoinedPath;
 205           $This->SetGraphProperty($CyclicPathsPropertyName, \@NewCyclicPaths, $JoinedPathStartVertexID);
 206         }
 207       }
 208       else {
 209         if ($This->HasEdge($JoinedPathStartVertexID, $JoinedPathEndVertexID)) {
 210           # Append to the list of exisiting paths property of the edge...
 211           my($ExistingPathsRef);
 212           $ExistingPathsRef = $This->GetEdgeProperty($PathsPropertyName, $JoinedPathStartVertexID, $JoinedPathEndVertexID);
 213           push @{$ExistingPathsRef}, $JoinedPath;
 214         }
 215         else {
 216           # Create a new edge and associate path property...
 217           my(@NewPaths) = ();
 218           push @NewPaths, $JoinedPath;
 219           $This->AddEdge($JoinedPathStartVertexID, $JoinedPathEndVertexID);
 220           $This->SetEdgeProperty($PathsPropertyName, \@NewPaths, $JoinedPathStartVertexID, $JoinedPathEndVertexID);
 221         }
 222       }
 223     }
 224   }
 225   $This->DeleteVertex($VertexID);
 226 
 227   return $This;
 228 }
 229 
 230 # Decide whether to give up cycles detection using collapse vertex methodology...
 231 #
 232 sub _IsTimeToGiveUpCyclesDetection {
 233   my($This) = @_;
 234 
 235   return ((time - $This->{StartTime}) > $This->{MaxAllowedTime}) ? 1 : 0;
 236 }
 237 
 238 # Delete vertices with degree less than a specifed degree...
 239 #
 240 sub DeleteVerticesWithDegreeLessThan {
 241   my($This, $Degree) = @_;
 242   my($VertexID, @VertexIDs);
 243 
 244   while (@VertexIDs = $This->GetVerticesWithDegreeLessThan($Degree)) {
 245     for $VertexID (@VertexIDs) {
 246       $This->DeleteVertex($VertexID);
 247     }
 248   }
 249   return $This;
 250 }
 251 
 252 # Get paths associated with edges...
 253 #
 254 sub GetPaths {
 255   my($This) = @_;
 256   my($PathsRef, @Paths, @PathsList);
 257 
 258   @Paths = (); @PathsList = ();
 259   @PathsList = $This->GetEdgesProperty($PathsPropertyName);
 260   for $PathsRef (@PathsList) {
 261     push @Paths, @{$PathsRef};
 262   }
 263   return wantarray ? @Paths : scalar @Paths;
 264 }
 265 
 266 # Get paths associated with edges which make a cylce...
 267 #
 268 sub GetCyclicPaths {
 269   my($This) = @_;
 270   my($PathsRef, @Paths, @PathsList);
 271 
 272   @Paths = (); @PathsList = ();
 273   @PathsList = $This->GetGraphProperty($CyclicPathsPropertyName);
 274   PATHS: for $PathsRef (@PathsList) {
 275     if (!(defined($PathsRef) && @{$PathsRef})) {
 276       next PATHS;
 277     }
 278     push @Paths, @{$PathsRef};
 279   }
 280   return wantarray ? @Paths : scalar @Paths;
 281 }
 282 
 283 # Is it a path graph object?
 284 sub IsPathGraph ($) {
 285   my($Object) = @_;
 286 
 287   return _IsPathGraph($Object);
 288 }
 289 
 290 # Return a string containg data for PathGraph object...
 291 sub StringifyPathGraph {
 292   my($This) = @_;
 293   my($PathGraphString);
 294 
 295   $PathGraphString = 'PathGraph:' . $This->StringifyVerticesAndEdges() . '; ' . $This->StringifyProperties();
 296 
 297   return $PathGraphString;
 298 }
 299 
 300 # Is it a PathGraph object?
 301 sub _IsPathGraph {
 302   my($Object) = @_;
 303 
 304   return (Scalar::Util::blessed($Object) && $Object->isa($ClassName)) ? 1 : 0;
 305 }
 306