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