MayaChemTools

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