       1 package Graph::PathGraph;
       2 #
       3 # File: PathGraph.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 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