Mercurial > repos > deepakjadmin > mayatool3_test3
diff mayachemtools/docs/modules/html/code/PathGraph.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/PathGraph.html Wed Jan 20 11:55:01 2016 -0500 @@ -0,0 +1,330 @@ +<html> +<head> +<title>MayaChemTools:Code:Graph::PathGraph.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::PathGraph-"></a> 1 <span class="k">package </span><span class="i">Graph::PathGraph</span><span class="sc">;</span> + 2 <span class="c">#</span> + 3 <span class="c"># $RCSfile: PathGraph.pm,v $</span> + 4 <span class="c"># $Date: 2015/02/28 20:49:06 $</span> + 5 <span class="c"># $Revision: 1.24 $</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">Storable</span> <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 33 <span class="k">use</span> <span class="w">Scalar::Util</span> <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 34 <span class="k">use</span> <span class="w">Graph</span><span class="sc">;</span> + 35 <span class="k">use</span> <span class="w">Graph::Path</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(Graph Exporter)</span><span class="sc">;</span> + 40 <span class="i">@EXPORT</span> = <span class="q">qw(IsPathGraph)</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="cm">,</span> <span class="i">$PathsPropertyName</span><span class="cm">,</span> <span class="i">$CyclicPathsPropertyName</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">'StringifyPathGraph'</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="i">$Class</span><span class="i">->SUPER::new</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">->_InitializePathGraph</span><span class="s">(</span><span class="i">$Graph</span><span class="s">)</span><span class="sc">;</span> + 60 + 61 <span class="i">$This</span><span class="i">->_ConvertGraphIntoPathGraph</span><span class="s">(</span><span class="i">$Graph</span><span class="s">)</span><span class="sc">;</span> + 62 + 63 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 64 <span class="s">}</span> + 65 + 66 <span class="c"># Initialize object data...</span> +<a name="_InitializePathGraph-"></a> 67 <span class="k">sub </span><span class="m">_InitializePathGraph</span> <span class="s">{</span> + 68 <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> + 69 + 70 <span class="k">if</span> <span class="s">(</span>!<span class="s">(</span><span class="k">defined</span><span class="s">(</span><span class="i">$Graph</span><span class="s">)</span> && <span class="i">Graph::IsGraph</span><span class="s">(</span><span class="i">$Graph</span><span class="s">)</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 71 <span class="w">croak</span> <span class="q">"Error: ${ClassName}->new: PathGraph object can't be instantiated without a Graph object..."</span><span class="sc">;</span> + 72 <span class="s">}</span> + 73 + 74 <span class="i">$This</span>->{<span class="w">Graph</span>} = <span class="i">$Graph</span><span class="sc">;</span> + 75 + 76 <span class="c"># Maximum time allowed for cycles detection during collapse vertex cycles detection</span> + 77 <span class="c"># methodology in seconds...</span> + 78 <span class="i">$This</span>->{<span class="w">MaxAllowedTime</span>} = <span class="n">30</span><span class="sc">;</span> + 79 + 80 <span class="c"># Starting time for cycles detection during collapse vertex cycles detection</span> + 81 <span class="c"># methodology...</span> + 82 <span class="i">$This</span>->{<span class="w">StartTime</span>} = <span class="k">time</span><span class="sc">;</span> + 83 + 84 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 85 <span class="s">}</span> + 86 + 87 <span class="c"># Initialize class ...</span> +<a name="_InitializeClass-"></a> 88 <span class="k">sub </span><span class="m">_InitializeClass</span> <span class="s">{</span> + 89 <span class="c">#Class name...</span> + 90 <span class="i">$ClassName</span> = <span class="w">__PACKAGE__</span><span class="sc">;</span> + 91 + 92 <span class="c"># Path edge property name...</span> + 93 <span class="i">$PathsPropertyName</span> = <span class="q">'Paths'</span><span class="sc">;</span> + 94 + 95 <span class="c"># Cyclic path vertex property name...</span> + 96 <span class="i">$CyclicPathsPropertyName</span> = <span class="q">'CyclicPaths'</span><span class="sc">;</span> + 97 <span class="s">}</span> + 98 + 99 <span class="c"># Convert graph into a path graph...</span> + 100 <span class="c">#</span> +<a name="_ConvertGraphIntoPathGraph-"></a> 101 <span class="k">sub </span><span class="m">_ConvertGraphIntoPathGraph</span> <span class="s">{</span> + 102 <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> + 103 + 104 <span class="c"># Copy graph vertices and edges without any associated properties data</span> + 105 <span class="c"># from Graph to This: Graph properties data is available using Graph object reference</span> + 106 <span class="c"># store in This object...</span> + 107 <span class="c">#</span> + 108 <span class="i">$Graph</span><span class="i">->CopyVerticesAndEdges</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span><span class="sc">;</span> + 109 + 110 <span class="c"># . Attach Path property to each edge...</span> + 111 <span class="c">#</span> + 112 <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">$Path</span><span class="cm">,</span> <span class="i">@EdgesVertexIDs</span><span class="s">)</span><span class="sc">;</span> + 113 + 114 <span class="i">@EdgesVertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 115 <span class="i">@EdgesVertexIDs</span> = <span class="i">$This</span><span class="i">->GetEdges</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 116 <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> + 117 <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> + 118 <span class="i">$Path</span> = <span class="i">new</span> <span class="i">Graph::Path</span><span class="s">(</span><span class="i">$VertexID1</span><span class="cm">,</span> <span class="i">$VertexID2</span><span class="s">)</span><span class="sc">;</span> + 119 <span class="k">my</span><span class="s">(</span><span class="i">@Paths</span><span class="s">)</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 120 <span class="k">push</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">$Path</span><span class="sc">;</span> + 121 <span class="i">$This</span><span class="i">->SetEdgeProperty</span><span class="s">(</span><span class="i">$PathsPropertyName</span><span class="cm">,</span> \<span class="i">@Paths</span><span class="cm">,</span> <span class="i">$VertexID1</span><span class="cm">,</span> <span class="i">$VertexID2</span><span class="s">)</span><span class="sc">;</span> + 122 <span class="s">}</span> + 123 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 124 <span class="s">}</span> + 125 + 126 <span class="c"># Collapse paths around a specified vertex by updating paths around the vertex</span> + 127 <span class="c"># and adding any resulting cyclic paths to vertices attached to specified vertex.</span> + 128 <span class="c">#</span> + 129 <span class="c"># Notes:</span> + 130 <span class="c"># . Path object references are stored as a list attached to Paths property on edges.</span> + 131 <span class="c"># Usage of list allows multiple paths attached to the egde between a pair of vertices;</span> + 132 <span class="c"># Graph doesn't support multiple egdes between a pair of vertices.</span> + 133 <span class="c">#</span> + 134 <span class="c"># . Cyclic path object references are stored as list on vertices as CyclicPaths graph property.</span> + 135 <span class="c"># List allows multiple Loop properties attached to a vertex.</span> + 136 <span class="c">#</span> + 137 <span class="c"># . For topologically complex graphs containing large number of cycles, cycles detection algorithm</span> + 138 <span class="c"># [ Ref 31 ] as implemented implemented in CollapseVertexAndCollectCyclicPathsDetectCycles</span> + 139 <span class="c"># might not be able to find all the cycles in a reasonable amount of time and is designed to</span> + 140 <span class="c"># abandon cycles detection after MaxAllowedTime. Consequently, no cycles are detected</span> + 141 <span class="c"># or assigned.</span> + 142 <span class="c">#</span> +<a name="CollapseVertexAndCollectCyclicPaths-"></a> 143 <span class="k">sub </span><span class="m">CollapseVertexAndCollectCyclicPaths</span> <span class="s">{</span> + 144 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 145 + 146 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span><span class="i">->HasVertex</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 147 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->CollapseVertexAndCollectCyclicPaths: Didn't collapse vertex $VertexID: Vertex $VertexID doesn't exist..."</span><span class="sc">;</span> + 148 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 149 <span class="s">}</span> + 150 <span class="c"># Collect all paths around specified VertexID by going over paths associated with its edges...</span> + 151 <span class="k">my</span><span class="s">(</span><span class="i">$Index</span><span class="cm">,</span> <span class="i">$EdgePathsRef</span><span class="cm">,</span> <span class="i">$EdgeVertexID1</span><span class="cm">,</span> <span class="i">$EdgeVertexID2</span><span class="cm">,</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@EdgesVertexIDs</span><span class="s">)</span><span class="sc">;</span> + 152 + 153 <span class="i">@EdgesVertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 154 <span class="i">@EdgesVertexIDs</span> = <span class="i">$This</span><span class="i">->GetEdges</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> + 155 + 156 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 157 <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> + 158 <span class="s">(</span><span class="i">$EdgeVertexID1</span><span class="cm">,</span> <span class="i">$EdgeVertexID2</span><span class="s">)</span> = <span class="s">(</span><span class="i">$EdgesVertexIDs</span>[<span class="i">$Index</span>]<span class="cm">,</span> <span class="i">$EdgesVertexIDs</span>[<span class="i">$Index</span> + <span class="n">1</span>]<span class="s">)</span><span class="sc">;</span> + 159 <span class="i">$EdgePathsRef</span> = <span class="i">$This</span><span class="i">->GetEdgeProperty</span><span class="s">(</span><span class="i">$PathsPropertyName</span><span class="cm">,</span> <span class="i">$EdgeVertexID1</span><span class="cm">,</span> <span class="i">$EdgeVertexID2</span><span class="s">)</span><span class="sc">;</span> + 160 <span class="k">push</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$EdgePathsRef</span>}<span class="sc">;</span> + 161 <span class="s">}</span> + 162 + 163 <span class="c"># Go over each pair of paths around the specified vertex, join paths and associate</span> + 164 <span class="c"># joined path to appropriate edge...</span> + 165 <span class="k">my</span><span class="s">(</span><span class="i">$Index1</span><span class="cm">,</span> <span class="i">$Index2</span><span class="cm">,</span> <span class="i">$Path1</span><span class="cm">,</span> <span class="i">$Path2</span><span class="cm">,</span> <span class="i">$JoinedPath</span><span class="cm">,</span> <span class="i">$JoinedPathStartVertexID</span><span class="cm">,</span> <span class="i">$JoinedPathEndVertexID</span><span class="cm">,</span> <span class="i">@CommonVertices</span><span class="s">)</span><span class="sc">;</span> + 166 + 167 <span class="k">for</span> <span class="s">(</span><span class="i">$Index1</span> = <span class="n">0</span><span class="sc">;</span> <span class="i">$Index1</span> < <span class="i">$#Paths</span><span class="sc">;</span> <span class="i">$Index1</span> +=<span class="n">1</span> <span class="s">)</span> <span class="s">{</span> + 168 <span class="i">$Path1</span> = <span class="i">$Paths</span>[<span class="i">$Index1</span>]<span class="sc">;</span> + 169 + 170 <span class="j">PATH2:</span> <span class="k">for</span> <span class="s">(</span><span class="i">$Index2</span> = <span class="i">$Index1</span> + <span class="n">1</span><span class="sc">;</span> <span class="i">$Index2</span> <= <span class="i">$#Paths</span><span class="sc">;</span> <span class="i">$Index2</span> +=<span class="n">1</span> <span class="s">)</span> <span class="s">{</span> + 171 <span class="i">$Path2</span> = <span class="i">$Paths</span>[<span class="i">$Index2</span>]<span class="sc">;</span> + 172 + 173 <span class="c"># For JoinedPath to be valid cycle, Path1 and Path2 must have exactly two vertices in common.</span> + 174 <span class="c"># Otherwise, joined path contains duplicate vertices besides the terminal vertices and</span> + 175 <span class="c"># indicates a path from a different direction.</span> + 176 <span class="c">#</span> + 177 <span class="c"># For paths leading to cycles, it only makes sense to join paths with only one common vertex;</span> + 178 <span class="c"># otherwise, it wouldn't lead to a cycle and can be ignored.</span> + 179 <span class="c">#</span> + 180 <span class="i">@CommonVertices</span> = <span class="i">$Path1</span><span class="i">->GetCommonVertices</span><span class="s">(</span><span class="i">$Path2</span><span class="s">)</span><span class="sc">;</span> + 181 <span class="k">if</span> <span class="s">(</span>!<span class="s">(</span><span class="i">@CommonVertices</span> <= <span class="n">2</span> && <span class="s">(</span><span class="i">$CommonVertices</span>[<span class="n">0</span>] == <span class="i">$VertexID</span> || <span class="i">$CommonVertices</span>[<span class="n">1</span>] == <span class="i">$VertexID</span><span class="s">)</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 182 <span class="k">next</span> <span class="j">PATH2</span><span class="sc">;</span> + 183 <span class="s">}</span> + 184 + 185 <span class="i">$JoinedPath</span> = <span class="i">$Path1</span><span class="i">->JoinAtVertex</span><span class="s">(</span><span class="i">$Path2</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> + 186 <span class="s">(</span><span class="i">$JoinedPathStartVertexID</span><span class="cm">,</span> <span class="i">$JoinedPathEndVertexID</span><span class="s">)</span> = <span class="i">$JoinedPath</span><span class="i">->GetTerminalVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 187 + 188 <span class="k">if</span> <span class="s">(</span>!<span class="i">$JoinedPath</span><span class="i">->IsIndependentPath</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 189 <span class="k">next</span> <span class="j">PATH2</span><span class="sc">;</span> + 190 <span class="s">}</span> + 191 + 192 <span class="c"># Decide whether to give up or keep going...</span> + 193 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span><span class="i">->_IsTimeToGiveUpCyclesDetection</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 194 <span class="k">warn</span> <span class="q">"Warning: ${ClassName}->CollapseVertexAndCollectCyclicPaths: Cycles detection algorithm [ Ref 31 ] as implemented in the current release of MayaChemTools didn't finish with in the maximum allowed time of $This->{MaxAllowedTime} seconds; Cycles detection has been abandoned..."</span><span class="sc">;</span> + 195 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 196 <span class="s">}</span> + 197 + 198 <span class="k">if</span> <span class="s">(</span><span class="i">$JoinedPathStartVertexID</span> == <span class="i">$JoinedPathEndVertexID</span><span class="s">)</span> <span class="s">{</span> + 199 <span class="c"># It's a cycle. Attach it to the graph as CylicPaths property...</span> + 200 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span><span class="i">->HasGraphProperty</span><span class="s">(</span><span class="i">$CyclicPathsPropertyName</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 201 <span class="k">my</span><span class="s">(</span><span class="i">$ExistingCyclicPathsRef</span><span class="s">)</span><span class="sc">;</span> + 202 <span class="i">$ExistingCyclicPathsRef</span> = <span class="i">$This</span><span class="i">->GetGraphProperty</span><span class="s">(</span><span class="i">$CyclicPathsPropertyName</span><span class="s">)</span><span class="sc">;</span> + 203 <span class="k">push</span> <span class="i">@</span>{<span class="i">$ExistingCyclicPathsRef</span>}<span class="cm">,</span> <span class="i">$JoinedPath</span><span class="sc">;</span> + 204 <span class="s">}</span> + 205 <span class="k">else</span> <span class="s">{</span> + 206 <span class="k">my</span><span class="s">(</span><span class="i">@NewCyclicPaths</span><span class="s">)</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 207 <span class="k">push</span> <span class="i">@NewCyclicPaths</span><span class="cm">,</span> <span class="i">$JoinedPath</span><span class="sc">;</span> + 208 <span class="i">$This</span><span class="i">->SetGraphProperty</span><span class="s">(</span><span class="i">$CyclicPathsPropertyName</span><span class="cm">,</span> \<span class="i">@NewCyclicPaths</span><span class="cm">,</span> <span class="i">$JoinedPathStartVertexID</span><span class="s">)</span><span class="sc">;</span> + 209 <span class="s">}</span> + 210 <span class="s">}</span> + 211 <span class="k">else</span> <span class="s">{</span> + 212 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span><span class="i">->HasEdge</span><span class="s">(</span><span class="i">$JoinedPathStartVertexID</span><span class="cm">,</span> <span class="i">$JoinedPathEndVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 213 <span class="c"># Append to the list of exisiting paths property of the edge...</span> + 214 <span class="k">my</span><span class="s">(</span><span class="i">$ExistingPathsRef</span><span class="s">)</span><span class="sc">;</span> + 215 <span class="i">$ExistingPathsRef</span> = <span class="i">$This</span><span class="i">->GetEdgeProperty</span><span class="s">(</span><span class="i">$PathsPropertyName</span><span class="cm">,</span> <span class="i">$JoinedPathStartVertexID</span><span class="cm">,</span> <span class="i">$JoinedPathEndVertexID</span><span class="s">)</span><span class="sc">;</span> + 216 <span class="k">push</span> <span class="i">@</span>{<span class="i">$ExistingPathsRef</span>}<span class="cm">,</span> <span class="i">$JoinedPath</span><span class="sc">;</span> + 217 <span class="s">}</span> + 218 <span class="k">else</span> <span class="s">{</span> + 219 <span class="c"># Create a new edge and associate path property...</span> + 220 <span class="k">my</span><span class="s">(</span><span class="i">@NewPaths</span><span class="s">)</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 221 <span class="k">push</span> <span class="i">@NewPaths</span><span class="cm">,</span> <span class="i">$JoinedPath</span><span class="sc">;</span> + 222 <span class="i">$This</span><span class="i">->AddEdge</span><span class="s">(</span><span class="i">$JoinedPathStartVertexID</span><span class="cm">,</span> <span class="i">$JoinedPathEndVertexID</span><span class="s">)</span><span class="sc">;</span> + 223 <span class="i">$This</span><span class="i">->SetEdgeProperty</span><span class="s">(</span><span class="i">$PathsPropertyName</span><span class="cm">,</span> \<span class="i">@NewPaths</span><span class="cm">,</span> <span class="i">$JoinedPathStartVertexID</span><span class="cm">,</span> <span class="i">$JoinedPathEndVertexID</span><span class="s">)</span><span class="sc">;</span> + 224 <span class="s">}</span> + 225 <span class="s">}</span> + 226 <span class="s">}</span> + 227 <span class="s">}</span> + 228 <span class="i">$This</span><span class="i">->DeleteVertex</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> + 229 + 230 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 231 <span class="s">}</span> + 232 + 233 <span class="c"># Decide whether to give up cycles detection using collapse vertex methodology...</span> + 234 <span class="c">#</span> +<a name="_IsTimeToGiveUpCyclesDetection-"></a> 235 <span class="k">sub </span><span class="m">_IsTimeToGiveUpCyclesDetection</span> <span class="s">{</span> + 236 <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> + 237 + 238 <span class="k">return</span> <span class="s">(</span><span class="s">(</span><span class="k">time</span> - <span class="i">$This</span>->{<span class="w">StartTime</span>}<span class="s">)</span> > <span class="i">$This</span>->{<span class="w">MaxAllowedTime</span>}<span class="s">)</span> ? <span class="n">1</span> <span class="co">:</span> <span class="n">0</span><span class="sc">;</span> + 239 <span class="s">}</span> + 240 + 241 <span class="c"># Delete vertices with degree less than a specifed degree...</span> + 242 <span class="c">#</span> +<a name="DeleteVerticesWithDegreeLessThan-"></a> 243 <span class="k">sub </span><span class="m">DeleteVerticesWithDegreeLessThan</span> <span class="s">{</span> + 244 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Degree</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 245 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 246 + 247 <span class="k">while</span> <span class="s">(</span><span class="i">@VertexIDs</span> = <span class="i">$This</span><span class="i">->GetVerticesWithDegreeLessThan</span><span class="s">(</span><span class="i">$Degree</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 248 <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="i">@VertexIDs</span><span class="s">)</span> <span class="s">{</span> + 249 <span class="i">$This</span><span class="i">->DeleteVertex</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> + 250 <span class="s">}</span> + 251 <span class="s">}</span> + 252 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 253 <span class="s">}</span> + 254 + 255 <span class="c"># Get paths associated with edges...</span> + 256 <span class="c">#</span> +<a name="GetPaths-"></a> 257 <span class="k">sub </span><span class="m">GetPaths</span> <span class="s">{</span> + 258 <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> + 259 <span class="k">my</span><span class="s">(</span><span class="i">$PathsRef</span><span class="cm">,</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@PathsList</span><span class="s">)</span><span class="sc">;</span> + 260 + 261 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@PathsList</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 262 <span class="i">@PathsList</span> = <span class="i">$This</span><span class="i">->GetEdgesProperty</span><span class="s">(</span><span class="i">$PathsPropertyName</span><span class="s">)</span><span class="sc">;</span> + 263 <span class="k">for</span> <span class="i">$PathsRef</span> <span class="s">(</span><span class="i">@PathsList</span><span class="s">)</span> <span class="s">{</span> + 264 <span class="k">push</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$PathsRef</span>}<span class="sc">;</span> + 265 <span class="s">}</span> + 266 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@Paths</span> <span class="co">:</span> <span class="k">scalar</span> <span class="i">@Paths</span><span class="sc">;</span> + 267 <span class="s">}</span> + 268 + 269 <span class="c"># Get paths associated with edges which make a cylce...</span> + 270 <span class="c">#</span> +<a name="GetCyclicPaths-"></a> 271 <span class="k">sub </span><span class="m">GetCyclicPaths</span> <span class="s">{</span> + 272 <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> + 273 <span class="k">my</span><span class="s">(</span><span class="i">$PathsRef</span><span class="cm">,</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@PathsList</span><span class="s">)</span><span class="sc">;</span> + 274 + 275 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@PathsList</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 276 <span class="i">@PathsList</span> = <span class="i">$This</span><span class="i">->GetGraphProperty</span><span class="s">(</span><span class="i">$CyclicPathsPropertyName</span><span class="s">)</span><span class="sc">;</span> + 277 <span class="j">PATHS:</span> <span class="k">for</span> <span class="i">$PathsRef</span> <span class="s">(</span><span class="i">@PathsList</span><span class="s">)</span> <span class="s">{</span> + 278 <span class="k">if</span> <span class="s">(</span>!<span class="s">(</span><span class="k">defined</span><span class="s">(</span><span class="i">$PathsRef</span><span class="s">)</span> && <span class="i">@</span>{<span class="i">$PathsRef</span>}<span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 279 <span class="k">next</span> <span class="j">PATHS</span><span class="sc">;</span> + 280 <span class="s">}</span> + 281 <span class="k">push</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$PathsRef</span>}<span class="sc">;</span> + 282 <span class="s">}</span> + 283 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@Paths</span> <span class="co">:</span> <span class="k">scalar</span> <span class="i">@Paths</span><span class="sc">;</span> + 284 <span class="s">}</span> + 285 + 286 <span class="c"># Is it a path graph object?</span> +<a name="IsPathGraph-"></a> 287 <span class="k">sub </span><span class="m">IsPathGraph ($)</span> <span class="s">{</span> + 288 <span class="k">my</span><span class="s">(</span><span class="i">$Object</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 289 + 290 <span class="k">return</span> <span class="i">_IsPathGraph</span><span class="s">(</span><span class="i">$Object</span><span class="s">)</span><span class="sc">;</span> + 291 <span class="s">}</span> + 292 + 293 <span class="c"># Return a string containg data for PathGraph object...</span> +<a name="StringifyPathGraph-"></a> 294 <span class="k">sub </span><span class="m">StringifyPathGraph</span> <span class="s">{</span> + 295 <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> + 296 <span class="k">my</span><span class="s">(</span><span class="i">$PathGraphString</span><span class="s">)</span><span class="sc">;</span> + 297 + 298 <span class="i">$PathGraphString</span> = <span class="q">'PathGraph:'</span> . <span class="i">$This</span><span class="i">->StringifyVerticesAndEdges</span><span class="s">(</span><span class="s">)</span> . <span class="q">'; '</span> . <span class="i">$This</span><span class="i">->StringifyProperties</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 299 + 300 <span class="k">return</span> <span class="i">$PathGraphString</span><span class="sc">;</span> + 301 <span class="s">}</span> + 302 + 303 <span class="c"># Is it a PathGraph object?</span> +<a name="_IsPathGraph-"></a> 304 <span class="k">sub </span><span class="m">_IsPathGraph</span> <span class="s">{</span> + 305 <span class="k">my</span><span class="s">(</span><span class="i">$Object</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 306 + 307 <span class="k">return</span> <span class="s">(</span><span class="i">Scalar::Util::blessed</span><span class="s">(</span><span class="i">$Object</span><span class="s">)</span> && <span class="i">$Object</span><span class="i">->isa</span><span class="s">(</span><span class="i">$ClassName</span><span class="s">)</span><span class="s">)</span> ? <span class="n">1</span> <span class="co">:</span> <span class="n">0</span><span class="sc">;</span> + 308 <span class="s">}</span> + 309 +<a name="EOF-"></a></pre> +<p> </p> +<br /> +<center> +<img src="../../../images/h2o2.png"> +</center> +</body> +</html>