Mercurial > repos > deepakjadmin > mayatool3_test3
diff mayachemtools/docs/modules/html/code/CyclesDetection.html @ 0:73ae111cf86f draft
Uploaded
| author | deepakjadmin |
|---|---|
| date | Wed, 20 Jan 2016 11:55:01 -0500 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/mayachemtools/docs/modules/html/code/CyclesDetection.html Wed Jan 20 11:55:01 2016 -0500 @@ -0,0 +1,373 @@ +<html> +<head> +<title>MayaChemTools:Code:Graph::CyclesDetection.pm</title> +<meta http-equiv="content-type" content="text/html;charset=utf-8"> +<link rel="stylesheet" type="text/css" href="../../../css/MayaChemToolsCode.css"> +</head> +<body leftmargin="20" rightmargin="20" topmargin="10" bottommargin="10"> +<br/> +<center> +<a href="http://www.mayachemtools.org" title="MayaChemTools Home"><img src="../../../images/MayaChemToolsLogo.gif" border="0" alt="MayaChemTools"></a> +</center> +<br/> +<pre> +<a name="package-Graph::CyclesDetection-"></a> 1 <span class="k">package </span><span class="i">Graph::CyclesDetection</span><span class="sc">;</span> + 2 <span class="c">#</span> + 3 <span class="c"># $RCSfile: CyclesDetection.pm,v $</span> + 4 <span class="c"># $Date: 2015/02/28 20:49:06 $</span> + 5 <span class="c"># $Revision: 1.27 $</span> + 6 <span class="c">#</span> + 7 <span class="c"># Author: Manish Sud <msud@san.rr.com></span> + 8 <span class="c">#</span> + 9 <span class="c"># Copyright (C) 2015 Manish Sud. All rights reserved.</span> + 10 <span class="c">#</span> + 11 <span class="c"># This file is part of MayaChemTools.</span> + 12 <span class="c">#</span> + 13 <span class="c"># MayaChemTools is free software; you can redistribute it and/or modify it under</span> + 14 <span class="c"># the terms of the GNU Lesser General Public License as published by the Free</span> + 15 <span class="c"># Software Foundation; either version 3 of the License, or (at your option) any</span> + 16 <span class="c"># later version.</span> + 17 <span class="c">#</span> + 18 <span class="c"># MayaChemTools is distributed in the hope that it will be useful, but without</span> + 19 <span class="c"># any warranty; without even the implied warranty of merchantability of fitness</span> + 20 <span class="c"># for a particular purpose. See the GNU Lesser General Public License for more</span> + 21 <span class="c"># details.</span> + 22 <span class="c">#</span> + 23 <span class="c"># You should have received a copy of the GNU Lesser General Public License</span> + 24 <span class="c"># along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or</span> + 25 <span class="c"># write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,</span> + 26 <span class="c"># Boston, MA, 02111-1307, USA.</span> + 27 <span class="c">#</span> + 28 + 29 <span class="k">use</span> <span class="w">strict</span><span class="sc">;</span> + 30 <span class="k">use</span> <span class="w">Carp</span><span class="sc">;</span> + 31 <span class="k">use</span> <span class="w">Exporter</span><span class="sc">;</span> + 32 <span class="k">use</span> <span class="w">Graph</span><span class="sc">;</span> + 33 <span class="k">use</span> <span class="w">Graph::Path</span><span class="sc">;</span> + 34 <span class="k">use</span> <span class="w">Graph::PathGraph</span><span class="sc">;</span> + 35 <span class="k">use</span> <span class="w">BitVector</span><span class="sc">;</span> + 36 + 37 <span class="k">use</span> <span class="w">vars</span> <span class="q">qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS)</span><span class="sc">;</span> + 38 + 39 <span class="i">@ISA</span> = <span class="q">qw(Exporter)</span><span class="sc">;</span> + 40 <span class="i">@EXPORT</span> = <span class="q">qw()</span><span class="sc">;</span> + 41 <span class="i">@EXPORT_OK</span> = <span class="q">qw()</span><span class="sc">;</span> + 42 + 43 <span class="i">%EXPORT_TAGS</span> = <span class="s">(</span><span class="w">all</span> <span class="cm">=></span> <span class="s">[</span><span class="i">@EXPORT</span><span class="cm">,</span> <span class="i">@EXPORT_OK</span><span class="s">]</span><span class="s">)</span><span class="sc">;</span> + 44 + 45 <span class="c"># Setup class variables...</span> + 46 <span class="k">my</span><span class="s">(</span><span class="i">$ClassName</span><span class="s">)</span><span class="sc">;</span> + 47 <span class="i">_InitializeClass</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 48 + 49 <span class="c"># Overload Perl functions...</span> + 50 <span class="k">use</span> <span class="w">overload</span> <span class="q">'""'</span> <span class="cm">=></span> <span class="q">'StringifyCyclesDetection'</span><span class="sc">;</span> + 51 + 52 <span class="c"># Class constructor...</span> +<a name="new-"></a> 53 <span class="k">sub </span><span class="m">new</span> <span class="s">{</span> + 54 <span class="k">my</span><span class="s">(</span><span class="i">$Class</span><span class="cm">,</span> <span class="i">$Graph</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 55 + 56 <span class="c"># Initialize object...</span> + 57 <span class="k">my</span> <span class="i">$This</span> = <span class="s">{</span><span class="s">}</span><span class="sc">;</span> + 58 <span class="k">bless</span> <span class="i">$This</span><span class="cm">,</span> <span class="k">ref</span><span class="s">(</span><span class="i">$Class</span><span class="s">)</span> || <span class="i">$Class</span><span class="sc">;</span> + 59 <span class="i">$This</span><span class="i">->_InitializeCyclesDetection</span><span class="s">(</span><span class="i">$Graph</span><span class="s">)</span><span class="sc">;</span> + 60 + 61 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 62 <span class="s">}</span> + 63 + 64 <span class="c"># Initialize object data...</span> +<a name="_InitializeCyclesDetection-"></a> 65 <span class="k">sub </span><span class="m">_InitializeCyclesDetection</span> <span class="s">{</span> + 66 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Graph</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 67 + 68 <span class="i">$This</span>->{<span class="w">Graph</span>} = <span class="i">$Graph</span><span class="sc">;</span> + 69 + 70 <span class="c"># Cycles list...</span> + 71 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 72 + 73 <span class="c"># Cyclic paths which are not part of any other cycle...</span> + 74 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 75 + 76 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 77 <span class="s">}</span> + 78 + 79 <span class="c"># Initialize class ...</span> +<a name="_InitializeClass-"></a> 80 <span class="k">sub </span><span class="m">_InitializeClass</span> <span class="s">{</span> + 81 <span class="c">#Class name...</span> + 82 <span class="i">$ClassName</span> = <span class="w">__PACKAGE__</span><span class="sc">;</span> + 83 <span class="s">}</span> + 84 + 85 <span class="c"># Detect all cycles in graph...</span> + 86 <span class="c">#</span> +<a name="DetectCycles-"></a> 87 <span class="k">sub </span><span class="m">DetectCycles</span> <span class="s">{</span> + 88 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 89 + 90 <span class="k">return</span> <span class="i">$This</span><span class="i">->DetectCyclesUsingCollapsingPathGraphMethodology</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 91 <span class="s">}</span> + 92 + 93 <span class="c"># Detect all cycles in the graph using collapsing path graph [Ref 31] methodology...</span> + 94 <span class="c">#</span> + 95 <span class="c"># Note:</span> + 96 <span class="c"># . For topologically complex graphs containing large number of cycles,</span> + 97 <span class="c"># CollapseVertexAndCollectCyclicPathsDetectCycles method implemented in</span> + 98 <span class="c"># PathGraph can time out in which case no cycles are detected or</span> + 99 <span class="c"># assigned.</span> + 100 <span class="c">#</span> +<a name="DetectCyclesUsingCollapsingPathGraphMethodology-"></a> 101 <span class="k">sub </span><span class="m">DetectCyclesUsingCollapsingPathGraphMethodology</span> <span class="s">{</span> + 102 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 103 <span class="k">my</span><span class="s">(</span><span class="i">$PathGraph</span><span class="s">)</span><span class="sc">;</span> + 104 + 105 <span class="c"># Create a path graph...</span> + 106 <span class="i">$PathGraph</span> = <span class="i">new</span> <span class="i">Graph::PathGraph</span><span class="s">(</span><span class="i">$This</span>->{<span class="w">Graph</span>}<span class="s">)</span><span class="sc">;</span> + 107 + 108 <span class="c"># For a vertex to be in a cycle, its degree must be >=2. So delete vertices recursively</span> + 109 <span class="c"># till all vertices with degree less than 2 have been deleted...</span> + 110 <span class="i">$PathGraph</span><span class="i">->DeleteVerticesWithDegreeLessThan</span><span class="s">(</span><span class="n">2</span><span class="s">)</span><span class="sc">;</span> + 111 + 112 <span class="c"># Setup a VertexID and EdgeID to index map usage during retrieval of independent cycles to</span> + 113 <span class="c"># avoid going over all vertices in all cylic paths later...</span> + 114 <span class="c">#</span> + 115 <span class="k">my</span><span class="s">(</span><span class="i">$VertexIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestVertexIndex</span><span class="cm">,</span> <span class="i">$EdgeIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestEdgeIDIndex</span><span class="s">)</span><span class="sc">;</span> + 116 <span class="s">(</span><span class="i">$VertexIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestVertexIndex</span><span class="s">)</span> = <span class="i">$This</span><span class="i">->_SetupVertexIDsToIndicesMap</span><span class="s">(</span><span class="i">$PathGraph</span><span class="s">)</span><span class="sc">;</span> + 117 <span class="s">(</span><span class="i">$EdgeIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestEdgeIDIndex</span><span class="s">)</span> = <span class="i">$This</span><span class="i">->_SetupEdgeIDsToIndicesMap</span><span class="s">(</span><span class="i">$PathGraph</span><span class="s">)</span><span class="sc">;</span> + 118 + 119 <span class="c"># Recursively collapse vertices with lowest degree...</span> + 120 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$CycleVertexID</span><span class="s">)</span><span class="sc">;</span> + 121 <span class="k">while</span> <span class="s">(</span><span class="i">$VertexID</span> = <span class="i">$PathGraph</span><span class="i">->GetVertexWithSmallestDegree</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 122 <span class="k">if</span> <span class="s">(</span>!<span class="i">$PathGraph</span><span class="i">->CollapseVertexAndCollectCyclicPaths</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 123 <span class="c"># Cycles detection didn't finish...</span> + 124 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 125 <span class="s">}</span> + 126 <span class="s">}</span> + 127 + 128 <span class="c"># Get detected cycles and save 'em sorted by size...</span> + 129 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}}<span class="cm">,</span> <span class="k">sort</span> <span class="s">{</span> <span class="i">$a</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span> <=> <span class="i">$b</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span> <span class="s">}</span> <span class="i">$PathGraph</span><span class="i">->GetCyclicPaths</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 130 + 131 <span class="c"># Retrieve independent cyclic paths...</span> + 132 <span class="k">return</span> <span class="i">$This</span><span class="i">->_RetrieveIndependentCycles</span><span class="s">(</span><span class="i">$VertexIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestVertexIndex</span><span class="cm">,</span> <span class="i">$EdgeIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestEdgeIDIndex</span><span class="s">)</span><span class="sc">;</span> + 133 <span class="s">}</span> + 134 + 135 <span class="c"># Retrieve and save independent cyclic paths...</span> + 136 <span class="c">#</span> + 137 <span class="c"># Set of independent cycles identified using this method doesn't correspond to basis set of</span> + 138 <span class="c"># rings or smallest set of smallest rings (SSSR) [ Refs 29-30 ]; instead, set of cycles identified</span> + 139 <span class="c"># as independent cycles simply correspond to cycles which contain no other cycle as their</span> + 140 <span class="c"># subcycles and can't be described as linear combination of smaller cycles. And it also happen</span> + 141 <span class="c"># to contain all the rings in basis set of rings and SSSR. In other words, it's a superset of basis set</span> + 142 <span class="c"># of cycles and SSSR. For example, six four membered cycles are identified for cubane which is one</span> + 143 <span class="c"># more than the basis set of cycles.</span> + 144 <span class="c">#</span> +<a name="_RetrieveIndependentCycles-"></a> 145 <span class="k">sub </span><span class="m">_RetrieveIndependentCycles</span> <span class="s">{</span> + 146 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$VertexIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestVertexIndex</span><span class="cm">,</span> <span class="i">$EdgeIDsToIndicesRef</span><span class="cm">,</span> <span class="i">$LargestEdgeIDIndex</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 147 + 148 <span class="c"># Only 1 or 0 cyclic paths...</span> + 149 <span class="k">if</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}} <= <span class="n">1</span><span class="s">)</span> <span class="s">{</span> + 150 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}}<span class="cm">,</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}}<span class="sc">;</span> + 151 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 152 <span class="s">}</span> + 153 + 154 <span class="c"># Setup bit vectors for each cyclic path with size of each bit vector corresponding to</span> + 155 <span class="c"># maximum vertex index plus one...</span> + 156 <span class="k">my</span><span class="s">(</span><span class="i">$CyclicPath</span><span class="cm">,</span> <span class="i">$BitVector</span><span class="cm">,</span> <span class="i">@BitNums</span><span class="cm">,</span> <span class="i">@CyclicPathBitVectors</span><span class="cm">,</span> <span class="i">@CyclicPathEdgeIDsBitVectors</span><span class="s">)</span><span class="sc">;</span> + 157 + 158 <span class="i">@CyclicPathBitVectors</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@CyclicPathEdgeIDsBitVectors</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 159 + 160 <span class="c"># Set bits corresponding to VertexIDs EdgeIDs using their indices...</span> + 161 <span class="k">for</span> <span class="i">$CyclicPath</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}}<span class="s">)</span> <span class="s">{</span> + 162 <span class="i">$BitVector</span> = <span class="i">new</span> <span class="i">BitVector</span><span class="s">(</span><span class="i">$LargestVertexIndex</span><span class="s">)</span><span class="sc">;</span> + 163 <span class="i">@BitNums</span> = <span class="k">map</span> <span class="s">{</span> <span class="i">$VertexIDsToIndicesRef</span>->{<span class="i">$_</span>} <span class="s">}</span> <span class="i">$CyclicPath</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 164 <span class="i">$BitVector</span><span class="i">->SetBits</span><span class="s">(</span><span class="i">@BitNums</span><span class="s">)</span><span class="sc">;</span> + 165 <span class="k">push</span> <span class="i">@CyclicPathBitVectors</span><span class="cm">,</span> <span class="i">$BitVector</span><span class="sc">;</span> + 166 + 167 <span class="i">$BitVector</span> = <span class="i">new</span> <span class="i">BitVector</span><span class="s">(</span><span class="i">$LargestEdgeIDIndex</span><span class="s">)</span><span class="sc">;</span> + 168 <span class="i">@BitNums</span> = <span class="k">map</span> <span class="s">{</span> <span class="i">$EdgeIDsToIndicesRef</span>->{<span class="i">$_</span>} <span class="s">}</span> <span class="i">$This</span><span class="i">->_GetPathEdgeIDs</span><span class="s">(</span><span class="i">$CyclicPath</span><span class="s">)</span><span class="sc">;</span> + 169 <span class="i">$BitVector</span><span class="i">->SetBits</span><span class="s">(</span><span class="i">@BitNums</span><span class="s">)</span><span class="sc">;</span> + 170 <span class="k">push</span> <span class="i">@CyclicPathEdgeIDsBitVectors</span><span class="cm">,</span> <span class="i">$BitVector</span><span class="sc">;</span> + 171 <span class="s">}</span> + 172 + 173 <span class="c"># First smallest cyclic path always ends up as an independent cyclic path...</span> + 174 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}}<span class="cm">,</span> <span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}[<span class="n">0</span>]<span class="sc">;</span> + 175 + 176 <span class="c"># Retrieve other independent cyclic paths...</span> + 177 <span class="k">my</span><span class="s">(</span><span class="i">$CurrentIndex</span><span class="cm">,</span> <span class="i">$PreviousIndex</span><span class="cm">,</span> <span class="i">$CurrentCyclicPath</span><span class="cm">,</span> <span class="i">$PreviousCyclicPath</span><span class="cm">,</span> <span class="i">$CurrentPathLength</span><span class="cm">,</span> <span class="i">$PreviousPathLength</span><span class="cm">,</span> <span class="i">$CurrentBitVector</span><span class="cm">,</span> <span class="i">$PreviousBitVector</span><span class="cm">,</span> <span class="i">$CurrentAndPreviousBitVectpor</span><span class="cm">,</span> <span class="i">$AllPreviousSmallerPathsBitVector</span><span class="cm">,</span> <span class="i">$AllPreviousSmallerPathsEdgeIDsBitVector</span><span class="cm">,</span> <span class="i">$CurrentEdgeIDsBitVector</span><span class="cm">,</span> <span class="i">$AndBitVector</span><span class="cm">,</span> <span class="i">%SmallerPathAlreadyAdded</span><span class="cm">,</span> <span class="i">%SkipPath</span><span class="s">)</span><span class="sc">;</span> + 178 + 179 <span class="i">%SkipPath</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 180 <span class="i">%SmallerPathAlreadyAdded</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 181 <span class="i">$AllPreviousSmallerPathsBitVector</span> = <span class="i">new</span> <span class="i">BitVector</span><span class="s">(</span><span class="i">$LargestVertexIndex</span><span class="s">)</span><span class="sc">;</span> + 182 <span class="i">$AllPreviousSmallerPathsEdgeIDsBitVector</span> = <span class="i">new</span> <span class="i">BitVector</span><span class="s">(</span><span class="i">$LargestEdgeIDIndex</span><span class="s">)</span><span class="sc">;</span> + 183 + 184 <span class="j">CURRENT:</span> <span class="k">for</span> <span class="i">$CurrentIndex</span> <span class="s">(</span><span class="n">1</span> .. <span class="i">$#</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}}<span class="s">)</span> <span class="s">{</span> + 185 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$SkipPath</span>{<span class="i">$CurrentIndex</span>}<span class="s">)</span> <span class="s">{</span> + 186 <span class="k">next</span> <span class="j">CURRENT</span><span class="sc">;</span> + 187 <span class="s">}</span> + 188 <span class="i">$CurrentCyclicPath</span> = <span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}[<span class="i">$CurrentIndex</span>]<span class="sc">;</span> + 189 <span class="i">$CurrentBitVector</span> = <span class="i">$CyclicPathBitVectors</span>[<span class="i">$CurrentIndex</span>]<span class="sc">;</span> + 190 <span class="i">$CurrentPathLength</span> = <span class="i">$CurrentCyclicPath</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 191 + 192 <span class="j">PREVIOUS:</span> <span class="k">for</span> <span class="i">$PreviousIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$CurrentIndex</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 193 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$SkipPath</span>{<span class="i">$PreviousIndex</span>}<span class="s">)</span> <span class="s">{</span> + 194 <span class="k">next</span> <span class="j">PREVIOUS</span><span class="sc">;</span> + 195 <span class="s">}</span> + 196 <span class="i">$PreviousCyclicPath</span> = <span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}[<span class="i">$PreviousIndex</span>]<span class="sc">;</span> + 197 <span class="i">$PreviousBitVector</span> = <span class="i">$CyclicPathBitVectors</span>[<span class="i">$PreviousIndex</span>]<span class="sc">;</span> + 198 + 199 <span class="c"># Is previous path a subset of current path?</span> + 200 <span class="i">$CurrentAndPreviousBitVectpor</span> = <span class="i">$PreviousBitVector</span> & <span class="i">$CurrentBitVector</span><span class="sc">;</span> + 201 <span class="k">if</span> <span class="s">(</span><span class="i">$PreviousBitVector</span><span class="i">->GetNumOfSetBits</span><span class="s">(</span><span class="s">)</span> == <span class="i">$CurrentAndPreviousBitVectpor</span><span class="i">->GetNumOfSetBits</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 202 <span class="c"># Current path doesn't qualify an independent path...</span> + 203 <span class="i">$SkipPath</span>{<span class="i">$CurrentIndex</span>} = <span class="n">1</span><span class="sc">;</span> + 204 <span class="k">next</span> <span class="j">CURRENT</span><span class="sc">;</span> + 205 <span class="s">}</span> + 206 + 207 <span class="i">$PreviousPathLength</span> = <span class="i">$PreviousCyclicPath</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 208 <span class="k">if</span> <span class="s">(</span><span class="i">$PreviousPathLength</span> < <span class="i">$CurrentPathLength</span><span class="s">)</span> <span class="s">{</span> + 209 <span class="c"># Mark cycle vertices seen in cyclic paths with length smaller than current path...</span> + 210 <span class="k">if</span> <span class="s">(</span>! <span class="k">exists</span> <span class="i">$SmallerPathAlreadyAdded</span>{<span class="i">$PreviousIndex</span>}<span class="s">)</span> <span class="s">{</span> + 211 <span class="i">$SmallerPathAlreadyAdded</span>{<span class="i">$PreviousIndex</span>} = <span class="n">1</span><span class="sc">;</span> + 212 <span class="i">$AllPreviousSmallerPathsBitVector</span> = <span class="i">$AllPreviousSmallerPathsBitVector</span> | <span class="i">$PreviousBitVector</span><span class="sc">;</span> + 213 <span class="i">$AllPreviousSmallerPathsEdgeIDsBitVector</span> = <span class="i">$AllPreviousSmallerPathsEdgeIDsBitVector</span> | <span class="i">$CyclicPathEdgeIDsBitVectors</span>[<span class="i">$PreviousIndex</span>]<span class="sc">;</span> + 214 <span class="s">}</span> + 215 <span class="s">}</span> + 216 <span class="s">}</span> + 217 <span class="k">if</span> <span class="s">(</span><span class="i">$AllPreviousSmallerPathsBitVector</span><span class="i">->GetNumOfSetBits</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 218 <span class="c"># Is current path a linear combination of smaller paths?</span> + 219 <span class="i">$AndBitVector</span> = <span class="i">$AllPreviousSmallerPathsBitVector</span> & <span class="i">$CurrentBitVector</span><span class="sc">;</span> + 220 <span class="k">if</span> <span class="s">(</span><span class="i">$CurrentBitVector</span><span class="i">->GetNumOfSetBits</span><span class="s">(</span><span class="s">)</span> == <span class="i">$AndBitVector</span><span class="i">->GetNumOfSetBits</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 221 <span class="c"># Are all edges in the current path already present in smaller paths?</span> + 222 <span class="i">$CurrentEdgeIDsBitVector</span> = <span class="i">$CyclicPathEdgeIDsBitVectors</span>[<span class="i">$CurrentIndex</span>]<span class="sc">;</span> + 223 <span class="i">$AndBitVector</span> = <span class="i">$AllPreviousSmallerPathsEdgeIDsBitVector</span> & <span class="i">$CurrentEdgeIDsBitVector</span><span class="sc">;</span> + 224 + 225 <span class="k">if</span> <span class="s">(</span><span class="i">$CurrentEdgeIDsBitVector</span><span class="i">->GetNumOfSetBits</span><span class="s">(</span><span class="s">)</span> == <span class="i">$AndBitVector</span><span class="i">->GetNumOfSetBits</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 226 <span class="c"># Current path doesn't qualify an independent path...</span> + 227 <span class="i">$SkipPath</span>{<span class="i">$CurrentIndex</span>} = <span class="n">1</span><span class="sc">;</span> + 228 <span class="k">next</span> <span class="j">CURRENT</span><span class="sc">;</span> + 229 <span class="s">}</span> + 230 <span class="s">}</span> + 231 <span class="s">}</span> + 232 <span class="c"># It's an independent cyclic path...</span> + 233 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}}<span class="cm">,</span> <span class="i">$CurrentCyclicPath</span><span class="sc">;</span> + 234 <span class="s">}</span> + 235 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 236 <span class="s">}</span> + 237 + 238 <span class="c"># Setup a VertexID to index map...</span> + 239 <span class="c">#</span> +<a name="_SetupVertexIDsToIndicesMap-"></a> 240 <span class="k">sub </span><span class="m">_SetupVertexIDsToIndicesMap</span> <span class="s">{</span> + 241 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$PathGraph</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 242 <span class="k">my</span><span class="s">(</span><span class="i">$LargestVertexIndex</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">%VertexIDsMap</span><span class="s">)</span><span class="sc">;</span> + 243 + 244 <span class="i">%VertexIDsMap</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@VertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">$LargestVertexIndex</span> = <span class="n">0</span><span class="sc">;</span> + 245 + 246 <span class="i">@VertexIDs</span> = <span class="i">$PathGraph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 247 <span class="k">if</span> <span class="s">(</span>! <span class="i">@VertexIDs</span><span class="s">)</span> <span class="s">{</span> + 248 <span class="k">return</span> <span class="s">(</span>\<span class="i">%VertexIDsMap</span><span class="cm">,</span> <span class="i">$LargestVertexIndex</span><span class="s">)</span><span class="sc">;</span> + 249 <span class="s">}</span> + 250 <span class="i">@VertexIDsMap</span>{ <span class="i">@VertexIDs</span> } = <span class="s">(</span><span class="n">0</span> .. <span class="i">$#VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 251 <span class="i">$LargestVertexIndex</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 252 + 253 <span class="k">return</span> <span class="s">(</span>\<span class="i">%VertexIDsMap</span><span class="cm">,</span> <span class="i">$LargestVertexIndex</span><span class="s">)</span><span class="sc">;</span> + 254 <span class="s">}</span> + 255 + 256 <span class="c"># Setup a Edge to index map using paths associated to egdes in an intial</span> + 257 <span class="c"># path graph...</span> + 258 <span class="c">#</span> +<a name="_SetupEdgeIDsToIndicesMap-"></a> 259 <span class="k">sub </span><span class="m">_SetupEdgeIDsToIndicesMap</span> <span class="s">{</span> + 260 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$PathGraph</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 261 <span class="k">my</span><span class="s">(</span><span class="i">$Path</span><span class="cm">,</span> <span class="i">$LargestEdgeIndex</span><span class="cm">,</span> <span class="i">@EdgeIDs</span><span class="cm">,</span> <span class="i">%EdgeIDsMap</span><span class="s">)</span><span class="sc">;</span> + 262 + 263 <span class="i">%EdgeIDsMap</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@EdgeIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">$LargestEdgeIndex</span> = <span class="n">0</span><span class="sc">;</span> + 264 + 265 <span class="i">@EdgeIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 266 <span class="k">for</span> <span class="i">$Path</span> <span class="s">(</span><span class="i">$PathGraph</span><span class="i">->GetPaths</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 267 <span class="k">push</span> <span class="i">@EdgeIDs</span><span class="cm">,</span> <span class="i">$This</span><span class="i">->_GetPathEdgeIDs</span><span class="s">(</span><span class="i">$Path</span><span class="s">)</span><span class="sc">;</span> + 268 <span class="s">}</span> + 269 + 270 <span class="k">if</span> <span class="s">(</span>! <span class="i">@EdgeIDs</span><span class="s">)</span> <span class="s">{</span> + 271 <span class="k">return</span> <span class="s">(</span>\<span class="i">%EdgeIDsMap</span><span class="cm">,</span> <span class="i">$LargestEdgeIndex</span><span class="s">)</span><span class="sc">;</span> + 272 <span class="s">}</span> + 273 + 274 <span class="i">@EdgeIDsMap</span>{ <span class="i">@EdgeIDs</span> } = <span class="s">(</span><span class="n">0</span> .. <span class="i">$#EdgeIDs</span><span class="s">)</span><span class="sc">;</span> + 275 <span class="i">$LargestEdgeIndex</span> = <span class="k">scalar</span> <span class="i">@EdgeIDs</span><span class="sc">;</span> + 276 + 277 <span class="k">return</span> <span class="s">(</span>\<span class="i">%EdgeIDsMap</span><span class="cm">,</span> <span class="i">$LargestEdgeIndex</span><span class="s">)</span><span class="sc">;</span> + 278 <span class="s">}</span> + 279 + 280 <span class="c"># Get path edge IDs or number of edges. The edge IDs are generated from</span> + 281 <span class="c"># edge vertices and correpond to VertexID1-VertexID2 where VertexID1 <=</span> + 282 <span class="c"># VertexID2.</span> + 283 <span class="c">#</span> +<a name="_GetPathEdgeIDs-"></a> 284 <span class="k">sub </span><span class="m">_GetPathEdgeIDs</span> <span class="s">{</span> + 285 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Path</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 286 <span class="k">my</span><span class="s">(</span><span class="i">@EdgesVertexIDs</span><span class="cm">,</span> <span class="i">@EdgeIDs</span><span class="s">)</span><span class="sc">;</span> + 287 + 288 <span class="i">@EdgesVertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@EdgeIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 289 <span class="i">@EdgesVertexIDs</span> = <span class="i">$Path</span><span class="i">->GetEdges</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 290 <span class="k">if</span> <span class="s">(</span>!<span class="i">@EdgesVertexIDs</span><span class="s">)</span> <span class="s">{</span> + 291 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@EdgeIDs</span> <span class="co">:</span> <span class="s">(</span><span class="k">scalar</span> <span class="i">@EdgeIDs</span><span class="s">)</span><span class="sc">;</span> + 292 <span class="s">}</span> + 293 + 294 <span class="c"># Set up edge IDs...</span> + 295 <span class="k">my</span><span class="s">(</span><span class="i">$Index</span><span class="cm">,</span> <span class="i">$VertexID1</span><span class="cm">,</span> <span class="i">$VertexID2</span><span class="cm">,</span> <span class="i">$EdgeID</span><span class="s">)</span><span class="sc">;</span> + 296 + 297 <span class="k">for</span> <span class="s">(</span><span class="i">$Index</span> = <span class="n">0</span><span class="sc">;</span> <span class="i">$Index</span> < <span class="i">$#EdgesVertexIDs</span><span class="sc">;</span> <span class="i">$Index</span> += <span class="n">2</span><span class="s">)</span> <span class="s">{</span> + 298 <span class="i">$VertexID1</span> = <span class="i">$EdgesVertexIDs</span>[<span class="i">$Index</span>]<span class="sc">;</span> <span class="i">$VertexID2</span> = <span class="i">$EdgesVertexIDs</span>[<span class="i">$Index</span> + <span class="n">1</span>]<span class="sc">;</span> + 299 <span class="i">$EdgeID</span> = <span class="s">(</span><span class="i">$VertexID1</span> <= <span class="i">$VertexID2</span><span class="s">)</span> ? <span class="q">"$VertexID1-$VertexID2"</span> <span class="co">:</span> <span class="q">"$VertexID2-$VertexID1"</span><span class="sc">;</span> + 300 <span class="k">push</span> <span class="i">@EdgeIDs</span><span class="cm">,</span> <span class="i">$EdgeID</span><span class="sc">;</span> + 301 <span class="s">}</span> + 302 + 303 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@EdgeIDs</span> <span class="co">:</span> <span class="s">(</span><span class="k">scalar</span> <span class="i">@EdgeIDs</span><span class="s">)</span><span class="sc">;</span> + 304 <span class="s">}</span> + 305 + 306 <span class="c"># Return an array containing references to cyclic paths or number of cylic paths...</span> + 307 <span class="c">#</span> +<a name="GetAllCyclicPaths-"></a> 308 <span class="k">sub </span><span class="m">GetAllCyclicPaths</span> <span class="s">{</span> + 309 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 310 + 311 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}} <span class="co">:</span> <span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}}<span class="sc">;</span> + 312 <span class="s">}</span> + 313 + 314 <span class="c"># Get cyclic paths which are independent. In otherwords, cycles which don't contain any other</span> + 315 <span class="c"># cycle as their subset...</span> + 316 <span class="c">#</span> +<a name="GetIndependentCyclicPaths-"></a> 317 <span class="k">sub </span><span class="m">GetIndependentCyclicPaths</span> <span class="s">{</span> + 318 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 319 + 320 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}} <span class="co">:</span> <span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}}<span class="sc">;</span> + 321 <span class="s">}</span> + 322 + 323 <span class="c"># Return a string containg data for CyclesDetection object...</span> +<a name="StringifyCyclesDetection-"></a> 324 <span class="k">sub </span><span class="m">StringifyCyclesDetection</span> <span class="s">{</span> + 325 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 326 <span class="k">my</span><span class="s">(</span><span class="i">$CyclesDetectionString</span><span class="cm">,</span> <span class="i">$CyclesCount</span><span class="cm">,</span> <span class="i">$CyclicPath</span><span class="s">)</span><span class="sc">;</span> + 327 + 328 <span class="i">$CyclesCount</span> = <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}}<span class="sc">;</span> + 329 <span class="i">$CyclesDetectionString</span> = <span class="q">"AllCycles: Count - $CyclesCount"</span><span class="sc">;</span> + 330 <span class="k">for</span> <span class="i">$CyclicPath</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">AllCyclicPaths</span>}}<span class="s">)</span> <span class="s">{</span> + 331 <span class="i">$CyclesDetectionString</span> .= <span class="q">"; Cycle: "</span> . <span class="k">join</span><span class="s">(</span><span class="q">'-'</span><span class="cm">,</span> <span class="i">$CyclicPath</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="s">)</span><span class="sc">;</span> + 332 <span class="s">}</span> + 333 + 334 <span class="i">$CyclesCount</span> = <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}}<span class="sc">;</span> + 335 <span class="i">$CyclesDetectionString</span> .= <span class="q">"\nIndependentCycles: Count - $CyclesCount"</span><span class="sc">;</span> + 336 <span class="k">for</span> <span class="i">$CyclicPath</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">IndependentCyclicPaths</span>}}<span class="s">)</span> <span class="s">{</span> + 337 <span class="i">$CyclesDetectionString</span> .= <span class="q">"; Cycle: "</span> . <span class="k">join</span><span class="s">(</span><span class="q">'-'</span><span class="cm">,</span> <span class="i">$CyclicPath</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="s">)</span><span class="sc">;</span> + 338 <span class="s">}</span> + 339 + 340 <span class="k">return</span> <span class="i">$CyclesDetectionString</span><span class="sc">;</span> + 341 <span class="s">}</span> + 342 + 343 <span class="c"># Return a reference to new cycle detection object...</span> +<a name="Copy-"></a> 344 <span class="k">sub </span><span class="m">Copy</span> <span class="s">{</span> + 345 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 346 <span class="k">my</span><span class="s">(</span><span class="i">$NewCyclesDetection</span><span class="s">)</span><span class="sc">;</span> + 347 + 348 <span class="i">$NewCyclesDetection</span> = <span class="i">Storable::dclone</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span><span class="sc">;</span> + 349 + 350 <span class="k">return</span> <span class="i">$NewCyclesDetection</span><span class="sc">;</span> + 351 <span class="s">}</span> + 352 +<a name="EOF-"></a></pre> +<p> </p> +<br /> +<center> +<img src="../../../images/h2o2.png"> +</center> +</body> +</html>