Mercurial > repos > deepakjadmin > mayatool3_test3
comparison mayachemtools/docs/modules/html/code/PathsTraversal.html @ 0:73ae111cf86f draft
Uploaded
| author | deepakjadmin |
|---|---|
| date | Wed, 20 Jan 2016 11:55:01 -0500 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| -1:000000000000 | 0:73ae111cf86f |
|---|---|
| 1 <html> | |
| 2 <head> | |
| 3 <title>MayaChemTools:Code:Graph::PathsTraversal.pm</title> | |
| 4 <meta http-equiv="content-type" content="text/html;charset=utf-8"> | |
| 5 <link rel="stylesheet" type="text/css" href="../../../css/MayaChemToolsCode.css"> | |
| 6 </head> | |
| 7 <body leftmargin="20" rightmargin="20" topmargin="10" bottommargin="10"> | |
| 8 <br/> | |
| 9 <center> | |
| 10 <a href="http://www.mayachemtools.org" title="MayaChemTools Home"><img src="../../../images/MayaChemToolsLogo.gif" border="0" alt="MayaChemTools"></a> | |
| 11 </center> | |
| 12 <br/> | |
| 13 <pre> | |
| 14 <a name="package-Graph::PathsTraversal-"></a> 1 <span class="k">package </span><span class="i">Graph::PathsTraversal</span><span class="sc">;</span> | |
| 15 2 <span class="c">#</span> | |
| 16 3 <span class="c"># $RCSfile: PathsTraversal.pm,v $</span> | |
| 17 4 <span class="c"># $Date: 2015/02/28 20:49:06 $</span> | |
| 18 5 <span class="c"># $Revision: 1.29 $</span> | |
| 19 6 <span class="c">#</span> | |
| 20 7 <span class="c"># Author: Manish Sud <msud@san.rr.com></span> | |
| 21 8 <span class="c">#</span> | |
| 22 9 <span class="c"># Copyright (C) 2015 Manish Sud. All rights reserved.</span> | |
| 23 10 <span class="c">#</span> | |
| 24 11 <span class="c"># This file is part of MayaChemTools.</span> | |
| 25 12 <span class="c">#</span> | |
| 26 13 <span class="c"># MayaChemTools is free software; you can redistribute it and/or modify it under</span> | |
| 27 14 <span class="c"># the terms of the GNU Lesser General Public License as published by the Free</span> | |
| 28 15 <span class="c"># Software Foundation; either version 3 of the License, or (at your option) any</span> | |
| 29 16 <span class="c"># later version.</span> | |
| 30 17 <span class="c">#</span> | |
| 31 18 <span class="c"># MayaChemTools is distributed in the hope that it will be useful, but without</span> | |
| 32 19 <span class="c"># any warranty; without even the implied warranty of merchantability of fitness</span> | |
| 33 20 <span class="c"># for a particular purpose. See the GNU Lesser General Public License for more</span> | |
| 34 21 <span class="c"># details.</span> | |
| 35 22 <span class="c">#</span> | |
| 36 23 <span class="c"># You should have received a copy of the GNU Lesser General Public License</span> | |
| 37 24 <span class="c"># along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or</span> | |
| 38 25 <span class="c"># write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,</span> | |
| 39 26 <span class="c"># Boston, MA, 02111-1307, USA.</span> | |
| 40 27 <span class="c">#</span> | |
| 41 28 | |
| 42 29 <span class="k">use</span> <span class="w">strict</span><span class="sc">;</span> | |
| 43 30 <span class="k">use</span> <span class="w">Carp</span><span class="sc">;</span> | |
| 44 31 <span class="k">use</span> <span class="w">Exporter</span><span class="sc">;</span> | |
| 45 32 <span class="k">use</span> <span class="w">Graph</span><span class="sc">;</span> | |
| 46 33 <span class="k">use</span> <span class="w">Graph::Path</span><span class="sc">;</span> | |
| 47 34 | |
| 48 35 <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> | |
| 49 36 | |
| 50 37 <span class="i">@ISA</span> = <span class="q">qw(Exporter)</span><span class="sc">;</span> | |
| 51 38 <span class="i">@EXPORT</span> = <span class="q">qw()</span><span class="sc">;</span> | |
| 52 39 <span class="i">@EXPORT_OK</span> = <span class="q">qw()</span><span class="sc">;</span> | |
| 53 40 | |
| 54 41 <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> | |
| 55 42 | |
| 56 43 <span class="c"># Setup class variables...</span> | |
| 57 44 <span class="k">my</span><span class="s">(</span><span class="i">$ClassName</span><span class="s">)</span><span class="sc">;</span> | |
| 58 45 <span class="i">_InitializeClass</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 59 46 | |
| 60 47 <span class="c"># Overload Perl functions...</span> | |
| 61 48 <span class="k">use</span> <span class="w">overload</span> <span class="q">'""'</span> <span class="cm">=></span> <span class="q">'StringifyPathsTraversal'</span><span class="sc">;</span> | |
| 62 49 | |
| 63 50 <span class="c"># Class constructor...</span> | |
| 64 <a name="new-"></a> 51 <span class="k">sub </span><span class="m">new</span> <span class="s">{</span> | |
| 65 52 <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> | |
| 66 53 | |
| 67 54 <span class="c"># Initialize object...</span> | |
| 68 55 <span class="k">my</span> <span class="i">$This</span> = <span class="s">{</span><span class="s">}</span><span class="sc">;</span> | |
| 69 56 <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> | |
| 70 57 <span class="i">$This</span><span class="i">->_InitializePathsTraversal</span><span class="s">(</span><span class="i">$Graph</span><span class="s">)</span><span class="sc">;</span> | |
| 71 58 | |
| 72 59 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 73 60 <span class="s">}</span> | |
| 74 61 | |
| 75 62 <span class="c"># Initialize object data...</span> | |
| 76 <a name="_InitializePathsTraversal-"></a> 63 <span class="k">sub </span><span class="m">_InitializePathsTraversal</span> <span class="s">{</span> | |
| 77 64 <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> | |
| 78 65 | |
| 79 66 <span class="c"># Graph object...</span> | |
| 80 67 <span class="i">$This</span>->{<span class="w">Graph</span>} = <span class="i">$Graph</span><span class="sc">;</span> | |
| 81 68 | |
| 82 69 <span class="c"># Traversal mode: Vertex or Path</span> | |
| 83 70 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">''</span><span class="sc">;</span> | |
| 84 71 | |
| 85 72 <span class="c"># Traversal type: DFS, DFSWithLimit, BFS, BFSWithLimit...</span> | |
| 86 73 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">''</span><span class="sc">;</span> | |
| 87 74 | |
| 88 75 <span class="c"># For finding root vertex and controlling search...</span> | |
| 89 76 <span class="k">my</span><span class="s">(</span><span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> | |
| 90 77 <span class="i">@VertexIDs</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 91 78 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesToVisit</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 92 79 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesToVisit</span>}}{ <span class="i">@VertexIDs</span> } = <span class="i">@VertexIDs</span><span class="sc">;</span> | |
| 93 80 | |
| 94 81 <span class="c"># Root vertex of all visited vertices...</span> | |
| 95 82 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesRoots</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 96 83 | |
| 97 84 <span class="c"># Visited vertices...</span> | |
| 98 85 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VisitedVertices</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 99 86 | |
| 100 87 <span class="c"># Finished vertices...</span> | |
| 101 88 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">FinishedVertices</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 102 89 | |
| 103 90 <span class="c"># List of active vertices during DFS/BFS search...</span> | |
| 104 91 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 105 92 | |
| 106 93 <span class="c"># List of ordered vertices traversed during DFS/BFS search...</span> | |
| 107 94 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 108 95 | |
| 109 96 <span class="c"># Vertex neighbors during traversal...</span> | |
| 110 97 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 111 98 | |
| 112 99 <span class="c"># Vertices depth from root...</span> | |
| 113 100 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesDepth</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 114 101 | |
| 115 102 <span class="c"># Predecessor of each vertex during vertex traversal. For root vertex, it's root itself...</span> | |
| 116 103 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 117 104 | |
| 118 105 <span class="c"># Successors of each vertex during vertex traversal...</span> | |
| 119 106 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 120 107 | |
| 121 108 <span class="c"># Vertices at different neighborhood levels during vertex traversal...</span> | |
| 122 109 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoods</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 123 110 | |
| 124 111 <span class="c"># Vertices, along with their successors, at different neighborhood levels during vertex traversal...</span> | |
| 125 112 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoodsWithSuccessors</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 126 113 | |
| 127 114 <span class="c"># Visited edges during Path TraversalMode...</span> | |
| 128 115 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VisitedEdges</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 129 116 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">From</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 130 117 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">To</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 131 118 | |
| 132 119 <span class="c"># Vertex path during Path TraversalMode...</span> | |
| 133 120 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 134 121 | |
| 135 122 <span class="c"># Allow cycles in paths during VertexNeighborhood TraversalMode. By default, cycles are not allowed</span> | |
| 136 123 <span class="c"># during vertex traversal: a vertex is only visited once during BFS search for neighborhoods. For</span> | |
| 137 124 <span class="c"># neighborhood vertices search during successors identification, vertex cycles are explicity allowed</span> | |
| 138 125 <span class="c"># to indentify all successors.</span> | |
| 139 126 <span class="i">$This</span>->{<span class="w">AllowVertexCycles</span>} = <span class="n">0</span><span class="sc">;</span> | |
| 140 127 | |
| 141 128 <span class="c"># Allow cycles in paths during Path TraversalMode...</span> | |
| 142 129 <span class="i">$This</span>->{<span class="w">AllowPathCycles</span>} = <span class="n">1</span><span class="sc">;</span> | |
| 143 130 | |
| 144 131 <span class="c"># Cycle closure vertices during Path TraversalMode...</span> | |
| 145 132 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">CycleClosureVertices</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 146 133 | |
| 147 134 <span class="c"># Paths traversed during search...</span> | |
| 148 135 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 149 136 | |
| 150 137 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 151 138 <span class="s">}</span> | |
| 152 139 | |
| 153 140 <span class="c"># Initialize class ...</span> | |
| 154 <a name="_InitializeClass-"></a> 141 <span class="k">sub </span><span class="m">_InitializeClass</span> <span class="s">{</span> | |
| 155 142 <span class="c">#Class name...</span> | |
| 156 143 <span class="i">$ClassName</span> = <span class="w">__PACKAGE__</span><span class="sc">;</span> | |
| 157 144 <span class="s">}</span> | |
| 158 145 | |
| 159 146 <span class="c"># Perform a depth first search (DFS)...</span> | |
| 160 147 <span class="c">#</span> | |
| 161 <a name="PerformDepthFirstSearch-"></a> 148 <span class="k">sub </span><span class="m">PerformDepthFirstSearch</span> <span class="s">{</span> | |
| 162 149 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 163 150 | |
| 164 151 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 165 152 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 166 153 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformDepthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 167 154 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 168 155 <span class="s">}</span> | |
| 169 156 <span class="s">}</span> | |
| 170 157 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformVertexSearch</span><span class="s">(</span><span class="q">"DFS"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 171 158 <span class="s">}</span> | |
| 172 159 | |
| 173 160 <span class="c"># Perform a depth first search (DFS) with limit on depth...</span> | |
| 174 161 <span class="c">#</span> | |
| 175 <a name="PerformDepthFirstSearchWithLimit-"></a> 162 <span class="k">sub </span><span class="m">PerformDepthFirstSearchWithLimit</span> <span class="s">{</span> | |
| 176 163 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 177 164 | |
| 178 165 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$DepthLimit</span><span class="s">)</span> <span class="s">{</span> | |
| 179 166 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Depth limit must be specified..."</span><span class="sc">;</span> | |
| 180 167 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 181 168 <span class="s">}</span> | |
| 182 169 <span class="k">if</span> <span class="s">(</span><span class="i">$DepthLimit</span> < <span class="n">0</span><span class="s">)</span> <span class="s">{</span> | |
| 183 170 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer..."</span><span class="sc">;</span> | |
| 184 171 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 185 172 <span class="s">}</span> | |
| 186 173 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 187 174 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 188 175 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 189 176 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 190 177 <span class="s">}</span> | |
| 191 178 <span class="s">}</span> | |
| 192 179 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformVertexSearch</span><span class="s">(</span><span class="q">"DFSWithLimit"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> | |
| 193 180 <span class="s">}</span> | |
| 194 181 | |
| 195 182 <span class="c"># Perform a breadth first search (BFS)...</span> | |
| 196 183 <span class="c">#</span> | |
| 197 <a name="PerformBreadthFirstSearch-"></a> 184 <span class="k">sub </span><span class="m">PerformBreadthFirstSearch</span> <span class="s">{</span> | |
| 198 185 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 199 186 | |
| 200 187 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 201 188 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 202 189 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformBreadthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 203 190 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 204 191 <span class="s">}</span> | |
| 205 192 <span class="s">}</span> | |
| 206 193 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformVertexSearch</span><span class="s">(</span><span class="q">"BFS"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 207 194 <span class="s">}</span> | |
| 208 195 | |
| 209 196 <span class="c"># Perform a breadth first search (BFS) with limit...</span> | |
| 210 197 <span class="c">#</span> | |
| 211 <a name="PerformBreadthFirstSearchWithLimit-"></a> 198 <span class="k">sub </span><span class="m">PerformBreadthFirstSearchWithLimit</span> <span class="s">{</span> | |
| 212 199 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 213 200 | |
| 214 201 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$DepthLimit</span><span class="s">)</span> <span class="s">{</span> | |
| 215 202 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Depth limit must be specified..."</span><span class="sc">;</span> | |
| 216 203 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 217 204 <span class="s">}</span> | |
| 218 205 <span class="k">if</span> <span class="s">(</span><span class="i">$DepthLimit</span> < <span class="n">0</span><span class="s">)</span> <span class="s">{</span> | |
| 219 206 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer..."</span><span class="sc">;</span> | |
| 220 207 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 221 208 <span class="s">}</span> | |
| 222 209 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 223 210 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 224 211 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 225 212 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 226 213 <span class="s">}</span> | |
| 227 214 <span class="s">}</span> | |
| 228 215 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformVertexSearch</span><span class="s">(</span><span class="q">"BFSWithLimit"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> | |
| 229 216 <span class="s">}</span> | |
| 230 217 | |
| 231 218 <span class="c"># Perform appropriate vertex search...</span> | |
| 232 219 <span class="c">#</span> | |
| 233 <a name="_PerformVertexSearch-"></a> 220 <span class="k">sub </span><span class="m">_PerformVertexSearch</span> <span class="s">{</span> | |
| 234 221 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$SearchType</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$TargetVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 235 222 | |
| 236 223 <span class="c"># Setup search...</span> | |
| 237 224 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'Vertex'</span><span class="sc">;</span> | |
| 238 225 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="i">$SearchType</span><span class="sc">;</span> | |
| 239 226 | |
| 240 227 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 241 228 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> | |
| 242 229 <span class="s">}</span> | |
| 243 230 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$DepthLimit</span><span class="s">)</span> <span class="s">{</span> | |
| 244 231 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> | |
| 245 232 <span class="s">}</span> | |
| 246 233 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$TargetVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 247 234 <span class="i">$This</span>->{<span class="w">TargetVertex</span>} = <span class="i">$TargetVertexID</span><span class="sc">;</span> | |
| 248 235 <span class="s">}</span> | |
| 249 236 | |
| 250 237 <span class="c"># Perform search...</span> | |
| 251 238 <span class="k">return</span> <span class="i">$This</span><span class="i">->_TraverseGraph</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 252 239 <span class="s">}</span> | |
| 253 240 | |
| 254 241 <span class="c"># Perform DFS or BFS traversal with or without any limits...</span> | |
| 255 242 <span class="c">#</span> | |
| 256 <a name="_TraverseGraph-"></a> 243 <span class="k">sub </span><span class="m">_TraverseGraph</span> <span class="s">{</span> | |
| 257 244 <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> | |
| 258 245 <span class="k">my</span><span class="s">(</span><span class="i">$ProcessingVertices</span><span class="cm">,</span> <span class="i">$CurrentVertexID</span><span class="cm">,</span> <span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 259 246 | |
| 260 247 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} !~ <span class="q">/^(Vertex|Path|VertexNeighborhood)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 261 248 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 262 249 <span class="s">}</span> | |
| 263 250 | |
| 264 251 <span class="i">$ProcessingVertices</span> = <span class="n">1</span><span class="sc">;</span> | |
| 265 252 | |
| 266 253 <span class="j">VERTICES:</span> <span class="k">while</span> <span class="s">(</span><span class="i">$ProcessingVertices</span><span class="s">)</span> <span class="s">{</span> | |
| 267 254 <span class="c"># Set root vertex...</span> | |
| 268 255 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 269 256 <span class="k">my</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 270 257 | |
| 271 258 <span class="i">$RootVertexID</span> = <span class="i">$This</span><span class="i">->_GetRootVertex</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 272 259 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 273 260 <span class="i">$ProcessingVertices</span> = <span class="n">0</span><span class="sc">;</span> <span class="k">next</span> <span class="j">VERTICES</span><span class="sc">;</span> | |
| 274 261 <span class="s">}</span> | |
| 275 262 <span class="i">$This</span><span class="i">->_ProcessVisitedVertex</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 276 263 <span class="s">}</span> | |
| 277 264 | |
| 278 265 <span class="c"># Get current active vertex...</span> | |
| 279 266 <span class="i">$CurrentVertexID</span> = <span class="i">$This</span><span class="i">->_GetActiveVertex</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 280 267 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$CurrentVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 281 268 <span class="i">$ProcessingVertices</span> = <span class="n">0</span><span class="sc">;</span> <span class="k">next</span> <span class="j">VERTICES</span><span class="sc">;</span> | |
| 282 269 <span class="s">}</span> | |
| 283 270 | |
| 284 271 <span class="c"># Get next available neighbor of current vertex...</span> | |
| 285 272 <span class="c">#</span> | |
| 286 273 <span class="i">$NeighborVertexID</span> = <span class="i">$This</span><span class="i">->_GetNeighborVertex</span><span class="s">(</span><span class="i">$CurrentVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 287 274 | |
| 288 275 <span class="c"># Process neighbor or current vertex...</span> | |
| 289 276 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$NeighborVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 290 277 <span class="i">$This</span><span class="i">->_ProcessVisitedVertex</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$CurrentVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 291 278 <span class="s">}</span> | |
| 292 279 <span class="k">else</span> <span class="s">{</span> | |
| 293 280 <span class="c"># Finished with all neighbors for current vertex...</span> | |
| 294 281 <span class="i">$This</span><span class="i">->_ProcessFinishedVertex</span><span class="s">(</span><span class="i">$CurrentVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 295 282 <span class="s">}</span> | |
| 296 283 <span class="s">}</span> | |
| 297 284 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 298 285 <span class="s">}</span> | |
| 299 286 | |
| 300 287 <span class="c"># Get root vertex to start the search...</span> | |
| 301 288 <span class="c">#</span> | |
| 302 289 <span class="c"># Notes:</span> | |
| 303 290 <span class="c"># . User specification of root vertex forces traversal in a specific connected component</span> | |
| 304 291 <span class="c"># of graph; To traverse find all connected components, perform traversal without specification of</span> | |
| 305 292 <span class="c"># a root vertex.</span> | |
| 306 293 <span class="c">#</span> | |
| 307 <a name="_GetRootVertex-"></a> 294 <span class="k">sub </span><span class="m">_GetRootVertex</span> <span class="s">{</span> | |
| 308 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> | |
| 309 296 <span class="k">my</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 310 297 | |
| 311 298 <span class="c"># Check for specified root vertex and constrain traversal to specific connected</span> | |
| 312 299 <span class="c"># component by setting root limit...</span> | |
| 313 300 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">RootVertex</span>}<span class="s">)</span> <span class="s">{</span> | |
| 314 301 <span class="i">$RootVertexID</span> = <span class="i">$This</span>->{<span class="w">RootVertex</span>}<span class="sc">;</span> | |
| 315 302 <span class="k">delete</span> <span class="i">$This</span>->{<span class="w">RootVertex</span>}<span class="sc">;</span> | |
| 316 303 <span class="i">$This</span>->{<span class="w">RootVertexSpecified</span>} = <span class="n">1</span><span class="sc">;</span> | |
| 317 304 | |
| 318 305 <span class="k">return</span> <span class="i">$RootVertexID</span><span class="sc">;</span> | |
| 319 306 <span class="s">}</span> | |
| 320 307 <span class="c"># Traversal limited to connected component containing specified root vertex...</span> | |
| 321 308 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">RootVertexSpecified</span>}<span class="s">)</span> <span class="s">{</span> | |
| 322 309 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 323 310 <span class="s">}</span> | |
| 324 311 | |
| 325 312 <span class="c"># Use first vertex in sorted available vertices list to get root vertex. Vertex</span> | |
| 326 313 <span class="c"># with largest degree could also be used as root vertex. However, for all</span> | |
| 327 314 <span class="c"># practical purposes, any arbitrary vertex can be used as root vertex to</span> | |
| 328 315 <span class="c"># start search for another disconnected component of the graph.</span> | |
| 329 316 <span class="c">#</span> | |
| 330 317 <span class="k">my</span><span class="s">(</span><span class="i">@VerticesToVisit</span><span class="s">)</span><span class="sc">;</span> | |
| 331 318 | |
| 332 319 <span class="i">$RootVertexID</span> = <span class="k">undef</span><span class="sc">;</span> <span class="i">@VerticesToVisit</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 333 320 <span class="i">@VerticesToVisit</span> = <span class="k">sort</span> <span class="s">{</span> <span class="i">$a</span> <=> <span class="i">$b</span> <span class="s">}</span> <span class="k">keys</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesToVisit</span>}}<span class="sc">;</span> | |
| 334 321 <span class="k">if</span> <span class="s">(</span><span class="i">@VerticesToVisit</span><span class="s">)</span> <span class="s">{</span> | |
| 335 322 <span class="i">$RootVertexID</span> = <span class="i">$VerticesToVisit</span>[<span class="n">0</span>]<span class="sc">;</span> | |
| 336 323 <span class="s">}</span> | |
| 337 324 <span class="k">return</span> <span class="i">$RootVertexID</span><span class="sc">;</span> | |
| 338 325 <span class="s">}</span> | |
| 339 326 | |
| 340 327 <span class="c"># Get current or new active vertex for DFS/BFS traversals...</span> | |
| 341 328 <span class="c">#</span> | |
| 342 <a name="_GetActiveVertex-"></a> 329 <span class="k">sub </span><span class="m">_GetActiveVertex</span> <span class="s">{</span> | |
| 343 330 <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> | |
| 344 331 <span class="k">my</span><span class="s">(</span><span class="i">$ActiveVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 345 332 | |
| 346 333 <span class="i">$ActiveVertexID</span> = <span class="k">undef</span><span class="sc">;</span> | |
| 347 334 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalType</span>} =~ <span class="q">/^(DFS|DFSWithLimit)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 348 335 <span class="c"># For DFS, it's last vertex in LIFO queue...</span> | |
| 349 336 <span class="i">$ActiveVertexID</span> = <span class="i">$This</span>->{<span class="w">ActiveVertices</span>}[<span class="n">-1</span>]<span class="sc">;</span> | |
| 350 337 <span class="s">}</span> | |
| 351 338 <span class="k">elsif</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalType</span>} =~ <span class="q">/^(BFS|BFSWithLimit)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 352 339 <span class="c"># For BFS, it's first vertex in FIFO queue...</span> | |
| 353 340 <span class="i">$ActiveVertexID</span> = <span class="i">$This</span>->{<span class="w">ActiveVertices</span>}[<span class="n">0</span>]<span class="sc">;</span> | |
| 354 341 <span class="s">}</span> | |
| 355 342 <span class="k">return</span> <span class="i">$ActiveVertexID</span><span class="sc">;</span> | |
| 356 343 <span class="s">}</span> | |
| 357 344 | |
| 358 345 <span class="c"># Get available neigbor of specified vertex...</span> | |
| 359 346 <span class="c">#</span> | |
| 360 <a name="_GetNeighborVertex-"></a> 347 <span class="k">sub </span><span class="m">_GetNeighborVertex</span> <span class="s">{</span> | |
| 361 348 <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> | |
| 362 349 | |
| 363 350 <span class="c"># Retrieve neighbors for vertex...</span> | |
| 364 351 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 365 352 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 366 353 | |
| 367 354 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 368 355 <span class="c"># Only collect neighbors to visit below specified depth limit...</span> | |
| 369 356 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>} < <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 370 357 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}}<span class="cm">,</span> <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->GetNeighbors</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 371 358 <span class="s">}</span> | |
| 372 359 <span class="k">else</span> <span class="s">{</span> | |
| 373 360 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">RootVertexSpecified</span>}<span class="s">)</span> <span class="s">{</span> | |
| 374 361 <span class="c"># Mark all other downstream neighbor vertices to be ignored from any further</span> | |
| 375 362 <span class="c"># processing and avoid selection of a new root...</span> | |
| 376 363 <span class="i">$This</span><span class="i">->_IgnoreDownstreamNeighbors</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 377 364 <span class="s">}</span> | |
| 378 365 <span class="s">}</span> | |
| 379 366 <span class="s">}</span> | |
| 380 367 <span class="k">elsif</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">TargetVertex</span>}<span class="s">)</span> <span class="s">{</span> | |
| 381 368 <span class="k">if</span> <span class="s">(</span><span class="i">$VertexID</span> != <span class="i">$This</span>->{<span class="w">TargetVertex</span>}<span class="s">)</span> <span class="s">{</span> | |
| 382 369 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}}<span class="cm">,</span> <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->GetNeighbors</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 383 370 <span class="s">}</span> | |
| 384 371 <span class="s">}</span> | |
| 385 372 <span class="k">else</span> <span class="s">{</span> | |
| 386 373 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}}<span class="cm">,</span> <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->GetNeighbors</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 387 374 <span class="s">}</span> | |
| 388 375 <span class="s">}</span> | |
| 389 376 | |
| 390 377 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} =~ <span class="q">/^Path$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 391 378 <span class="c"># Get available neighbor for path search...</span> | |
| 392 379 <span class="k">return</span> <span class="i">$This</span><span class="i">->_GetNeighborVertexDuringPathTraversal</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 393 380 <span class="s">}</span> | |
| 394 381 <span class="k">elsif</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} =~ <span class="q">/^Vertex$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 395 382 <span class="c"># Get unvisited neighbor for vertex search...</span> | |
| 396 383 <span class="k">return</span> <span class="i">$This</span><span class="i">->_GetNeighborVertexDuringVertexTraversal</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 397 384 <span class="s">}</span> | |
| 398 385 <span class="k">elsif</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} =~ <span class="q">/^VertexNeighborhood$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 399 386 <span class="c"># Get available neighbor during vertex neighborhood search...</span> | |
| 400 387 <span class="k">return</span> <span class="i">$This</span><span class="i">->_GetNeighborVertexDuringVertexNeighborhoodTraversal</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 401 388 <span class="s">}</span> | |
| 402 389 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 403 390 <span class="s">}</span> | |
| 404 391 | |
| 405 392 <span class="c"># Get unvisited neighbor of specified vertex during vertex traversal...</span> | |
| 406 393 <span class="c">#</span> | |
| 407 <a name="_GetNeighborVertexDuringVertexTraversal-"></a> 394 <span class="k">sub </span><span class="m">_GetNeighborVertexDuringVertexTraversal</span> <span class="s">{</span> | |
| 408 395 <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> | |
| 409 396 <span class="k">my</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 410 397 | |
| 411 398 <span class="c"># Get unvisited neighbor...</span> | |
| 412 399 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="k">undef</span><span class="sc">;</span> | |
| 413 400 <span class="j">NEIGHBOR:</span> <span class="k">for</span> <span class="i">$NeighborVertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 414 401 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedVertices</span>}{<span class="i">$NeighborVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 415 402 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> | |
| 416 403 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 417 404 <span class="s">}</span> | |
| 418 405 <span class="s">}</span> | |
| 419 406 <span class="k">return</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="sc">;</span> | |
| 420 407 <span class="s">}</span> | |
| 421 408 | |
| 422 409 <span class="c"># Get available neighbor of specified vertex during vertex neighborhood traversal...</span> | |
| 423 410 <span class="c">#</span> | |
| 424 <a name="_GetNeighborVertexDuringVertexNeighborhoodTraversal-"></a> 411 <span class="k">sub </span><span class="m">_GetNeighborVertexDuringVertexNeighborhoodTraversal</span> <span class="s">{</span> | |
| 425 412 <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> | |
| 426 413 <span class="k">my</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 427 414 | |
| 428 415 <span class="c"># Get available neighbor...</span> | |
| 429 416 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="k">undef</span><span class="sc">;</span> | |
| 430 417 <span class="j">NEIGHBOR:</span> <span class="k">for</span> <span class="i">$NeighborVertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 431 418 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedVertices</span>}{<span class="i">$NeighborVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 432 419 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> | |
| 433 420 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 434 421 <span class="s">}</span> | |
| 435 422 <span class="c"># Look for any unvisited edge back to visited vertex...</span> | |
| 436 423 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span><span class="i">->_IsVisitedEdge</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$NeighborVertexID</span><span class="s">)</span> || <span class="i">$This</span><span class="i">->_IsVisitedEdge</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 437 424 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 438 425 <span class="s">}</span> | |
| 439 426 <span class="c"># Check its depth...</span> | |
| 440 427 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 441 428 <span class="k">if</span> <span class="s">(</span><span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>} + <span class="n">1</span><span class="s">)</span> > <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 442 429 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 443 430 <span class="s">}</span> | |
| 444 431 <span class="s">}</span> | |
| 445 432 <span class="c"># Its an edge that makes a cycle during BFS search...</span> | |
| 446 433 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">AllowVertexCycles</span>}<span class="s">)</span> <span class="s">{</span> | |
| 447 434 <span class="i">$This</span>->{<span class="w">CycleClosureVertices</span>}{<span class="i">$NeighborVertexID</span>} = <span class="n">1</span><span class="sc">;</span> | |
| 448 435 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> | |
| 449 436 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 450 437 <span class="s">}</span> | |
| 451 438 <span class="s">}</span> | |
| 452 439 <span class="k">return</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="sc">;</span> | |
| 453 440 <span class="s">}</span> | |
| 454 441 | |
| 455 442 <span class="c"># Get available neighbor of specified vertex during path traversal...</span> | |
| 456 443 <span class="c">#</span> | |
| 457 <a name="_GetNeighborVertexDuringPathTraversal-"></a> 444 <span class="k">sub </span><span class="m">_GetNeighborVertexDuringPathTraversal</span> <span class="s">{</span> | |
| 458 445 <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> | |
| 459 446 <span class="k">my</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 460 447 | |
| 461 448 <span class="c"># Get unvisited neighbor...</span> | |
| 462 449 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="k">undef</span><span class="sc">;</span> | |
| 463 450 <span class="j">NEIGHBOR:</span> <span class="k">for</span> <span class="i">$NeighborVertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighbors</span>}{<span class="i">$VertexID</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 464 451 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedVertices</span>}{<span class="i">$NeighborVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 465 452 <span class="c"># An unvisited vertex...</span> | |
| 466 453 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> | |
| 467 454 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 468 455 <span class="s">}</span> | |
| 469 456 <span class="c"># Look for any unvisited edge back to visited vertex...</span> | |
| 470 457 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span><span class="i">->_IsVisitedEdge</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$NeighborVertexID</span><span class="s">)</span> || <span class="i">$This</span><span class="i">->_IsVisitedEdge</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 471 458 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 472 459 <span class="s">}</span> | |
| 473 460 <span class="c"># Check its depth...</span> | |
| 474 461 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 475 462 <span class="k">if</span> <span class="s">(</span><span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>} + <span class="n">1</span><span class="s">)</span> >= <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 476 463 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 477 464 <span class="s">}</span> | |
| 478 465 <span class="s">}</span> | |
| 479 466 | |
| 480 467 <span class="c"># It's the edge final edge of a cycle in case $NeighborVertexID is already in the path; otherwise, it's</span> | |
| 481 468 <span class="c"># part of the path from a different direction in a cycle or a left over vertex during Limit search.</span> | |
| 482 469 <span class="c">#</span> | |
| 483 470 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span><span class="i">->_IsCycleClosureEdge</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$NeighborVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 484 471 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">AllowPathCycles</span>}<span class="s">)</span> <span class="s">{</span> | |
| 485 472 <span class="i">$This</span>->{<span class="w">CycleClosureVertices</span>}{<span class="i">$NeighborVertexID</span>} = <span class="n">1</span><span class="sc">;</span> | |
| 486 473 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> | |
| 487 474 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 488 475 <span class="s">}</span> | |
| 489 476 <span class="s">}</span> | |
| 490 477 <span class="k">else</span> <span class="s">{</span> | |
| 491 478 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> | |
| 492 479 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 493 480 <span class="s">}</span> | |
| 494 481 <span class="s">}</span> | |
| 495 482 <span class="k">return</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="sc">;</span> | |
| 496 483 <span class="s">}</span> | |
| 497 484 | |
| 498 485 <span class="c"># Process visited vertex...</span> | |
| 499 486 <span class="c">#</span> | |
| 500 <a name="_ProcessVisitedVertex-"></a> 487 <span class="k">sub </span><span class="m">_ProcessVisitedVertex</span> <span class="s">{</span> | |
| 501 488 <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="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 502 489 | |
| 503 490 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedVertices</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 504 491 <span class="c"># Add it to active vertices list...</span> | |
| 505 492 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}}<span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 506 493 | |
| 507 494 <span class="c"># Mark vertex as visited vertex and take it out from the list of vertices to visit...</span> | |
| 508 495 <span class="i">$This</span>->{<span class="w">VisitedVertices</span>}{<span class="i">$VertexID</span>} = <span class="n">1</span><span class="sc">;</span> | |
| 509 496 <span class="k">delete</span> <span class="i">$This</span>->{<span class="w">VerticesToVisit</span>}{<span class="i">$VertexID</span>}<span class="sc">;</span> | |
| 510 497 <span class="s">}</span> | |
| 511 498 | |
| 512 499 <span class="c"># Set up root vertex, predecessor vertex and distance from root...</span> | |
| 513 500 <span class="k">if</span> <span class="s">(</span><span class="i">$VertexID</span> == <span class="i">$PredecessorVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 514 501 <span class="i">$This</span>->{<span class="w">VerticesRoots</span>}{<span class="i">$VertexID</span>} = <span class="i">$VertexID</span><span class="sc">;</span> | |
| 515 502 | |
| 516 503 <span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}{<span class="i">$VertexID</span>} = <span class="i">$VertexID</span><span class="sc">;</span> | |
| 517 504 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 518 505 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 519 506 <span class="s">}</span> | |
| 520 507 | |
| 521 508 <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>} = <span class="n">0</span><span class="sc">;</span> | |
| 522 509 | |
| 523 510 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} =~ <span class="q">/^Path$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 524 511 <span class="i">$This</span><span class="i">->_ProcessVisitedPath</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 525 512 <span class="s">}</span> | |
| 526 513 <span class="s">}</span> | |
| 527 514 <span class="k">else</span> <span class="s">{</span> | |
| 528 515 <span class="i">$This</span>->{<span class="w">VerticesRoots</span>}{<span class="i">$VertexID</span>} = <span class="i">$This</span>->{<span class="w">VerticesRoots</span>}{<span class="i">$PredecessorVertexID</span>}<span class="sc">;</span> | |
| 529 516 | |
| 530 517 <span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}{<span class="i">$VertexID</span>} = <span class="i">$PredecessorVertexID</span><span class="sc">;</span> | |
| 531 518 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$PredecessorVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 532 519 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$PredecessorVertexID</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 533 520 <span class="s">}</span> | |
| 534 521 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$PredecessorVertexID</span>}}<span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 535 522 | |
| 536 523 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 537 524 <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>} = <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$PredecessorVertexID</span>} + <span class="n">1</span><span class="sc">;</span> | |
| 538 525 <span class="s">}</span> | |
| 539 526 | |
| 540 527 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} =~ <span class="q">/^Path$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 541 528 <span class="i">$This</span><span class="i">->_ProcessVisitedPath</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 542 529 <span class="i">$This</span><span class="i">->_ProcessVisitedEdge</span><span class="s">(</span><span class="i">$PredecessorVertexID</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 543 530 <span class="s">}</span> | |
| 544 531 <span class="k">elsif</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} =~ <span class="q">/^VertexNeighborhood$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 545 532 <span class="i">$This</span><span class="i">->_ProcessVisitedEdge</span><span class="s">(</span><span class="i">$PredecessorVertexID</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 546 533 <span class="s">}</span> | |
| 547 534 <span class="s">}</span> | |
| 548 535 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 549 536 <span class="s">}</span> | |
| 550 537 | |
| 551 538 <span class="c"># Process visited path...</span> | |
| 552 539 <span class="c">#</span> | |
| 553 <a name="_ProcessVisitedPath-"></a> 540 <span class="k">sub </span><span class="m">_ProcessVisitedPath</span> <span class="s">{</span> | |
| 554 541 <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="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 555 542 | |
| 556 543 <span class="c"># Initialize VerticesPath...</span> | |
| 557 544 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 558 545 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 559 546 <span class="s">}</span> | |
| 560 547 | |
| 561 548 <span class="k">if</span> <span class="s">(</span><span class="i">$VertexID</span> == <span class="i">$PredecessorVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 562 549 <span class="c"># Starting of a path from root...</span> | |
| 563 550 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID</span>}}<span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 564 551 <span class="s">}</span> | |
| 565 552 <span class="k">else</span> <span class="s">{</span> | |
| 566 553 <span class="c"># Setup path for a vertex using path information from predecessor vertex...</span> | |
| 567 554 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">CycleClosureVertices</span>}{<span class="i">$PredecessorVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 568 555 <span class="c"># Start of a new path from predecessor vertex...</span> | |
| 569 556 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID</span>}}<span class="cm">,</span> <span class="q">"${PredecessorVertexID}-${VertexID}"</span><span class="sc">;</span> | |
| 570 557 <span class="s">}</span> | |
| 571 558 <span class="k">else</span> <span class="s">{</span> | |
| 572 559 <span class="k">my</span><span class="s">(</span><span class="i">$PredecessorVertexPath</span><span class="s">)</span><span class="sc">;</span> | |
| 573 560 <span class="k">for</span> <span class="i">$PredecessorVertexPath</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$PredecessorVertexID</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 574 561 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID</span>}}<span class="cm">,</span> <span class="q">"${PredecessorVertexPath}-${VertexID}"</span><span class="sc">;</span> | |
| 575 562 <span class="s">}</span> | |
| 576 563 <span class="s">}</span> | |
| 577 564 <span class="s">}</span> | |
| 578 565 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 579 566 <span class="s">}</span> | |
| 580 567 | |
| 581 568 <span class="c"># Process visited edge...</span> | |
| 582 569 <span class="c">#</span> | |
| 583 <a name="_ProcessVisitedEdge-"></a> 570 <span class="k">sub </span><span class="m">_ProcessVisitedEdge</span> <span class="s">{</span> | |
| 584 571 <span class="k">my</span><span class="s">(</span><span class="i">$This</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="i">@_</span><span class="sc">;</span> | |
| 585 572 | |
| 586 573 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">From</span>}->{<span class="i">$VertexID1</span>}<span class="s">)</span> <span class="s">{</span> | |
| 587 574 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">From</span>}->{<span class="i">$VertexID1</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 588 575 <span class="s">}</span> | |
| 589 576 <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">From</span>}->{<span class="i">$VertexID1</span>}->{<span class="i">$VertexID2</span>} = <span class="i">$VertexID2</span><span class="sc">;</span> | |
| 590 577 | |
| 591 578 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">To</span>}->{<span class="i">$VertexID2</span>}<span class="s">)</span> <span class="s">{</span> | |
| 592 579 <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">To</span>}->{<span class="i">$VertexID2</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 593 580 <span class="s">}</span> | |
| 594 581 <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">To</span>}->{<span class="i">$VertexID2</span>}->{<span class="i">$VertexID1</span>} = <span class="i">$VertexID1</span><span class="sc">;</span> | |
| 595 582 | |
| 596 583 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 597 584 <span class="s">}</span> | |
| 598 585 | |
| 599 586 <span class="c"># Finished processing active vertex...</span> | |
| 600 587 <span class="c">#</span> | |
| 601 <a name="_ProcessFinishedVertex-"></a> 588 <span class="k">sub </span><span class="m">_ProcessFinishedVertex</span> <span class="s">{</span> | |
| 602 589 <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> | |
| 603 590 | |
| 604 591 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">FinishedVertices</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 605 592 <span class="i">$This</span>->{<span class="w">FinishedVertices</span>}{<span class="i">$VertexID</span>} = <span class="i">$VertexID</span><span class="sc">;</span> | |
| 606 593 <span class="c"># Add vertex to list of vertices found by traversal...</span> | |
| 607 594 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 608 595 <span class="s">}</span> | |
| 609 596 | |
| 610 597 <span class="c"># Any active vertices left...</span> | |
| 611 598 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 612 599 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 613 600 <span class="s">}</span> | |
| 614 601 | |
| 615 602 <span class="c"># Take it off active vertices list...</span> | |
| 616 603 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalType</span>} =~ <span class="q">/^(DFS|DFSWithLimit)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 617 604 <span class="c"># For DFS, it's last vertex in LIFO queue...</span> | |
| 618 605 <span class="k">pop</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}}<span class="sc">;</span> | |
| 619 606 <span class="s">}</span> | |
| 620 607 <span class="k">elsif</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalType</span>} =~ <span class="q">/^(BFS|BFSWithLimit)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 621 608 <span class="c"># For BFS, it's first vertex in FIFO queue...</span> | |
| 622 609 <span class="k">shift</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}}<span class="sc">;</span> | |
| 623 610 <span class="s">}</span> | |
| 624 611 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 625 612 <span class="s">}</span> | |
| 626 613 | |
| 627 614 <span class="c"># Mark all other downstream neighbor vertices to be ignored from any further</span> | |
| 628 615 <span class="c"># processing...</span> | |
| 629 616 <span class="c">#</span> | |
| 630 <a name="_IgnoreDownstreamNeighbors-"></a> 617 <span class="k">sub </span><span class="m">_IgnoreDownstreamNeighbors</span> <span class="s">{</span> | |
| 631 618 <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="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 632 619 | |
| 633 620 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesToVisit</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 634 621 <span class="c"># Mark vertex as visited vertex and take it out from the list of vertices to visit...</span> | |
| 635 622 <span class="i">$This</span>->{<span class="w">VisitedVertices</span>}{<span class="i">$VertexID</span>} = <span class="n">1</span><span class="sc">;</span> | |
| 636 623 <span class="k">delete</span> <span class="i">$This</span>->{<span class="w">VerticesToVisit</span>}{<span class="i">$VertexID</span>}<span class="sc">;</span> | |
| 637 624 | |
| 638 625 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span><span class="s">(</span><span class="i">$PredecessorVertexID</span><span class="s">)</span> && <span class="i">$This</span>->{<span class="w">TraversalMode</span>} =~ <span class="q">/^(Path|VertexNeighborhood)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 639 626 <span class="i">$This</span><span class="i">->_ProcessVisitedEdge</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 640 627 <span class="s">}</span> | |
| 641 628 <span class="s">}</span> | |
| 642 629 <span class="k">my</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">@NeighborsVertexIDs</span><span class="s">)</span><span class="sc">;</span> | |
| 643 630 | |
| 644 631 <span class="i">@NeighborsVertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 645 632 <span class="i">@NeighborsVertexIDs</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->GetNeighbors</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 646 633 <span class="j">NEIGHBOR:</span> <span class="k">for</span> <span class="i">$NeighborVertexID</span> <span class="s">(</span><span class="i">@NeighborsVertexIDs</span><span class="s">)</span> <span class="s">{</span> | |
| 647 634 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesToVisit</span>}{<span class="i">$NeighborVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 648 635 <span class="c"># Avoid going back to predecessor vertex which has already been ignored...</span> | |
| 649 636 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 650 637 <span class="s">}</span> | |
| 651 638 <span class="i">$This</span><span class="i">->_IgnoreDownstreamNeighbors</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 652 639 <span class="s">}</span> | |
| 653 640 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 654 641 <span class="s">}</span> | |
| 655 642 | |
| 656 643 <span class="c"># Is it a visited edge?</span> | |
| 657 644 <span class="c">#</span> | |
| 658 <a name="_IsVisitedEdge-"></a> 645 <span class="k">sub </span><span class="m">_IsVisitedEdge</span> <span class="s">{</span> | |
| 659 646 <span class="k">my</span><span class="s">(</span><span class="i">$This</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="i">@_</span><span class="sc">;</span> | |
| 660 647 | |
| 661 648 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">From</span>}->{<span class="i">$VertexID1</span>}<span class="s">)</span> <span class="s">{</span> | |
| 662 649 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">From</span>}->{<span class="i">$VertexID1</span>}->{<span class="i">$VertexID2</span>}<span class="s">)</span> <span class="s">{</span> | |
| 663 650 <span class="k">return</span> <span class="n">1</span><span class="sc">;</span> | |
| 664 651 <span class="s">}</span> | |
| 665 652 <span class="s">}</span> | |
| 666 653 <span class="k">elsif</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">To</span>}->{<span class="i">$VertexID2</span>}<span class="s">)</span> <span class="s">{</span> | |
| 667 654 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VisitedEdges</span>}->{<span class="w">To</span>}->{<span class="i">$VertexID2</span>}->{<span class="i">$VertexID1</span>}<span class="s">)</span> <span class="s">{</span> | |
| 668 655 <span class="k">return</span> <span class="n">1</span><span class="sc">;</span> | |
| 669 656 <span class="s">}</span> | |
| 670 657 <span class="s">}</span> | |
| 671 658 <span class="k">return</span> <span class="n">0</span><span class="sc">;</span> | |
| 672 659 <span class="s">}</span> | |
| 673 660 | |
| 674 661 <span class="c"># Is it a cycle closure edge?</span> | |
| 675 662 <span class="c">#</span> | |
| 676 663 <span class="c"># Notes:</span> | |
| 677 664 <span class="c"># . Presence of VertexID2 in DFS path traversed for VertexID1 make it a cycle</span> | |
| 678 665 <span class="c"># closure edge...</span> | |
| 679 666 <span class="c">#</span> | |
| 680 <a name="_IsCycleClosureEdge-"></a> 667 <span class="k">sub </span><span class="m">_IsCycleClosureEdge</span> <span class="s">{</span> | |
| 681 668 <span class="k">my</span><span class="s">(</span><span class="i">$This</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="i">@_</span><span class="sc">;</span> | |
| 682 669 | |
| 683 670 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID1</span>}<span class="s">)</span> <span class="s">{</span> | |
| 684 671 <span class="k">return</span> <span class="n">0</span><span class="sc">;</span> | |
| 685 672 <span class="s">}</span> | |
| 686 673 <span class="k">my</span><span class="s">(</span><span class="i">$Path</span><span class="s">)</span><span class="sc">;</span> | |
| 687 674 <span class="k">for</span> <span class="i">$Path</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID1</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 688 675 <span class="k">if</span> <span class="s">(</span><span class="s">(</span><span class="i">$Path</span> =~ <span class="q">/-$VertexID2-/</span> || <span class="i">$Path</span> =~ <span class="q">/^$VertexID2-/</span> || <span class="i">$Path</span> =~ <span class="q">/-$VertexID2$/</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 689 676 <span class="k">return</span> <span class="n">1</span><span class="sc">;</span> | |
| 690 677 <span class="s">}</span> | |
| 691 678 <span class="s">}</span> | |
| 692 679 <span class="k">return</span> <span class="n">0</span><span class="sc">;</span> | |
| 693 680 <span class="s">}</span> | |
| 694 681 | |
| 695 682 <span class="c"># Search paths starting from a specified vertex with no sharing of edges in paths traversed.</span> | |
| 696 683 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 697 684 <span class="c"># completing the cycle.</span> | |
| 698 685 <span class="c">#</span> | |
| 699 <a name="PerformPathsSearch-"></a> 686 <span class="k">sub </span><span class="m">PerformPathsSearch</span> <span class="s">{</span> | |
| 700 687 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 701 688 | |
| 702 689 <span class="c"># Make sure start vertex is defined...</span> | |
| 703 690 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 704 691 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 705 692 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 706 693 <span class="s">}</span> | |
| 707 694 | |
| 708 695 <span class="c"># Make sure start vertex is valid...</span> | |
| 709 696 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 710 697 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 711 698 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 712 699 <span class="s">}</span> | |
| 713 700 | |
| 714 701 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$AllowCycles</span><span class="s">)</span> <span class="s">{</span> | |
| 715 702 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> | |
| 716 703 <span class="s">}</span> | |
| 717 704 | |
| 718 705 <span class="c"># Perform paths search...</span> | |
| 719 706 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformPathsSearch</span><span class="s">(</span><span class="q">"AllLengths"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 720 707 <span class="s">}</span> | |
| 721 708 | |
| 722 709 <span class="c"># Search paths starting from a specified vertex with length upto a specified length</span> | |
| 723 710 <span class="c"># with no sharing of edges in paths traversed...</span> | |
| 724 711 <span class="c">#</span> | |
| 725 712 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 726 713 <span class="c"># completing the cycle.</span> | |
| 727 714 <span class="c">#</span> | |
| 728 <a name="PerformPathsSearchWithLengthUpto-"></a> 715 <span class="k">sub </span><span class="m">PerformPathsSearchWithLengthUpto</span> <span class="s">{</span> | |
| 729 716 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 730 717 | |
| 731 718 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformPathsSearchWithLength</span><span class="s">(</span><span class="q">"LengthUpto"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 732 719 <span class="s">}</span> | |
| 733 720 | |
| 734 721 <span class="c"># Search paths starting from a specified vertex with specified length</span> | |
| 735 722 <span class="c"># with no sharing of edges in paths traversed...</span> | |
| 736 723 <span class="c">#</span> | |
| 737 724 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 738 725 <span class="c"># completing the cycle.</span> | |
| 739 726 <span class="c">#</span> | |
| 740 <a name="PerformPathsSearchWithLength-"></a> 727 <span class="k">sub </span><span class="m">PerformPathsSearchWithLength</span> <span class="s">{</span> | |
| 741 728 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 742 729 | |
| 743 730 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformPathsSearchWithLength</span><span class="s">(</span><span class="q">"Length"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 744 731 <span class="s">}</span> | |
| 745 732 | |
| 746 733 | |
| 747 734 <span class="c"># Search paths starting from a specified vertex with length upto a specified length</span> | |
| 748 735 <span class="c"># with no sharing of edges in paths traversed...</span> | |
| 749 736 <span class="c">#</span> | |
| 750 737 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 751 738 <span class="c"># completing the cycle.</span> | |
| 752 739 <span class="c">#</span> | |
| 753 <a name="_PerformPathsSearchWithLength-"></a> 740 <span class="k">sub </span><span class="m">_PerformPathsSearchWithLength</span> <span class="s">{</span> | |
| 754 741 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Mode</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 755 742 | |
| 756 743 <span class="c"># Make sure both start vertex and length are defined...</span> | |
| 757 744 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 758 745 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 759 746 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 760 747 <span class="s">}</span> | |
| 761 748 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$Length</span><span class="s">)</span> <span class="s">{</span> | |
| 762 749 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Length must be specified..."</span><span class="sc">;</span> | |
| 763 750 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 764 751 <span class="s">}</span> | |
| 765 752 | |
| 766 753 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$AllowCycles</span><span class="s">)</span> <span class="s">{</span> | |
| 767 754 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> | |
| 768 755 <span class="s">}</span> | |
| 769 756 | |
| 770 757 <span class="c"># Make sure both start vertex and length are valid...</span> | |
| 771 758 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 772 759 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 773 760 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 774 761 <span class="s">}</span> | |
| 775 762 | |
| 776 763 <span class="k">if</span> <span class="s">(</span><span class="i">$Length</span> < <span class="n">1</span><span class="s">)</span> <span class="s">{</span> | |
| 777 764 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1..."</span><span class="sc">;</span> | |
| 778 765 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 779 766 <span class="s">}</span> | |
| 780 767 | |
| 781 768 <span class="c"># Perform paths search...</span> | |
| 782 769 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformPathsSearch</span><span class="s">(</span><span class="i">$Mode</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="cm">,</span> <span class="i">$Length</span><span class="s">)</span><span class="sc">;</span> | |
| 783 770 <span class="s">}</span> | |
| 784 771 | |
| 785 772 <span class="c"># Search all paths starting from a specified vertex with sharing of edges in paths traversed...</span> | |
| 786 773 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 787 774 <span class="c"># completing the cycle.</span> | |
| 788 775 <span class="c">#</span> | |
| 789 <a name="PerformAllPathsSearch-"></a> 776 <span class="k">sub </span><span class="m">PerformAllPathsSearch</span> <span class="s">{</span> | |
| 790 777 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 791 778 | |
| 792 779 <span class="c"># Make sure start vertex is defined...</span> | |
| 793 780 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 794 781 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 795 782 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 796 783 <span class="s">}</span> | |
| 797 784 | |
| 798 785 <span class="c"># Make sure start vertex is valid...</span> | |
| 799 786 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 800 787 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 801 788 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 802 789 <span class="s">}</span> | |
| 803 790 | |
| 804 791 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$AllowCycles</span><span class="s">)</span> <span class="s">{</span> | |
| 805 792 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> | |
| 806 793 <span class="s">}</span> | |
| 807 794 | |
| 808 795 <span class="c"># Perform paths search...</span> | |
| 809 796 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformAllPathsSearch</span><span class="s">(</span><span class="q">"AllLengths"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 810 797 <span class="s">}</span> | |
| 811 798 | |
| 812 799 <span class="c"># Search all paths starting from a specified vertex with length upto a specified length with sharing of</span> | |
| 813 800 <span class="c"># edges in paths traversed.</span> | |
| 814 801 <span class="c">#</span> | |
| 815 802 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 816 803 <span class="c"># completing the cycle.</span> | |
| 817 804 <span class="c">#</span> | |
| 818 <a name="PerformAllPathsSearchWithLengthUpto-"></a> 805 <span class="k">sub </span><span class="m">PerformAllPathsSearchWithLengthUpto</span> <span class="s">{</span> | |
| 819 806 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 820 807 | |
| 821 808 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformAllPathsSearchWithLength</span><span class="s">(</span><span class="q">"LengthUpto"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 822 809 <span class="s">}</span> | |
| 823 810 | |
| 824 811 <span class="c"># Search all paths starting from a specified vertex with specified length with sharing of</span> | |
| 825 812 <span class="c"># edges in paths traversed.</span> | |
| 826 813 <span class="c">#</span> | |
| 827 814 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 828 815 <span class="c"># completing the cycle.</span> | |
| 829 816 <span class="c">#</span> | |
| 830 <a name="PerformAllPathsSearchWithLength-"></a> 817 <span class="k">sub </span><span class="m">PerformAllPathsSearchWithLength</span> <span class="s">{</span> | |
| 831 818 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 832 819 | |
| 833 820 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformAllPathsSearchWithLength</span><span class="s">(</span><span class="q">"Length"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 834 821 <span class="s">}</span> | |
| 835 822 | |
| 836 823 <span class="c"># Search all paths starting from a specified vertex with length upto a specified length with sharing of</span> | |
| 837 824 <span class="c"># edges in paths traversed.</span> | |
| 838 825 <span class="c">#</span> | |
| 839 826 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> | |
| 840 827 <span class="c"># completing the cycle.</span> | |
| 841 828 <span class="c">#</span> | |
| 842 <a name="_PerformAllPathsSearchWithLength-"></a> 829 <span class="k">sub </span><span class="m">_PerformAllPathsSearchWithLength</span> <span class="s">{</span> | |
| 843 830 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Mode</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Length</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 844 831 | |
| 845 832 <span class="c"># Make sure both start vertex and length are defined...</span> | |
| 846 833 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 847 834 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 848 835 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 849 836 <span class="s">}</span> | |
| 850 837 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$Length</span><span class="s">)</span> <span class="s">{</span> | |
| 851 838 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Length must be specified..."</span><span class="sc">;</span> | |
| 852 839 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 853 840 <span class="s">}</span> | |
| 854 841 | |
| 855 842 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$AllowCycles</span><span class="s">)</span> <span class="s">{</span> | |
| 856 843 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> | |
| 857 844 <span class="s">}</span> | |
| 858 845 | |
| 859 846 <span class="c"># Make sure both start vertex and length are valid...</span> | |
| 860 847 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 861 848 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 862 849 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 863 850 <span class="s">}</span> | |
| 864 851 | |
| 865 852 <span class="k">if</span> <span class="s">(</span><span class="i">$Length</span> < <span class="n">1</span><span class="s">)</span> <span class="s">{</span> | |
| 866 853 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1..."</span><span class="sc">;</span> | |
| 867 854 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 868 855 <span class="s">}</span> | |
| 869 856 | |
| 870 857 <span class="c"># Perform paths search...</span> | |
| 871 858 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformAllPathsSearch</span><span class="s">(</span><span class="i">$Mode</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="cm">,</span> <span class="i">$Length</span><span class="s">)</span><span class="sc">;</span> | |
| 872 859 <span class="s">}</span> | |
| 873 860 | |
| 874 861 <span class="c"># Search paths between two vertices...</span> | |
| 875 862 <span class="c">#</span> | |
| 876 <a name="PerformPathsSearchBetween-"></a> 863 <span class="k">sub </span><span class="m">PerformPathsSearchBetween</span> <span class="s">{</span> | |
| 877 864 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$EndVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 878 865 | |
| 879 866 <span class="c"># Make sure start and end vertices are defined...</span> | |
| 880 867 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 881 868 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 882 869 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 883 870 <span class="s">}</span> | |
| 884 871 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$EndVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 885 872 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: EndVertex vertex must be specified..."</span><span class="sc">;</span> | |
| 886 873 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 887 874 <span class="s">}</span> | |
| 888 875 <span class="c"># Make sure start and end vertices are valid...</span> | |
| 889 876 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 890 877 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 891 878 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 892 879 <span class="s">}</span> | |
| 893 880 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$EndVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 894 881 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $EndVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 895 882 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 896 883 <span class="s">}</span> | |
| 897 884 | |
| 898 885 <span class="c"># Perform paths search...</span> | |
| 899 886 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformPathsSearchBetween</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$EndVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 900 887 <span class="s">}</span> | |
| 901 888 | |
| 902 889 <span class="c"># Search paths starting from root vertex with no sharing of edges...</span> | |
| 903 890 <span class="c">#</span> | |
| 904 891 <span class="c"># Notes:</span> | |
| 905 892 <span class="c"># . Possible paths searche modes are: DFSPathsWithLimit, DFSPaths. And each</span> | |
| 906 893 <span class="c"># of these modes supports any combination of two options: CommonEdges, Cycles.</span> | |
| 907 894 <span class="c"># Default for CommonEdges - No; Cycles - No.</span> | |
| 908 895 <span class="c">#</span> | |
| 909 <a name="_PerformPathsSearch-"></a> 896 <span class="k">sub </span><span class="m">_PerformPathsSearch</span> <span class="s">{</span> | |
| 910 897 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Mode</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="cm">,</span> <span class="i">$Length</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 911 898 | |
| 912 899 <span class="c"># Perform DFS path search...</span> | |
| 913 900 | |
| 914 901 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'Path'</span><span class="sc">;</span> | |
| 915 902 | |
| 916 903 <span class="k">if</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^(LengthUpto|Length)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 917 904 <span class="k">my</span><span class="s">(</span><span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> | |
| 918 905 | |
| 919 906 <span class="i">$DepthLimit</span> = <span class="i">$Length</span> - <span class="n">1</span><span class="sc">;</span> | |
| 920 907 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFSWithLimit'</span><span class="sc">;</span> | |
| 921 908 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> | |
| 922 909 <span class="s">}</span> | |
| 923 910 <span class="k">else</span> <span class="s">{</span> | |
| 924 911 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFS'</span><span class="sc">;</span> | |
| 925 912 <span class="s">}</span> | |
| 926 913 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 927 914 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> | |
| 928 915 <span class="s">}</span> | |
| 929 916 | |
| 930 917 <span class="i">$This</span>->{<span class="w">AllowPathCycles</span>} = <span class="i">$AllowCycles</span><span class="sc">;</span> | |
| 931 918 | |
| 932 919 <span class="c"># Perform search...</span> | |
| 933 920 <span class="i">$This</span><span class="i">->_TraverseGraph</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 934 921 | |
| 935 922 <span class="c"># Make sure traversal did get the root vertex...</span> | |
| 936 923 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$RootVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 937 924 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 938 925 <span class="s">}</span> | |
| 939 926 <span class="k">if</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^Length$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 940 927 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="cm">,</span> <span class="i">$This</span><span class="i">->_CollectPathsTraversedDuringPathsSearchWithLength</span><span class="s">(</span><span class="i">$Length</span><span class="s">)</span><span class="sc">;</span> | |
| 941 928 <span class="s">}</span> | |
| 942 929 <span class="k">else</span> <span class="s">{</span> | |
| 943 930 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="cm">,</span> <span class="i">$This</span><span class="i">->_CollectPathsTraversedDuringPathsSearch</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 944 931 <span class="s">}</span> | |
| 945 932 | |
| 946 933 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 947 934 <span class="s">}</span> | |
| 948 935 | |
| 949 936 <span class="c"># Search all paths starting from root vertex with sharing of edges...</span> | |
| 950 937 <span class="c">#</span> | |
| 951 <a name="_PerformAllPathsSearch-"></a> 938 <span class="k">sub </span><span class="m">_PerformAllPathsSearch</span> <span class="s">{</span> | |
| 952 939 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Mode</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="cm">,</span> <span class="i">$Length</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 953 940 | |
| 954 941 <span class="c"># Perform DFS path search...</span> | |
| 955 942 | |
| 956 943 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'AllPaths'</span><span class="sc">;</span> | |
| 957 944 | |
| 958 945 <span class="k">if</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^(LengthUpto|Length)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 959 946 <span class="k">my</span><span class="s">(</span><span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> | |
| 960 947 | |
| 961 948 <span class="i">$DepthLimit</span> = <span class="i">$Length</span> - <span class="n">1</span><span class="sc">;</span> | |
| 962 949 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFSWithLimit'</span><span class="sc">;</span> | |
| 963 950 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> | |
| 964 951 <span class="s">}</span> | |
| 965 952 <span class="k">else</span> <span class="s">{</span> | |
| 966 953 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFS'</span><span class="sc">;</span> | |
| 967 954 <span class="s">}</span> | |
| 968 955 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> | |
| 969 956 <span class="i">$This</span>->{<span class="w">AllowPathCycles</span>} = <span class="i">$AllowCycles</span><span class="sc">;</span> | |
| 970 957 | |
| 971 958 <span class="c"># Traverse all paths search using DFS search...</span> | |
| 972 959 <span class="i">$This</span><span class="i">->_TraverseAllPathsInGraph</span><span class="s">(</span><span class="i">$Mode</span><span class="cm">,</span> <span class="i">$Length</span><span class="s">)</span><span class="sc">;</span> | |
| 973 960 | |
| 974 961 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 975 962 <span class="s">}</span> | |
| 976 963 | |
| 977 964 <span class="c"># Travese all paths in graph starting from a specified root vertex...</span> | |
| 978 965 <span class="c">#</span> | |
| 979 <a name="_TraverseAllPathsInGraph-"></a> 966 <span class="k">sub </span><span class="m">_TraverseAllPathsInGraph</span> <span class="s">{</span> | |
| 980 967 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Mode</span><span class="cm">,</span> <span class="i">$Length</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 981 968 | |
| 982 969 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">TraversalMode</span>} !~ <span class="q">/^AllPaths$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 983 970 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 984 971 <span class="s">}</span> | |
| 985 972 <span class="k">my</span><span class="s">(</span><span class="i">$CurrentVertexID</span><span class="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="cm">,</span> <span class="i">$CurrentDepth</span><span class="cm">,</span> <span class="i">$CurrentPath</span><span class="s">)</span><span class="sc">;</span> | |
| 986 973 | |
| 987 974 <span class="i">$CurrentVertexID</span> = <span class="i">$This</span>->{<span class="w">RootVertex</span>}<span class="sc">;</span> | |
| 988 975 <span class="i">$PredecessorVertexID</span> = <span class="i">$CurrentVertexID</span><span class="sc">;</span> | |
| 989 976 <span class="i">$CurrentDepth</span> = <span class="n">0</span><span class="sc">;</span> | |
| 990 977 <span class="i">$CurrentPath</span> = <span class="q">"$CurrentVertexID"</span><span class="sc">;</span> | |
| 991 978 | |
| 992 979 <span class="i">$This</span><span class="i">->_TraverseAllPaths</span><span class="s">(</span><span class="i">$CurrentVertexID</span><span class="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="cm">,</span> <span class="i">$CurrentDepth</span><span class="cm">,</span> <span class="i">$CurrentPath</span><span class="s">)</span><span class="sc">;</span> | |
| 993 980 | |
| 994 981 <span class="k">if</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^Length$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 995 982 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="cm">,</span> <span class="i">$This</span><span class="i">->_CollectPathsTraversedDuringPathsSearchWithLength</span><span class="s">(</span><span class="i">$Length</span><span class="s">)</span><span class="sc">;</span> | |
| 996 983 <span class="s">}</span> | |
| 997 984 <span class="k">else</span> <span class="s">{</span> | |
| 998 985 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="cm">,</span> <span class="i">$This</span><span class="i">->_CollectPathsTraversedDuringPathsSearch</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 999 986 <span class="s">}</span> | |
| 1000 987 | |
| 1001 988 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 1002 989 <span class="s">}</span> | |
| 1003 990 | |
| 1004 991 <span class="c"># Traverse and collect all paths recuresively..</span> | |
| 1005 992 <span class="c">#</span> | |
| 1006 <a name="_TraverseAllPaths-"></a> 993 <span class="k">sub </span><span class="m">_TraverseAllPaths</span> <span class="s">{</span> | |
| 1007 994 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$CurrentVertexID</span><span class="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="cm">,</span> <span class="i">$CurrentDepth</span><span class="cm">,</span> <span class="i">$CurrentPath</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1008 995 | |
| 1009 996 <span class="c"># Save path traversed for current vertex..</span> | |
| 1010 997 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$CurrentVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1011 998 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$CurrentVertexID</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1012 999 <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$CurrentVertexID</span>} = <span class="n">0</span><span class="sc">;</span> | |
| 1013 1000 <span class="s">}</span> | |
| 1014 1001 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$CurrentVertexID</span>}}<span class="cm">,</span> <span class="i">$CurrentPath</span><span class="sc">;</span> | |
| 1015 1002 <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$CurrentVertexID</span>} = <span class="i">$CurrentDepth</span><span class="sc">;</span> | |
| 1016 1003 | |
| 1017 1004 <span class="i">$CurrentDepth</span>++<span class="sc">;</span> | |
| 1018 1005 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1019 1006 <span class="k">if</span> <span class="s">(</span><span class="i">$CurrentDepth</span> > <span class="i">$This</span>->{<span class="w">DepthLimit</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1020 1007 <span class="c"># Nothing more to do...</span> | |
| 1021 1008 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 1022 1009 <span class="s">}</span> | |
| 1023 1010 <span class="s">}</span> | |
| 1024 1011 <span class="k">my</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$NewPath</span><span class="s">)</span><span class="sc">;</span> | |
| 1025 1012 | |
| 1026 1013 <span class="j">NEIGHBOR:</span> <span class="k">for</span> <span class="i">$NeighborVertexID</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->GetNeighbors</span><span class="s">(</span><span class="i">$CurrentVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1027 1014 <span class="k">if</span> <span class="s">(</span><span class="i">$NeighborVertexID</span> == <span class="i">$PredecessorVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 1028 1015 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 1029 1016 <span class="s">}</span> | |
| 1030 1017 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span><span class="i">->_IsVertexInTraversedPath</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$CurrentPath</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1031 1018 <span class="c"># It's a cycle...</span> | |
| 1032 1019 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">AllowPathCycles</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1033 1020 <span class="i">$NewPath</span> = <span class="q">"${CurrentPath}-${NeighborVertexID}"</span><span class="sc">;</span> | |
| 1034 1021 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$NeighborVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1035 1022 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$NeighborVertexID</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1036 1023 <span class="s">}</span> | |
| 1037 1024 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$NeighborVertexID</span>}}<span class="cm">,</span> <span class="i">$NewPath</span><span class="sc">;</span> | |
| 1038 1025 <span class="s">}</span> | |
| 1039 1026 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> | |
| 1040 1027 <span class="s">}</span> | |
| 1041 1028 <span class="i">$NewPath</span> = <span class="q">"${CurrentPath}-${NeighborVertexID}"</span><span class="sc">;</span> | |
| 1042 1029 <span class="i">$This</span><span class="i">->_TraverseAllPaths</span><span class="s">(</span><span class="i">$NeighborVertexID</span><span class="cm">,</span> <span class="i">$CurrentVertexID</span><span class="cm">,</span> <span class="i">$CurrentDepth</span><span class="cm">,</span> <span class="i">$NewPath</span><span class="s">)</span><span class="sc">;</span> | |
| 1043 1030 <span class="s">}</span> | |
| 1044 1031 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 1045 1032 <span class="s">}</span> | |
| 1046 1033 | |
| 1047 1034 <span class="c"># Is vertex already in traversed path?</span> | |
| 1048 1035 <span class="c">#</span> | |
| 1049 <a name="_IsVertexInTraversedPath-"></a>1036 <span class="k">sub </span><span class="m">_IsVertexInTraversedPath</span> <span class="s">{</span> | |
| 1050 1037 <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="cm">,</span> <span class="i">$Path</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1051 1038 | |
| 1052 1039 <span class="k">return</span> <span class="s">(</span><span class="i">$Path</span> =~ <span class="q">/-$VertexID-/</span> || <span class="i">$Path</span> =~ <span class="q">/^$VertexID-/</span> || <span class="i">$Path</span> =~ <span class="q">/-$VertexID$/</span><span class="s">)</span> ? <span class="n">1</span> <span class="co">:</span> <span class="n">0</span><span class="sc">;</span> | |
| 1053 1040 <span class="s">}</span> | |
| 1054 1041 | |
| 1055 1042 <span class="c"># Collect all paths traversed during Path TraversalMode and sort 'em in</span> | |
| 1056 1043 <span class="c"># ascending order of lengths</span> | |
| 1057 1044 <span class="c">#</span> | |
| 1058 <a name="_CollectPathsTraversedDuringPathsSearch-"></a>1045 <span class="k">sub </span><span class="m">_CollectPathsTraversedDuringPathsSearch</span> <span class="s">{</span> | |
| 1059 1046 <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> | |
| 1060 1047 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@SortedPaths</span><span class="s">)</span><span class="sc">;</span> | |
| 1061 1048 | |
| 1062 1049 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@SortedPaths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1063 1050 | |
| 1064 1051 <span class="c"># Create path objects from path vertex strings...</span> | |
| 1065 1052 <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="k">keys</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1066 1053 <span class="k">push</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="k">map</span> <span class="s">{</span> <span class="i">new</span> <span class="i">Graph::Path</span><span class="s">(</span><span class="k">split</span> <span class="q">/-/</span><span class="cm">,</span> <span class="i">$_</span><span class="s">)</span> <span class="s">}</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID</span>}}<span class="sc">;</span> | |
| 1067 1054 <span class="s">}</span> | |
| 1068 1055 | |
| 1069 1056 <span class="c"># Sort paths in ascending order of lengths...</span> | |
| 1070 1057 <span class="k">push</span> <span class="i">@SortedPaths</span><span class="cm">,</span> <span class="k">sort</span> <span class="s">{</span> <span class="i">$a</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span> <=> <span class="i">$b</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span> <span class="s">}</span> <span class="i">@Paths</span><span class="sc">;</span> | |
| 1071 1058 | |
| 1072 1059 <span class="k">return</span> <span class="i">@SortedPaths</span><span class="sc">;</span> | |
| 1073 1060 <span class="s">}</span> | |
| 1074 1061 | |
| 1075 1062 <span class="c"># Collect paths traversed during Path TraversalMode with specific length...</span> | |
| 1076 1063 <span class="c">#</span> | |
| 1077 <a name="_CollectPathsTraversedDuringPathsSearchWithLength-"></a>1064 <span class="k">sub </span><span class="m">_CollectPathsTraversedDuringPathsSearchWithLength</span> <span class="s">{</span> | |
| 1078 1065 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Length</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1079 1066 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$Depth</span><span class="cm">,</span> <span class="i">$PathString</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">@Paths</span><span class="s">)</span><span class="sc">;</span> | |
| 1080 1067 | |
| 1081 1068 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1082 1069 <span class="i">$Depth</span> = <span class="i">$Length</span> - <span class="n">1</span><span class="sc">;</span> | |
| 1083 1070 | |
| 1084 1071 <span class="c"># Create path objects from path vertex strings...</span> | |
| 1085 1072 <span class="j">VERTEXID:</span> <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="k">keys</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1086 1073 <span class="k">if</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>} != <span class="i">$Depth</span><span class="s">)</span> <span class="s">{</span> | |
| 1087 1074 <span class="k">next</span> <span class="j">VERTEXID</span><span class="sc">;</span> | |
| 1088 1075 <span class="s">}</span> | |
| 1089 1076 <span class="c"># For vertices involved in cycles, the path might also contain some shorter paths. So check</span> | |
| 1090 1077 <span class="c"># the lengths before its collection...</span> | |
| 1091 1078 <span class="j">PATHSTRING:</span> <span class="k">for</span> <span class="i">$PathString</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesPaths</span>}{<span class="i">$VertexID</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1092 1079 <span class="i">@VertexIDs</span> = <span class="k">split</span> <span class="q">/-/</span><span class="cm">,</span> <span class="i">$PathString</span><span class="sc">;</span> | |
| 1093 1080 <span class="k">if</span> <span class="s">(</span><span class="i">$Length</span> != <span class="i">@VertexIDs</span><span class="s">)</span> <span class="s">{</span> | |
| 1094 1081 <span class="k">next</span> <span class="j">PATHSTRING</span><span class="sc">;</span> | |
| 1095 1082 <span class="s">}</span> | |
| 1096 1083 <span class="k">push</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">new</span> <span class="i">Graph::Path</span><span class="s">(</span><span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> | |
| 1097 1084 <span class="s">}</span> | |
| 1098 1085 <span class="s">}</span> | |
| 1099 1086 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> | |
| 1100 1087 <span class="s">}</span> | |
| 1101 1088 | |
| 1102 1089 <span class="c"># Collect paths traversed during Vertex TraversalMode...</span> | |
| 1103 1090 <span class="c">#</span> | |
| 1104 <a name="_CollectPathsTraversedDuringVertexSearch-"></a>1091 <span class="k">sub </span><span class="m">_CollectPathsTraversedDuringVertexSearch</span> <span class="s">{</span> | |
| 1105 1092 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1106 1093 <span class="k">my</span><span class="s">(</span><span class="i">$Depth</span><span class="cm">,</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="i">@VerticesAtDepth</span><span class="s">)</span><span class="sc">;</span> | |
| 1107 1094 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1108 1095 | |
| 1109 1096 <span class="c"># Get vertices at specific depths...</span> | |
| 1110 1097 <span class="i">@VerticesAtDepth</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1111 1098 <span class="i">@VerticesAtDepth</span> = <span class="i">$This</span><span class="i">->_CollectVerticesAtSpecificDepths</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1112 1099 <span class="k">if</span> <span class="s">(</span>!<span class="i">@VerticesAtDepth</span><span class="s">)</span> <span class="s">{</span> | |
| 1113 1100 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> | |
| 1114 1101 <span class="s">}</span> | |
| 1115 1102 | |
| 1116 1103 <span class="c"># Make sure search found only one root vertex and it corresponds to</span> | |
| 1117 1104 <span class="c"># what was specified...</span> | |
| 1118 1105 <span class="i">$Depth</span> = <span class="n">0</span><span class="sc">;</span> | |
| 1119 1106 <span class="k">if</span> <span class="s">(</span><span class="s">(</span><span class="i">@</span>{<span class="i">$VerticesAtDepth</span>[<span class="i">$Depth</span>]} > <span class="n">1</span><span class="s">)</span> || <span class="s">(</span><span class="i">$VerticesAtDepth</span>[<span class="i">$Depth</span>][<span class="n">0</span>] != <span class="i">$RootVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1120 1107 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->_PerformPathsSearch: No paths found: Root vertex, $VerticesAtDepth[$Depth][0], identified by paths traversal doen't match specified root vertex $RootVertexID..."</span><span class="sc">;</span> | |
| 1121 1108 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> | |
| 1122 1109 <span class="s">}</span> | |
| 1123 1110 | |
| 1124 1111 <span class="c"># Setup root vertex at depth 0. And set its path...</span> | |
| 1125 1112 <span class="k">my</span><span class="s">(</span><span class="i">$Path</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$SuccessorVertexID</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">%PathAtVertex</span><span class="s">)</span><span class="sc">;</span> | |
| 1126 1113 <span class="i">%PathAtVertex</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1127 1114 <span class="i">$PathAtVertex</span>{<span class="i">$RootVertexID</span>} = <span class="i">new</span> <span class="i">Graph::Path</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 1128 1115 | |
| 1129 1116 <span class="k">for</span> <span class="i">$Depth</span> <span class="s">(</span><span class="n">0</span> .. <span class="i">$#VerticesAtDepth</span><span class="s">)</span> <span class="s">{</span> | |
| 1130 1117 <span class="c"># Go over all vertices at current depth...</span> | |
| 1131 1118 <span class="j">VERTEX:</span> <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$VerticesAtDepth</span>[<span class="i">$Depth</span>]}<span class="s">)</span> <span class="s">{</span> | |
| 1132 1119 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1133 1120 <span class="k">next</span> <span class="j">VERTEX</span><span class="sc">;</span> | |
| 1134 1121 <span class="s">}</span> | |
| 1135 1122 <span class="c"># Get vertices for current path...</span> | |
| 1136 1123 <span class="i">@VertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1137 1124 <span class="k">push</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">$PathAtVertex</span>{<span class="i">$VertexID</span>}<span class="i">->GetVertices</span><span class="sc">;</span> | |
| 1138 1125 | |
| 1139 1126 <span class="c"># Expand path to successor vertex found during traversal...</span> | |
| 1140 1127 <span class="k">for</span> <span class="i">$SuccessorVertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1141 1128 <span class="i">$Path</span> = <span class="i">new</span> <span class="i">Graph::Path</span><span class="s">(</span><span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> | |
| 1142 1129 <span class="i">$Path</span><span class="i">->AddVertex</span><span class="s">(</span><span class="i">$SuccessorVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 1143 1130 <span class="i">$PathAtVertex</span>{<span class="i">$SuccessorVertexID</span>} = <span class="i">$Path</span><span class="sc">;</span> | |
| 1144 1131 <span class="s">}</span> | |
| 1145 1132 <span class="s">}</span> | |
| 1146 1133 <span class="s">}</span> | |
| 1147 1134 <span class="c"># Sort paths in ascending order of lengths...</span> | |
| 1148 1135 <span class="k">push</span> <span class="i">@Paths</span><span class="cm">,</span> <span class="k">sort</span> <span class="s">{</span> <span class="i">$a</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span> <=> <span class="i">$b</span><span class="i">->GetLength</span><span class="s">(</span><span class="s">)</span> <span class="s">}</span> <span class="k">values</span> <span class="i">%PathAtVertex</span><span class="sc">;</span> | |
| 1149 1136 | |
| 1150 1137 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> | |
| 1151 1138 <span class="s">}</span> | |
| 1152 1139 | |
| 1153 1140 <span class="c"># Collect vertices at specific depths. Depth values start from 0...</span> | |
| 1154 1141 <span class="c">#</span> | |
| 1155 <a name="_CollectVerticesAtSpecificDepths-"></a>1142 <span class="k">sub </span><span class="m">_CollectVerticesAtSpecificDepths</span> <span class="s">{</span> | |
| 1156 1143 <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> | |
| 1157 1144 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$Depth</span><span class="cm">,</span> <span class="i">@VerticesAtDepth</span><span class="s">)</span><span class="sc">;</span> | |
| 1158 1145 | |
| 1159 1146 <span class="i">@VerticesAtDepth</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1160 1147 <span class="k">while</span> <span class="s">(</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$Depth</span><span class="s">)</span> = <span class="k">each</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesDepth</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1161 1148 <span class="k">push</span> <span class="i">@</span>{<span class="i">$VerticesAtDepth</span>[<span class="i">$Depth</span>]}<span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 1162 1149 <span class="s">}</span> | |
| 1163 1150 <span class="k">return</span> <span class="i">@VerticesAtDepth</span><span class="sc">;</span> | |
| 1164 1151 <span class="s">}</span> | |
| 1165 1152 | |
| 1166 1153 <span class="c"># Collect vertices, along with their successors, at specific depths and return a list containing references to</span> | |
| 1167 1154 <span class="c"># lists with first value corresponding to vertex ID and second value a reference to a list containing</span> | |
| 1168 1155 <span class="c"># its successors.</span> | |
| 1169 1156 <span class="c">#</span> | |
| 1170 1157 <span class="c"># Depth values start from 0...</span> | |
| 1171 1158 <span class="c">#</span> | |
| 1172 <a name="_CollectVerticesWithSuccessorsAtSpecificDepths-"></a>1159 <span class="k">sub </span><span class="m">_CollectVerticesWithSuccessorsAtSpecificDepths</span> <span class="s">{</span> | |
| 1173 1160 <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> | |
| 1174 1161 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$Depth</span><span class="cm">,</span> <span class="i">@VerticesWithSuccessorsAtDepth</span><span class="s">)</span><span class="sc">;</span> | |
| 1175 1162 | |
| 1176 1163 <span class="i">@VerticesWithSuccessorsAtDepth</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1177 1164 <span class="k">while</span> <span class="s">(</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$Depth</span><span class="s">)</span> = <span class="k">each</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesDepth</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1178 1165 <span class="k">my</span><span class="s">(</span><span class="i">@VertexWithSuccessors</span><span class="cm">,</span> <span class="i">@VertexSuccessors</span><span class="s">)</span><span class="sc">;</span> | |
| 1179 1166 | |
| 1180 1167 <span class="i">@VertexWithSuccessors</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> <span class="i">@VertexSuccessors</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1181 1168 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1182 1169 <span class="k">push</span> <span class="i">@VertexSuccessors</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}}<span class="sc">;</span> | |
| 1183 1170 <span class="s">}</span> | |
| 1184 1171 <span class="k">push</span> <span class="i">@VertexWithSuccessors</span><span class="cm">,</span> <span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> \<span class="i">@VertexSuccessors</span><span class="s">)</span><span class="sc">;</span> | |
| 1185 1172 <span class="c"># Multiple entries for a vertex and its successors could be present at a specific depth...</span> | |
| 1186 1173 <span class="k">push</span> <span class="i">@</span>{<span class="i">$VerticesWithSuccessorsAtDepth</span>[<span class="i">$Depth</span>]}<span class="cm">,</span> \<span class="i">@VertexWithSuccessors</span><span class="sc">;</span> | |
| 1187 1174 <span class="s">}</span> | |
| 1188 1175 <span class="k">return</span> <span class="i">@VerticesWithSuccessorsAtDepth</span><span class="sc">;</span> | |
| 1189 1176 <span class="s">}</span> | |
| 1190 1177 | |
| 1191 1178 <span class="c"># Search paths between two vertices...</span> | |
| 1192 1179 <span class="c">#</span> | |
| 1193 <a name="_PerformPathsSearchBetween-"></a>1180 <span class="k">sub </span><span class="m">_PerformPathsSearchBetween</span> <span class="s">{</span> | |
| 1194 1181 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$TargetVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1195 1182 <span class="k">my</span><span class="s">(</span><span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> | |
| 1196 1183 | |
| 1197 1184 <span class="c"># Perform a targeted DFS search...</span> | |
| 1198 1185 <span class="i">$DepthLimit</span> = <span class="k">undef</span><span class="sc">;</span> | |
| 1199 1186 <span class="i">$This</span><span class="i">->_PerformVertexSearch</span><span class="s">(</span><span class="q">"DFS"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$TargetVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 1200 1187 | |
| 1201 1188 <span class="k">my</span><span class="s">(</span><span class="i">$Path</span><span class="s">)</span><span class="sc">;</span> | |
| 1202 1189 <span class="i">$Path</span> = <span class="i">$This</span><span class="i">->_CollectPathBetween</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$TargetVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 1203 1190 | |
| 1204 1191 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$Path</span><span class="s">)</span> <span class="s">{</span> | |
| 1205 1192 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="cm">,</span> <span class="i">$Path</span><span class="sc">;</span> | |
| 1206 1193 <span class="s">}</span> | |
| 1207 1194 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 1208 1195 <span class="s">}</span> | |
| 1209 1196 | |
| 1210 1197 <span class="c"># Collect path between root and target vertex after the search...</span> | |
| 1211 1198 <span class="c">#</span> | |
| 1212 <a name="_CollectPathBetween-"></a>1199 <span class="k">sub </span><span class="m">_CollectPathBetween</span> <span class="s">{</span> | |
| 1213 1200 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$TargetVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1214 1201 | |
| 1215 1202 <span class="c"># Does a path from root to target vertex exist?</span> | |
| 1216 1203 <span class="k">if</span> <span class="s">(</span>!<span class="s">(</span><span class="k">exists</span><span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesRoots</span>}{<span class="i">$TargetVertexID</span>}<span class="s">)</span> && <span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesRoots</span>}{<span class="i">$TargetVertexID</span>} == <span class="i">$RootVertexID</span><span class="s">)</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1217 1204 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1218 1205 <span class="s">}</span> | |
| 1219 1206 | |
| 1220 1207 <span class="c"># Add target vertex ID path vertices...</span> | |
| 1221 1208 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$Path</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> | |
| 1222 1209 <span class="i">@VertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1223 1210 <span class="i">$VertexID</span> = <span class="i">$TargetVertexID</span><span class="sc">;</span> | |
| 1224 1211 <span class="k">push</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 1225 1212 | |
| 1226 1213 <span class="c"># Backtrack to root vertex ID...</span> | |
| 1227 1214 <span class="k">while</span> <span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}{<span class="i">$VertexID</span>} != <span class="i">$VertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 1228 1215 <span class="i">$VertexID</span> = <span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}{<span class="i">$VertexID</span>}<span class="sc">;</span> | |
| 1229 1216 <span class="k">push</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 1230 1217 <span class="s">}</span> | |
| 1231 1218 | |
| 1232 1219 <span class="c"># Create path from target to root and reverse it...</span> | |
| 1233 1220 <span class="i">$Path</span> = <span class="i">new</span> <span class="i">Graph::Path</span><span class="s">(</span><span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> | |
| 1234 1221 <span class="i">$Path</span><span class="i">->Reverse</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1235 1222 | |
| 1236 1223 <span class="k">return</span> <span class="i">$Path</span><span class="sc">;</span> | |
| 1237 1224 <span class="s">}</span> | |
| 1238 1225 | |
| 1239 1226 <span class="c"># Search vertices around specified root vertex with in specific neighborhood radius...</span> | |
| 1240 1227 <span class="c">#</span> | |
| 1241 <a name="PerformNeighborhoodVerticesSearchWithRadiusUpto-"></a>1228 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearchWithRadiusUpto</span> <span class="s">{</span> | |
| 1242 1229 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Radius</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1243 1230 | |
| 1244 1231 <span class="c"># Make sure both start vertex and radius are defined...</span> | |
| 1245 1232 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 1246 1233 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 1247 1234 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1248 1235 <span class="s">}</span> | |
| 1249 1236 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$Radius</span><span class="s">)</span> <span class="s">{</span> | |
| 1250 1237 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Radius must be specified..."</span><span class="sc">;</span> | |
| 1251 1238 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1252 1239 <span class="s">}</span> | |
| 1253 1240 | |
| 1254 1241 <span class="c"># Make sure both start vertex and length are valid...</span> | |
| 1255 1242 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1256 1243 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 1257 1244 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1258 1245 <span class="s">}</span> | |
| 1259 1246 <span class="k">if</span> <span class="s">(</span><span class="i">$Radius</span> < <span class="n">0</span><span class="s">)</span> <span class="s">{</span> | |
| 1260 1247 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Specified radius, $Radius, must be a positive integer..."</span><span class="sc">;</span> | |
| 1261 1248 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1262 1249 <span class="s">}</span> | |
| 1263 1250 | |
| 1264 1251 <span class="c"># Perform vertices search...</span> | |
| 1265 1252 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformNeighborhoodVerticesSearch</span><span class="s">(</span><span class="q">"RadiusUpto"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Radius</span><span class="s">)</span><span class="sc">;</span> | |
| 1266 1253 <span class="s">}</span> | |
| 1267 1254 | |
| 1268 1255 <span class="c"># Search vertices around specified root vertex...</span> | |
| 1269 1256 <span class="c">#</span> | |
| 1270 <a name="PerformNeighborhoodVerticesSearch-"></a>1257 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearch</span> <span class="s">{</span> | |
| 1271 1258 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1272 1259 | |
| 1273 1260 <span class="c"># Make sure start vertex is defined...</span> | |
| 1274 1261 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 1275 1262 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 1276 1263 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1277 1264 <span class="s">}</span> | |
| 1278 1265 | |
| 1279 1266 <span class="c"># Make sure start vertex is valid...</span> | |
| 1280 1267 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1281 1268 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 1282 1269 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1283 1270 <span class="s">}</span> | |
| 1284 1271 <span class="c"># Perform vertices search...</span> | |
| 1285 1272 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformNeighborhoodVerticesSearch</span><span class="s">(</span><span class="q">"AllRadii"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 1286 1273 <span class="s">}</span> | |
| 1287 1274 | |
| 1288 1275 <span class="c"># Search vertices around specified root vertex with in specific neighborhood radius along with</span> | |
| 1289 1276 <span class="c"># identification of successors of each vertex found during the search...</span> | |
| 1290 1277 <span class="c">#</span> | |
| 1291 <a name="PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto-"></a>1278 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto</span> <span class="s">{</span> | |
| 1292 1279 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Radius</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1293 1280 | |
| 1294 1281 <span class="c"># Make sure both start vertex and radius are defined...</span> | |
| 1295 1282 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 1296 1283 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 1297 1284 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1298 1285 <span class="s">}</span> | |
| 1299 1286 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$Radius</span><span class="s">)</span> <span class="s">{</span> | |
| 1300 1287 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Radius must be specified..."</span><span class="sc">;</span> | |
| 1301 1288 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1302 1289 <span class="s">}</span> | |
| 1303 1290 | |
| 1304 1291 <span class="c"># Make sure both start vertex and length are valid...</span> | |
| 1305 1292 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1306 1293 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 1307 1294 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1308 1295 <span class="s">}</span> | |
| 1309 1296 <span class="k">if</span> <span class="s">(</span><span class="i">$Radius</span> < <span class="n">0</span><span class="s">)</span> <span class="s">{</span> | |
| 1310 1297 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Specified radius, $Radius, must be a positive integer..."</span><span class="sc">;</span> | |
| 1311 1298 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1312 1299 <span class="s">}</span> | |
| 1313 1300 | |
| 1314 1301 <span class="c"># Perform vertices search...</span> | |
| 1315 1302 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformNeighborhoodVerticesSearch</span><span class="s">(</span><span class="q">"WithSuccessorsAndRadiusUpto"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="cm">,</span> <span class="i">$Radius</span><span class="s">)</span><span class="sc">;</span> | |
| 1316 1303 <span class="s">}</span> | |
| 1317 1304 | |
| 1318 1305 <span class="c"># Search vertices around specified root vertex along with identification of</span> | |
| 1319 1306 <span class="c"># successors of each vertex found during the search...</span> | |
| 1320 1307 <span class="c">#</span> | |
| 1321 <a name="PerformNeighborhoodVerticesSearchWithSuccessors-"></a>1308 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearchWithSuccessors</span> <span class="s">{</span> | |
| 1322 1309 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1323 1310 | |
| 1324 1311 <span class="c"># Make sure start vertex is defined...</span> | |
| 1325 1312 <span class="k">if</span> <span class="s">(</span>!<span class="k">defined</span> <span class="i">$StartVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 1326 1313 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessors: No vertices search performed: Start vertex must be specified..."</span><span class="sc">;</span> | |
| 1327 1314 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1328 1315 <span class="s">}</span> | |
| 1329 1316 | |
| 1330 1317 <span class="c"># Make sure start vertex is valid...</span> | |
| 1331 1318 <span class="k">if</span> <span class="s">(</span>!<span class="i">$This</span>->{<span class="w">Graph</span>}<span class="i">->HasVertex</span><span class="s">(</span><span class="i">$StartVertexID</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> | |
| 1332 1319 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessors: No vertices search performed: Vertex $StartVertexID doesn't exist..."</span><span class="sc">;</span> | |
| 1333 1320 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1334 1321 <span class="s">}</span> | |
| 1335 1322 <span class="c"># Perform vertices search...</span> | |
| 1336 1323 <span class="k">return</span> <span class="i">$This</span><span class="i">->_PerformNeighborhoodVerticesSearch</span><span class="s">(</span><span class="q">"WithSuccessorsAndAllRadii"</span><span class="cm">,</span> <span class="i">$StartVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 1337 1324 <span class="s">}</span> | |
| 1338 1325 | |
| 1339 1326 <span class="c"># Search vertices at successive neighborhood radii levels...</span> | |
| 1340 1327 <span class="c">#</span> | |
| 1341 <a name="_PerformNeighborhoodVerticesSearch-"></a>1328 <span class="k">sub </span><span class="m">_PerformNeighborhoodVerticesSearch</span> <span class="s">{</span> | |
| 1342 1329 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Mode</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$Radius</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1343 1330 <span class="k">my</span><span class="s">(</span><span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 1344 1331 | |
| 1345 1332 <span class="i">$DepthLimit</span> = <span class="k">defined</span> <span class="i">$Radius</span> ? <span class="i">$Radius</span> <span class="co">:</span> <span class="k">undef</span><span class="sc">;</span> | |
| 1346 1333 <span class="i">$AllowCycles</span> = <span class="k">undef</span><span class="sc">;</span> | |
| 1347 1334 | |
| 1348 1335 <span class="c"># Perform BFS search...</span> | |
| 1349 1336 <span class="k">if</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^RadiusUpto$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 1350 1337 <span class="i">$This</span><span class="i">->_PerformVertexNeighborhoodSearch</span><span class="s">(</span><span class="q">"BFSWithLimit"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> | |
| 1351 1338 <span class="s">}</span> | |
| 1352 1339 <span class="k">elsif</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^(AllRadii)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 1353 1340 <span class="i">$This</span><span class="i">->_PerformVertexNeighborhoodSearch</span><span class="s">(</span><span class="q">"BFS"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> | |
| 1354 1341 <span class="s">}</span> | |
| 1355 1342 <span class="k">elsif</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^WithSuccessorsAndRadiusUpto$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 1356 1343 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> | |
| 1357 1344 <span class="i">$This</span><span class="i">->_PerformVertexNeighborhoodSearch</span><span class="s">(</span><span class="q">"BFSWithLimit"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 1358 1345 <span class="s">}</span> | |
| 1359 1346 <span class="k">elsif</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^WithSuccessorsAndAllRadii$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 1360 1347 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> | |
| 1361 1348 <span class="i">$This</span><span class="i">->_PerformVertexNeighborhoodSearch</span><span class="s">(</span><span class="q">"BFSWithLimit"</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span><span class="sc">;</span> | |
| 1362 1349 <span class="s">}</span> | |
| 1363 1350 | |
| 1364 1351 <span class="c"># Make sure traversal did get the root vertex...</span> | |
| 1365 1352 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$RootVertexID</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1366 1353 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 1367 1354 <span class="s">}</span> | |
| 1368 1355 | |
| 1369 1356 <span class="k">if</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^(RadiusUpto|AllRadii)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 1370 1357 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoods</span>}}<span class="cm">,</span> <span class="i">$This</span><span class="i">->_CollectVerticesAtSpecificDepths</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1371 1358 <span class="s">}</span> | |
| 1372 1359 <span class="k">elsif</span> <span class="s">(</span><span class="i">$Mode</span> =~ <span class="q">/^(WithSuccessorsAndRadiusUpto|WithSuccessorsAndAllRadii)$/i</span><span class="s">)</span> <span class="s">{</span> | |
| 1373 1360 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoodsWithSuccessors</span>}}<span class="cm">,</span> <span class="i">$This</span><span class="i">->_CollectVerticesWithSuccessorsAtSpecificDepths</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1374 1361 <span class="s">}</span> | |
| 1375 1362 | |
| 1376 1363 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> | |
| 1377 1364 <span class="s">}</span> | |
| 1378 1365 | |
| 1379 1366 <span class="c"># Perform appropriate vertex search...</span> | |
| 1380 1367 <span class="c">#</span> | |
| 1381 <a name="_PerformVertexNeighborhoodSearch-"></a>1368 <span class="k">sub </span><span class="m">_PerformVertexNeighborhoodSearch</span> <span class="s">{</span> | |
| 1382 1369 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$SearchType</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$DepthLimit</span><span class="cm">,</span> <span class="i">$AllowCycles</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> | |
| 1383 1370 | |
| 1384 1371 <span class="c"># Setup search...</span> | |
| 1385 1372 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'VertexNeighborhood'</span><span class="sc">;</span> | |
| 1386 1373 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="i">$SearchType</span><span class="sc">;</span> | |
| 1387 1374 | |
| 1388 1375 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$RootVertexID</span><span class="s">)</span> <span class="s">{</span> | |
| 1389 1376 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> | |
| 1390 1377 <span class="s">}</span> | |
| 1391 1378 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$DepthLimit</span><span class="s">)</span> <span class="s">{</span> | |
| 1392 1379 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> | |
| 1393 1380 <span class="s">}</span> | |
| 1394 1381 <span class="k">if</span> <span class="s">(</span><span class="k">defined</span> <span class="i">$AllowCycles</span><span class="s">)</span> <span class="s">{</span> | |
| 1395 1382 <span class="i">$This</span>->{<span class="w">AllowVertexCycles</span>} = <span class="i">$AllowCycles</span><span class="sc">;</span> | |
| 1396 1383 <span class="s">}</span> | |
| 1397 1384 | |
| 1398 1385 <span class="c"># Perform search...</span> | |
| 1399 1386 <span class="k">return</span> <span class="i">$This</span><span class="i">->_TraverseGraph</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1400 1387 <span class="s">}</span> | |
| 1401 1388 | |
| 1402 1389 <span class="c"># Get orderded list of vertices after DFS/BFS search...</span> | |
| 1403 1390 <span class="c">#</span> | |
| 1404 <a name="GetVertices-"></a>1391 <span class="k">sub </span><span class="m">GetVertices</span> <span class="s">{</span> | |
| 1405 1392 <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> | |
| 1406 1393 | |
| 1407 1394 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}} <span class="co">:</span> <span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="sc">;</span> | |
| 1408 1395 <span class="s">}</span> | |
| 1409 1396 | |
| 1410 1397 <span class="c"># Get a hash list containing vertex and root vertex as key/value pair for all vertices</span> | |
| 1411 1398 <span class="c"># ordered using DFS/BFS search available via GetVertices method...</span> | |
| 1412 1399 <span class="c">#</span> | |
| 1413 <a name="GetVerticesRoots-"></a>1400 <span class="k">sub </span><span class="m">GetVerticesRoots</span> <span class="s">{</span> | |
| 1414 1401 <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> | |
| 1415 1402 | |
| 1416 1403 <span class="k">return</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesRoots</span>}}<span class="sc">;</span> | |
| 1417 1404 <span class="s">}</span> | |
| 1418 1405 | |
| 1419 1406 <span class="c"># Get a list containing lists of vertices in connected components of graph after DFS/BFS</span> | |
| 1420 1407 <span class="c"># search...</span> | |
| 1421 1408 <span class="c">#</span> | |
| 1422 1409 <span class="c"># Note:</span> | |
| 1423 1410 <span class="c"># . List is sorted in descending order of number of vertices in each connected component.</span> | |
| 1424 1411 <span class="c">#</span> | |
| 1425 <a name="GetConnectedComponentsVertices-"></a>1412 <span class="k">sub </span><span class="m">GetConnectedComponentsVertices</span> <span class="s">{</span> | |
| 1426 1413 <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> | |
| 1427 1414 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$VertexRoot</span><span class="cm">,</span> <span class="i">@ConnectedVertices</span><span class="cm">,</span> <span class="i">%VerticesAtRoot</span><span class="s">)</span><span class="sc">;</span> | |
| 1428 1415 | |
| 1429 1416 <span class="i">@ConnectedVertices</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1430 1417 <span class="i">%VerticesAtRoot</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1431 1418 <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1432 1419 <span class="i">$VertexRoot</span> = <span class="i">$This</span>->{<span class="w">VerticesRoots</span>}{<span class="i">$VertexID</span>}<span class="sc">;</span> | |
| 1433 1420 <span class="k">if</span> <span class="s">(</span>!<span class="k">exists</span> <span class="i">$VerticesAtRoot</span>{<span class="i">$VertexRoot</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1434 1421 <span class="i">@</span>{<span class="i">$VerticesAtRoot</span>{<span class="i">$VertexRoot</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1435 1422 <span class="s">}</span> | |
| 1436 1423 <span class="k">push</span> <span class="i">@</span>{<span class="i">$VerticesAtRoot</span>{<span class="i">$VertexRoot</span>}}<span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> | |
| 1437 1424 <span class="s">}</span> | |
| 1438 1425 <span class="k">push</span> <span class="i">@ConnectedVertices</span><span class="cm">,</span> <span class="k">sort</span> <span class="s">{</span> <span class="i">@</span>{<span class="i">$b</span>} <=> <span class="i">@</span>{<span class="i">$a</span>} <span class="s">}</span> <span class="k">values</span> <span class="i">%VerticesAtRoot</span><span class="sc">;</span> | |
| 1439 1426 | |
| 1440 1427 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@ConnectedVertices</span> <span class="co">:</span> <span class="k">scalar</span> <span class="i">@ConnectedVertices</span><span class="sc">;</span> | |
| 1441 1428 <span class="s">}</span> | |
| 1442 1429 | |
| 1443 1430 <span class="c"># Get predecessor vertices...</span> | |
| 1444 1431 <span class="c">#</span> | |
| 1445 <a name="GetVerticesPredecessors-"></a>1432 <span class="k">sub </span><span class="m">GetVerticesPredecessors</span> <span class="s">{</span> | |
| 1446 1433 <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> | |
| 1447 1434 | |
| 1448 1435 <span class="k">return</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}}<span class="sc">;</span> | |
| 1449 1436 <span class="s">}</span> | |
| 1450 1437 | |
| 1451 1438 <span class="c"># Get a hash list containing vertex and depth from root vertex as key/value pair for all vertices</span> | |
| 1452 1439 <span class="c"># ordered using DFS/BFS search available via GetVertices method...</span> | |
| 1453 1440 <span class="c">#</span> | |
| 1454 <a name="GetVerticesDepth-"></a>1441 <span class="k">sub </span><span class="m">GetVerticesDepth</span> <span class="s">{</span> | |
| 1455 1442 <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> | |
| 1456 1443 | |
| 1457 1444 <span class="k">return</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesDepth</span>}}<span class="sc">;</span> | |
| 1458 1445 <span class="s">}</span> | |
| 1459 1446 | |
| 1460 1447 <span class="c"># Get paths found during paths search...</span> | |
| 1461 1448 <span class="c">#</span> | |
| 1462 <a name="GetPaths-"></a>1449 <span class="k">sub </span><span class="m">GetPaths</span> <span class="s">{</span> | |
| 1463 1450 <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> | |
| 1464 1451 | |
| 1465 1452 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}} <span class="co">:</span> <span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="sc">;</span> | |
| 1466 1453 <span class="s">}</span> | |
| 1467 1454 | |
| 1468 1455 <span class="c"># Get vertices collected at various neighborhood radii...</span> | |
| 1469 1456 <span class="c">#</span> | |
| 1470 <a name="GetVerticesNeighborhoods-"></a>1457 <span class="k">sub </span><span class="m">GetVerticesNeighborhoods</span> <span class="s">{</span> | |
| 1471 1458 <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> | |
| 1472 1459 | |
| 1473 1460 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoods</span>}} <span class="co">:</span> <span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoods</span>}}<span class="sc">;</span> | |
| 1474 1461 <span class="s">}</span> | |
| 1475 1462 | |
| 1476 1463 <span class="c"># Get vertices, along with their successor vertices, collected at various neighborhood radii as</span> | |
| 1477 1464 <span class="c"># a list containing references to lists with first value corresponding to vertex ID and second value</span> | |
| 1478 1465 <span class="c"># a reference to a list containing its successors.</span> | |
| 1479 1466 <span class="c">#</span> | |
| 1480 <a name="GetVerticesNeighborhoodsWithSuccessors-"></a>1467 <span class="k">sub </span><span class="m">GetVerticesNeighborhoodsWithSuccessors</span> <span class="s">{</span> | |
| 1481 1468 <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> | |
| 1482 1469 | |
| 1483 1470 <span class="k">return</span> <span class="k">wantarray</span> ? <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoodsWithSuccessors</span>}} <span class="co">:</span> <span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoodsWithSuccessors</span>}}<span class="sc">;</span> | |
| 1484 1471 <span class="s">}</span> | |
| 1485 1472 | |
| 1486 1473 <span class="c"># Return a string containg data for PathsTraversal object...</span> | |
| 1487 <a name="StringifyPathsTraversal-"></a>1474 <span class="k">sub </span><span class="m">StringifyPathsTraversal</span> <span class="s">{</span> | |
| 1488 1475 <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> | |
| 1489 1476 <span class="k">my</span><span class="s">(</span><span class="i">$PathsTraversalString</span><span class="s">)</span><span class="sc">;</span> | |
| 1490 1477 | |
| 1491 1478 <span class="i">$PathsTraversalString</span> = <span class="q">"PathsTraversalMode: "</span> . <span class="i">$This</span>->{<span class="w">TraversalMode</span>}<span class="sc">;</span> | |
| 1492 1479 <span class="i">$PathsTraversalString</span> .= <span class="q">"; PathsTraversalType: "</span> . <span class="i">$This</span>->{<span class="w">TraversalType</span>}<span class="sc">;</span> | |
| 1493 1480 | |
| 1494 1481 <span class="c"># Vertices ordered by traversal...</span> | |
| 1495 1482 <span class="i">$PathsTraversalString</span> .= <span class="q">"; Vertices: "</span> . <span class="k">join</span><span class="s">(</span><span class="q">' '</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span><span class="sc">;</span> | |
| 1496 1483 | |
| 1497 1484 <span class="c"># Stringify depths of vertices...</span> | |
| 1498 1485 <span class="i">$PathsTraversalString</span> .= <span class="q">"; "</span> . <span class="i">$This</span><span class="i">->StringifyVerticesDepth</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1499 1486 | |
| 1500 1487 <span class="c"># Stringify roots of vertices...</span> | |
| 1501 1488 <span class="i">$PathsTraversalString</span> .= <span class="q">"; "</span> . <span class="i">$This</span><span class="i">->StringifyVerticesRoots</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1502 1489 | |
| 1503 1490 <span class="c"># Stringify predecessor of vertices...</span> | |
| 1504 1491 <span class="i">$PathsTraversalString</span> .= <span class="q">"; "</span> . <span class="i">$This</span><span class="i">->StringifyVerticesPredecessors</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1505 1492 | |
| 1506 1493 <span class="c"># Stringify successor vertices...</span> | |
| 1507 1494 <span class="i">$PathsTraversalString</span> .= <span class="q">"; "</span> . <span class="i">$This</span><span class="i">->StringifyVerticesSuccessors</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1508 1495 | |
| 1509 1496 <span class="c"># Stringify paths...</span> | |
| 1510 1497 <span class="i">$PathsTraversalString</span> .= <span class="q">"; "</span> . <span class="i">$This</span><span class="i">->StringifyPaths</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1511 1498 | |
| 1512 1499 <span class="c"># Stringify vertices neighborhoods...</span> | |
| 1513 1500 <span class="i">$PathsTraversalString</span> .= <span class="q">"; "</span> . <span class="i">$This</span><span class="i">->StringifyVerticesNeighborhoods</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1514 1501 | |
| 1515 1502 <span class="c"># Stringify vertices neighborhoods with successors...</span> | |
| 1516 1503 <span class="i">$PathsTraversalString</span> .= <span class="q">"; "</span> . <span class="i">$This</span><span class="i">->StringifyVerticesNeighborhoodsWithSuccessors</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> | |
| 1517 1504 | |
| 1518 1505 <span class="k">return</span> <span class="i">$PathsTraversalString</span><span class="sc">;</span> | |
| 1519 1506 <span class="s">}</span> | |
| 1520 1507 | |
| 1521 1508 <span class="c"># Stringify vertices depth...</span> | |
| 1522 1509 <span class="c">#</span> | |
| 1523 <a name="StringifyVerticesDepth-"></a>1510 <span class="k">sub </span><span class="m">StringifyVerticesDepth</span> <span class="s">{</span> | |
| 1524 1511 <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> | |
| 1525 1512 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$VertexDepth</span><span class="cm">,</span> <span class="i">$DepthString</span><span class="s">)</span><span class="sc">;</span> | |
| 1526 1513 | |
| 1527 1514 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1528 1515 <span class="i">$DepthString</span> = <span class="q">"<Vertex-Depth>: None"</span><span class="sc">;</span> | |
| 1529 1516 <span class="k">return</span> <span class="i">$DepthString</span><span class="sc">;</span> | |
| 1530 1517 <span class="s">}</span> | |
| 1531 1518 | |
| 1532 1519 <span class="i">$DepthString</span> = <span class="q">"<Vertex-Depth>: "</span><span class="sc">;</span> | |
| 1533 1520 <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1534 1521 <span class="i">$VertexDepth</span> = <span class="i">$This</span>->{<span class="w">VerticesDepth</span>}{<span class="i">$VertexID</span>}<span class="sc">;</span> | |
| 1535 1522 <span class="i">$DepthString</span> .= <span class="q">" <$VertexID-$VertexDepth>"</span><span class="sc">;</span> | |
| 1536 1523 <span class="s">}</span> | |
| 1537 1524 <span class="k">return</span> <span class="i">$DepthString</span><span class="sc">;</span> | |
| 1538 1525 <span class="s">}</span> | |
| 1539 1526 | |
| 1540 1527 <span class="c"># Stringify roots of vertices...</span> | |
| 1541 1528 <span class="c">#</span> | |
| 1542 <a name="StringifyVerticesRoots-"></a>1529 <span class="k">sub </span><span class="m">StringifyVerticesRoots</span> <span class="s">{</span> | |
| 1543 1530 <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> | |
| 1544 1531 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$RootVertexID</span><span class="cm">,</span> <span class="i">$RootsString</span><span class="s">)</span><span class="sc">;</span> | |
| 1545 1532 | |
| 1546 1533 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1547 1534 <span class="i">$RootsString</span> = <span class="q">"<Vertex-RootVertex>: None"</span><span class="sc">;</span> | |
| 1548 1535 <span class="k">return</span> <span class="i">$RootsString</span><span class="sc">;</span> | |
| 1549 1536 <span class="s">}</span> | |
| 1550 1537 | |
| 1551 1538 <span class="i">$RootsString</span> = <span class="q">"<Vertex-RootVertex>: "</span><span class="sc">;</span> | |
| 1552 1539 <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1553 1540 <span class="i">$RootVertexID</span> = <span class="i">$This</span>->{<span class="w">VerticesRoots</span>}{<span class="i">$VertexID</span>}<span class="sc">;</span> | |
| 1554 1541 <span class="i">$RootsString</span> .= <span class="q">" <$VertexID-$RootVertexID>"</span><span class="sc">;</span> | |
| 1555 1542 <span class="s">}</span> | |
| 1556 1543 <span class="k">return</span> <span class="i">$RootsString</span><span class="sc">;</span> | |
| 1557 1544 <span class="s">}</span> | |
| 1558 1545 | |
| 1559 1546 <span class="c"># Stringify predecessor of vertices...</span> | |
| 1560 1547 <span class="c">#</span> | |
| 1561 <a name="StringifyVerticesPredecessors-"></a>1548 <span class="k">sub </span><span class="m">StringifyVerticesPredecessors</span> <span class="s">{</span> | |
| 1562 1549 <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> | |
| 1563 1550 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$PredecessorVertexID</span><span class="cm">,</span> <span class="i">$PredecessorString</span><span class="s">)</span><span class="sc">;</span> | |
| 1564 1551 | |
| 1565 1552 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1566 1553 <span class="i">$PredecessorString</span> = <span class="q">"<Vertex-PredecessorVertex>: None"</span><span class="sc">;</span> | |
| 1567 1554 <span class="k">return</span> <span class="i">$PredecessorString</span><span class="sc">;</span> | |
| 1568 1555 <span class="s">}</span> | |
| 1569 1556 | |
| 1570 1557 <span class="i">$PredecessorString</span> = <span class="q">"<Vertex-PredecessorVertex>: "</span><span class="sc">;</span> | |
| 1571 1558 <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1572 1559 <span class="i">$PredecessorVertexID</span> = <span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}{<span class="i">$VertexID</span>}<span class="sc">;</span> | |
| 1573 1560 <span class="i">$PredecessorString</span> .= <span class="q">" <$VertexID-$PredecessorVertexID>"</span><span class="sc">;</span> | |
| 1574 1561 <span class="s">}</span> | |
| 1575 1562 <span class="k">return</span> <span class="i">$PredecessorString</span><span class="sc">;</span> | |
| 1576 1563 <span class="s">}</span> | |
| 1577 1564 | |
| 1578 1565 <span class="c"># Stringify successor vertices...</span> | |
| 1579 1566 <span class="c">#</span> | |
| 1580 <a name="StringifyVerticesSuccessors-"></a>1567 <span class="k">sub </span><span class="m">StringifyVerticesSuccessors</span> <span class="s">{</span> | |
| 1581 1568 <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> | |
| 1582 1569 <span class="k">my</span><span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$SuccessorString</span><span class="cm">,</span> <span class="i">$VerticesSuccessorsString</span><span class="s">)</span><span class="sc">;</span> | |
| 1583 1570 | |
| 1584 1571 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1585 1572 <span class="i">$SuccessorString</span> = <span class="q">"<Vertex-VerticesSuccessorsList>: None"</span><span class="sc">;</span> | |
| 1586 1573 <span class="k">return</span> <span class="i">$SuccessorString</span><span class="sc">;</span> | |
| 1587 1574 <span class="s">}</span> | |
| 1588 1575 | |
| 1589 1576 <span class="i">$SuccessorString</span> = <span class="q">"<Vertex-VerticesSuccessorsList>: "</span><span class="sc">;</span> | |
| 1590 1577 <span class="k">for</span> <span class="i">$VertexID</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Vertices</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1591 1578 <span class="k">if</span> <span class="s">(</span><span class="k">exists</span><span class="s">(</span><span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}<span class="s">)</span> && <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1592 1579 <span class="i">$VerticesSuccessorsString</span> = <span class="k">join</span><span class="s">(</span><span class="q">','</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesSuccessors</span>}{<span class="i">$VertexID</span>}}<span class="s">)</span><span class="sc">;</span> | |
| 1593 1580 <span class="s">}</span> | |
| 1594 1581 <span class="k">else</span> <span class="s">{</span> | |
| 1595 1582 <span class="i">$VerticesSuccessorsString</span> = <span class="q">"None"</span><span class="sc">;</span> | |
| 1596 1583 <span class="s">}</span> | |
| 1597 1584 <span class="i">$SuccessorString</span> .= <span class="q">" <$VertexID-$VerticesSuccessorsString>"</span><span class="sc">;</span> | |
| 1598 1585 <span class="s">}</span> | |
| 1599 1586 <span class="k">return</span> <span class="i">$SuccessorString</span><span class="sc">;</span> | |
| 1600 1587 <span class="s">}</span> | |
| 1601 1588 | |
| 1602 1589 <span class="c"># Strinigify paths...</span> | |
| 1603 1590 <span class="c">#</span> | |
| 1604 <a name="StringifyPaths-"></a>1591 <span class="k">sub </span><span class="m">StringifyPaths</span> <span class="s">{</span> | |
| 1605 1592 <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> | |
| 1606 1593 <span class="k">my</span><span class="s">(</span><span class="i">$PathsString</span><span class="cm">,</span> <span class="i">$Path</span><span class="s">)</span><span class="sc">;</span> | |
| 1607 1594 | |
| 1608 1595 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1609 1596 <span class="i">$PathsString</span> = <span class="q">"Paths: None"</span><span class="sc">;</span> | |
| 1610 1597 <span class="k">return</span> <span class="i">$PathsString</span><span class="sc">;</span> | |
| 1611 1598 <span class="s">}</span> | |
| 1612 1599 | |
| 1613 1600 <span class="k">my</span><span class="s">(</span><span class="i">$FirstPath</span><span class="s">)</span><span class="sc">;</span> | |
| 1614 1601 <span class="i">$PathsString</span> = <span class="q">"Paths: "</span><span class="sc">;</span> | |
| 1615 1602 <span class="i">$FirstPath</span> = <span class="n">1</span><span class="sc">;</span> | |
| 1616 1603 <span class="k">for</span> <span class="i">$Path</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">Paths</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1617 1604 <span class="k">if</span> <span class="s">(</span><span class="i">$FirstPath</span><span class="s">)</span> <span class="s">{</span> | |
| 1618 1605 <span class="i">$FirstPath</span> = <span class="n">0</span><span class="sc">;</span> | |
| 1619 1606 <span class="s">}</span> | |
| 1620 1607 <span class="k">else</span> <span class="s">{</span> | |
| 1621 1608 <span class="i">$PathsString</span> .= <span class="q">" "</span><span class="sc">;</span> | |
| 1622 1609 <span class="s">}</span> | |
| 1623 1610 <span class="i">$PathsString</span> .= <span class="q">"<"</span> . <span class="k">join</span><span class="s">(</span><span class="q">'-'</span><span class="cm">,</span> <span class="i">$Path</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="s">)</span> . <span class="q">">"</span><span class="sc">;</span> | |
| 1624 1611 <span class="s">}</span> | |
| 1625 1612 <span class="k">return</span> <span class="i">$PathsString</span><span class="sc">;</span> | |
| 1626 1613 <span class="s">}</span> | |
| 1627 1614 | |
| 1628 1615 <span class="c"># Strinigify vertices neighborhoods...</span> | |
| 1629 1616 <span class="c">#</span> | |
| 1630 <a name="StringifyVerticesNeighborhoods-"></a>1617 <span class="k">sub </span><span class="m">StringifyVerticesNeighborhoods</span> <span class="s">{</span> | |
| 1631 1618 <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> | |
| 1632 1619 <span class="k">my</span><span class="s">(</span><span class="i">$NeighborhoodsString</span><span class="cm">,</span> <span class="i">$NeighborhoodVerticesString</span><span class="cm">,</span> <span class="i">$Radius</span><span class="s">)</span><span class="sc">;</span> | |
| 1633 1620 | |
| 1634 1621 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoods</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1635 1622 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVerticesList>: None"</span><span class="sc">;</span> | |
| 1636 1623 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> | |
| 1637 1624 <span class="s">}</span> | |
| 1638 1625 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVerticesList>:"</span><span class="sc">;</span> | |
| 1639 1626 <span class="k">for</span> <span class="i">$Radius</span> <span class="s">(</span><span class="n">0</span> .. <span class="i">$#</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoods</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1640 1627 <span class="i">$NeighborhoodVerticesString</span> = <span class="k">join</span><span class="s">(</span><span class="q">','</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoods</span>}[<span class="i">$Radius</span>]}<span class="s">)</span><span class="sc">;</span> | |
| 1641 1628 <span class="i">$NeighborhoodsString</span> .= <span class="q">" <$Radius-$NeighborhoodVerticesString>"</span><span class="sc">;</span> | |
| 1642 1629 <span class="s">}</span> | |
| 1643 1630 | |
| 1644 1631 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> | |
| 1645 1632 <span class="s">}</span> | |
| 1646 1633 | |
| 1647 1634 <span class="c"># Strinigify vertices neighborhoods...</span> | |
| 1648 1635 <span class="c">#</span> | |
| 1649 <a name="StringifyVerticesNeighborhoodsWithSuccessors-"></a>1636 <span class="k">sub </span><span class="m">StringifyVerticesNeighborhoodsWithSuccessors</span> <span class="s">{</span> | |
| 1650 1637 <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> | |
| 1651 1638 <span class="k">my</span><span class="s">(</span><span class="i">$NeighborhoodsString</span><span class="cm">,</span> <span class="i">$NeighborhoodVertexSuccessorsString</span><span class="cm">,</span> <span class="i">$Radius</span><span class="cm">,</span> <span class="i">$NeighborhoodVertericesWithSuccessorsRef</span><span class="cm">,</span> <span class="i">$NeighborhoodVertexWithSuccessorsRef</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$NeighborhoodVertexSuccessorsRef</span><span class="s">)</span><span class="sc">;</span> | |
| 1652 1639 | |
| 1653 1640 <span class="k">if</span> <span class="s">(</span>!<span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoodsWithSuccessors</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1654 1641 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None"</span><span class="sc">;</span> | |
| 1655 1642 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> | |
| 1656 1643 <span class="s">}</span> | |
| 1657 1644 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None"</span><span class="sc">;</span> | |
| 1658 1645 | |
| 1659 1646 <span class="i">$Radius</span> = <span class="n">0</span><span class="sc">;</span> | |
| 1660 1647 <span class="k">for</span> <span class="i">$NeighborhoodVertericesWithSuccessorsRef</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$This</span>->{<span class="w">VerticesNeighborhoodsWithSuccessors</span>}}<span class="s">)</span> <span class="s">{</span> | |
| 1661 1648 <span class="k">for</span> <span class="i">$NeighborhoodVertexWithSuccessorsRef</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$NeighborhoodVertericesWithSuccessorsRef</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1662 1649 <span class="s">(</span><span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$NeighborhoodVertexSuccessorsRef</span><span class="s">)</span> = <span class="i">@</span>{<span class="i">$NeighborhoodVertexWithSuccessorsRef</span>}<span class="sc">;</span> | |
| 1663 1650 <span class="i">$NeighborhoodVertexSuccessorsString</span> = <span class="q">'None'</span><span class="sc">;</span> | |
| 1664 1651 <span class="k">if</span> <span class="s">(</span><span class="i">@</span>{<span class="i">$NeighborhoodVertexSuccessorsRef</span>}<span class="s">)</span> <span class="s">{</span> | |
| 1665 1652 <span class="i">$NeighborhoodVertexSuccessorsString</span> = <span class="k">join</span><span class="s">(</span><span class="q">','</span><span class="cm">,</span> <span class="i">@</span>{<span class="i">$NeighborhoodVertexSuccessorsRef</span>}<span class="s">)</span><span class="sc">;</span> | |
| 1666 1653 <span class="s">}</span> | |
| 1667 1654 <span class="i">$NeighborhoodsString</span> .= <span class="q">" <$Radius-$VertexID-$NeighborhoodVertexSuccessorsString>"</span><span class="sc">;</span> | |
| 1668 1655 <span class="s">}</span> | |
| 1669 1656 <span class="i">$Radius</span>++<span class="sc">;</span> | |
| 1670 1657 <span class="s">}</span> | |
| 1671 1658 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> | |
| 1672 1659 <span class="s">}</span> | |
| 1673 1660 | |
| 1674 1661 <span class="c"># Return a reference to new paths traversal object...</span> | |
| 1675 <a name="Copy-"></a>1662 <span class="k">sub </span><span class="m">Copy</span> <span class="s">{</span> | |
| 1676 1663 <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> | |
| 1677 1664 <span class="k">my</span><span class="s">(</span><span class="i">$NewPathsTraversal</span><span class="s">)</span><span class="sc">;</span> | |
| 1678 1665 | |
| 1679 1666 <span class="i">$NewPathsTraversal</span> = <span class="i">Storable::dclone</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span><span class="sc">;</span> | |
| 1680 1667 | |
| 1681 1668 <span class="k">return</span> <span class="i">$NewPathsTraversal</span><span class="sc">;</span> | |
| 1682 1669 <span class="s">}</span> | |
| 1683 1670 | |
| 1684 <a name="EOF-"></a></pre> | |
| 1685 <p> </p> | |
| 1686 <br /> | |
| 1687 <center> | |
| 1688 <img src="../../../images/h2o2.png"> | |
| 1689 </center> | |
| 1690 </body> | |
| 1691 </html> |