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