annotate mayachemtools/docs/modules/html/code/CyclesDetection.html @ 0:73ae111cf86f draft

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