1 package CyclesDetection;
   2 #
   3 # $RCSfile: CyclesDetection.pm,v $
   4 # $Date: 2011/12/16 00:05:32 $
   5 # $Revision: 1.18 $
   6 #
   7 # Author: Manish Sud <msud@san.rr.com>
   8 #
   9 # Copyright (C) 2004-2012 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 Graph;
  33 use Graph::Path;
  34 use Graph::PathGraph;
  35 use BitVector;
  36 
  37 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
  38 
  39 @ISA = qw(Exporter);
  40 @EXPORT = qw();
  41 @EXPORT_OK = qw();
  42 
  43 %EXPORT_TAGS = (all  => [@EXPORT, @EXPORT_OK]);
  44 
  45 # Setup class variables...
  46 my($ClassName);
  47 _InitializeClass();
  48 
  49 # Overload Perl functions...
  50 use overload '""' => 'StringifyCyclesDetection';
  51 
  52 # Class constructor...
  53 sub new {
  54   my($Class, $Graph) = @_;
  55 
  56   # Initialize object...
  57   my $This = {};
  58   bless $This, ref($Class) || $Class;
  59   $This->_InitializeCyclesDetection($Graph);
  60 
  61   return $This;
  62 }
  63 
  64 # Initialize object data...
  65 sub _InitializeCyclesDetection {
  66   my($This, $Graph) = @_;
  67 
  68   $This->{Graph} = $Graph;
  69 
  70   # Cycles list...
  71   @{$This->{AllCyclicPaths}} = ();
  72 
  73   # Cyclic paths which are not part of any other cycle...
  74   @{$This->{IndependentCyclicPaths}} = ();
  75 
  76   return $This;
  77 }
  78 
  79 # Initialize class ...
  80 sub _InitializeClass {
  81   #Class name...
  82   $ClassName = __PACKAGE__;
  83 }
  84 
  85 # Detect all cycles in graph...
  86 #
  87 sub DetectCycles {
  88   my($This) = @_;
  89 
  90   return $This->DetectCyclesUsingCollapsingPathGraphMethodology();
  91 }
  92 
  93 # Detect all cycles in the graph using collapsing path graph [Ref 31] methodology...
  94 #
  95 # Note:
  96 #   . For topologically complex graphs containing large number of cycles,
  97 #     CollapseVertexAndCollectCyclicPathsDetectCycles method implemented in
  98 #     PathGraph can time out in which case no cycles are detected or
  99 #     assigned.
 100 #
 101 sub DetectCyclesUsingCollapsingPathGraphMethodology {
 102   my($This) = @_;
 103   my($PathGraph);
 104 
 105   # Create a path graph...
 106   $PathGraph = new PathGraph($This->{Graph});
 107 
 108   # For a vertex to be in a cycle, its degree must be >=2. So delete vertices recursively
 109   # till all vertices with degree less than 2 have been deleted...
 110   $PathGraph->DeleteVerticesWithDegreeLessThan(2);
 111 
 112   # Setup a VertexID to index map usage during retrieval of independent cycles to
 113   # avoid going over all vertices in all cylic paths later...
 114   my($VertexIDsToIndicesRef, $LargestVertexIndex);
 115   ($VertexIDsToIndicesRef, $LargestVertexIndex) = $This->_SetupVertexIDsToIndicesMap($PathGraph);
 116 
 117   # Recursively collapse vertices with lowest degree...
 118   my($VertexID, $CycleVertexID);
 119   while ($VertexID = $PathGraph->GetVertexWithSmallestDegree()) {
 120       if (!$PathGraph->CollapseVertexAndCollectCyclicPaths($VertexID)) {
 121         # Cycles detection didn't finish...
 122         return undef;
 123       }
 124   }
 125 
 126   # Get detected cycles and save 'em sorted by size...
 127   push @{$This->{AllCyclicPaths}}, sort { $a->GetLength() <=> $b->GetLength() } $PathGraph->GetCyclicPaths();
 128 
 129   # Retrieve independent cyclic paths...
 130   return $This->_RetrieveIndependentCycles($VertexIDsToIndicesRef, $LargestVertexIndex);
 131 }
 132 
 133 # Retrieve and save independent cyclic paths...
 134 #
 135 # Set of independent cycles identified using this method doesn't correspond to basis set of
 136 # rings or smallest set of smallest rings (SSSR) [ Refs 29-30 ]; instead, set of cycles identified
 137 # as independent cycles simply correspond to cycles which contain no other cycle as their
 138 # subcycles and can't be described as linear combination of smaller cycles. And it also happen
 139 # to contain all the rings in basis set of rings and SSSR. In other words, it's a superset of basis set
 140 # of cycles and SSSR. For example, six four membered cycles are identified for cubane which is one
 141 # more than the basis set of cycles.
 142 #
 143 sub _RetrieveIndependentCycles {
 144   my($This, $VertexIDsToIndicesRef, $LargestVertexIndex) = @_;
 145 
 146   # Only 1 or 0 cyclic paths...
 147   if (@{$This->{AllCyclicPaths}} <= 1) {
 148     push @{$This->{IndependentCyclicPaths}}, @{$This->{AllCyclicPaths}};
 149     return $This;
 150   }
 151 
 152   # Setup bit vectors for each cyclic path with size of each bit vector corresponding to
 153   # maximum vertex index plus one...
 154   my($CyclicPath, $BitVectorSize, $BitVector, @BitNums, @CyclicPathBitVectors);
 155 
 156   @CyclicPathBitVectors = ();
 157   $BitVectorSize = $LargestVertexIndex;
 158 
 159   # Set bits corresponding to VertexIDs using their indices...
 160   for $CyclicPath (@{$This->{AllCyclicPaths}}) {
 161     $BitVector = new BitVector($BitVectorSize);
 162     @BitNums = ();
 163     @BitNums = map { $VertexIDsToIndicesRef->{$_} } $CyclicPath->GetVertices();
 164     $BitVector->SetBits(@BitNums);
 165     push @CyclicPathBitVectors, $BitVector;
 166   }
 167 
 168   # First smallest cyclic path always ends up as an independent cyclic path...
 169   push @{$This->{IndependentCyclicPaths}}, $This->{AllCyclicPaths}[0];
 170 
 171   # Retrieve other independent cyclic paths...
 172   my($CurrentIndex, $PreviousIndex, $CurrentCyclicPath, $PreviousCyclicPath, $CurrentPathLength, $PreviousPathLength, $CurrentBitVector, $PreviousBitVector, $CurrentAndPreviousBitVectpor, $AllPreviousSmallerPathsBitVector, $AndBitVector, %SmallerPathAlreadyAdded, %SkipPath);
 173 
 174   %SkipPath = ();
 175   %SmallerPathAlreadyAdded = ();
 176   $AllPreviousSmallerPathsBitVector = new BitVector($BitVectorSize);
 177 
 178   CURRENT: for $CurrentIndex (1 .. $#{$This->{AllCyclicPaths}}) {
 179     if (exists $SkipPath{$CurrentIndex}) {
 180       next CURRENT;
 181     }
 182     $CurrentCyclicPath = $This->{AllCyclicPaths}[$CurrentIndex];
 183     $CurrentBitVector = $CyclicPathBitVectors[$CurrentIndex];
 184     $CurrentPathLength = $CurrentCyclicPath->GetLength();
 185 
 186     PREVIOUS: for $PreviousIndex (0 .. ($CurrentIndex - 1)) {
 187       if (exists $SkipPath{$PreviousIndex}) {
 188         next PREVIOUS;
 189       }
 190       $PreviousCyclicPath = $This->{AllCyclicPaths}[$PreviousIndex];
 191       $PreviousBitVector = $CyclicPathBitVectors[$PreviousIndex];
 192 
 193       # Is previous path a subset of current path?
 194       $CurrentAndPreviousBitVectpor = $PreviousBitVector &  $CurrentBitVector;
 195       if ($PreviousBitVector->GetNumOfSetBits() == $CurrentAndPreviousBitVectpor->GetNumOfSetBits()) {
 196         # Current path doesn't qualify an independent path...
 197         $SkipPath{$CurrentIndex} = 1;
 198         next CURRENT;
 199       }
 200 
 201       $PreviousPathLength = $PreviousCyclicPath->GetLength();
 202       if ($PreviousPathLength < $CurrentPathLength) {
 203         # Mark cycle vertices seen in cyclic paths with length smaller than current path...
 204         if (! exists $SmallerPathAlreadyAdded{$PreviousIndex}) {
 205           $SmallerPathAlreadyAdded{$PreviousIndex} = 1;
 206           $AllPreviousSmallerPathsBitVector = $AllPreviousSmallerPathsBitVector | $PreviousBitVector;
 207         }
 208       }
 209     }
 210     if ($AllPreviousSmallerPathsBitVector->GetNumOfSetBits()) {
 211       # Is current path a linear combination of smaller paths?
 212       $AndBitVector = $AllPreviousSmallerPathsBitVector &  $CurrentBitVector;
 213       if ($CurrentBitVector->GetNumOfSetBits() == $AndBitVector->GetNumOfSetBits()) {
 214         # Current path doesn't qualify an independent path...
 215         $SkipPath{$CurrentIndex} = 1;
 216         next CURRENT;
 217       }
 218     }
 219     # It's an independent cyclic path...
 220     push @{$This->{IndependentCyclicPaths}}, $CurrentCyclicPath;
 221   }
 222   return $This;
 223 }
 224 
 225 # Setup a VertexID to index map...
 226 #
 227 sub _SetupVertexIDsToIndicesMap {
 228   my($This, $PathGraph) = @_;
 229   my($LargestVertexIndex, @VertexIDs, %VertexIDsMap);
 230 
 231   %VertexIDsMap = (); @VertexIDs = (); $LargestVertexIndex = 0;
 232 
 233   @VertexIDs = $PathGraph->GetVertices();
 234   if (! @VertexIDs) {
 235     return (\%VertexIDsMap, $LargestVertexIndex);
 236   }
 237   @VertexIDsMap{ @VertexIDs } = (0 .. $#VertexIDs);
 238   $LargestVertexIndex = scalar @VertexIDs;
 239 
 240   return (\%VertexIDsMap, $LargestVertexIndex);
 241 }
 242 
 243 # Return an array containing references to cyclic paths or number of cylic paths...
 244 #
 245 sub GetAllCyclicPaths {
 246   my($This) = @_;
 247 
 248   return wantarray ? @{$This->{AllCyclicPaths}} : scalar @{$This->{AllCyclicPaths}};
 249 }
 250 
 251 # Get cyclic paths which are independent. In otherwords, cycles which don't contain any other
 252 # cycle as their subset...
 253 #
 254 sub GetIndependentCyclicPaths {
 255   my($This) = @_;
 256 
 257   return wantarray ? @{$This->{IndependentCyclicPaths}} : scalar @{$This->{IndependentCyclicPaths}};
 258 }
 259 
 260 # Return a string containg data for CyclesDetection object...
 261 sub StringifyCyclesDetection {
 262   my($This) = @_;
 263   my($CyclesDetectionString, $CyclesCount, $CyclicPath);
 264 
 265   $CyclesCount = @{$This->{AllCyclicPaths}};
 266   $CyclesDetectionString = "AllCycles: Count - $CyclesCount";
 267   for $CyclicPath (@{$This->{AllCyclicPaths}}) {
 268     $CyclesDetectionString .= "; Cycle: " . join('-', $CyclicPath->GetVertices());
 269   }
 270 
 271   $CyclesCount = @{$This->{IndependentCyclicPaths}};
 272   $CyclesDetectionString .= "\nIndependentCycles: Count - $CyclesCount";
 273   for $CyclicPath (@{$This->{IndependentCyclicPaths}}) {
 274     $CyclesDetectionString .= "; Cycle: " . join('-', $CyclicPath->GetVertices());
 275   }
 276 
 277   return $CyclesDetectionString;
 278 }
 279 
 280 # Return a reference to new cycle detection object...
 281 sub Copy {
 282   my($This) = @_;
 283   my($NewCyclesDetection);
 284 
 285   $NewCyclesDetection = Storable::dclone($This);
 286 
 287   return $NewCyclesDetection;
 288 }
 289