Mercurial > repos > deepakjadmin > mayatool3_test3
diff mayachemtools/docs/modules/html/code/PathsTraversal.html @ 0:73ae111cf86f draft
Uploaded
| author | deepakjadmin |
|---|---|
| date | Wed, 20 Jan 2016 11:55:01 -0500 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/mayachemtools/docs/modules/html/code/PathsTraversal.html Wed Jan 20 11:55:01 2016 -0500 @@ -0,0 +1,1691 @@ +<html> +<head> +<title>MayaChemTools:Code:Graph::PathsTraversal.pm</title> +<meta http-equiv="content-type" content="text/html;charset=utf-8"> +<link rel="stylesheet" type="text/css" href="../../../css/MayaChemToolsCode.css"> +</head> +<body leftmargin="20" rightmargin="20" topmargin="10" bottommargin="10"> +<br/> +<center> +<a href="http://www.mayachemtools.org" title="MayaChemTools Home"><img src="../../../images/MayaChemToolsLogo.gif" border="0" alt="MayaChemTools"></a> +</center> +<br/> +<pre> +<a name="package-Graph::PathsTraversal-"></a> 1 <span class="k">package </span><span class="i">Graph::PathsTraversal</span><span class="sc">;</span> + 2 <span class="c">#</span> + 3 <span class="c"># $RCSfile: PathsTraversal.pm,v $</span> + 4 <span class="c"># $Date: 2015/02/28 20:49:06 $</span> + 5 <span class="c"># $Revision: 1.29 $</span> + 6 <span class="c">#</span> + 7 <span class="c"># Author: Manish Sud <msud@san.rr.com></span> + 8 <span class="c">#</span> + 9 <span class="c"># Copyright (C) 2015 Manish Sud. All rights reserved.</span> + 10 <span class="c">#</span> + 11 <span class="c"># This file is part of MayaChemTools.</span> + 12 <span class="c">#</span> + 13 <span class="c"># MayaChemTools is free software; you can redistribute it and/or modify it under</span> + 14 <span class="c"># the terms of the GNU Lesser General Public License as published by the Free</span> + 15 <span class="c"># Software Foundation; either version 3 of the License, or (at your option) any</span> + 16 <span class="c"># later version.</span> + 17 <span class="c">#</span> + 18 <span class="c"># MayaChemTools is distributed in the hope that it will be useful, but without</span> + 19 <span class="c"># any warranty; without even the implied warranty of merchantability of fitness</span> + 20 <span class="c"># for a particular purpose. See the GNU Lesser General Public License for more</span> + 21 <span class="c"># details.</span> + 22 <span class="c">#</span> + 23 <span class="c"># You should have received a copy of the GNU Lesser General Public License</span> + 24 <span class="c"># along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or</span> + 25 <span class="c"># write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,</span> + 26 <span class="c"># Boston, MA, 02111-1307, USA.</span> + 27 <span class="c">#</span> + 28 + 29 <span class="k">use</span> <span class="w">strict</span><span class="sc">;</span> + 30 <span class="k">use</span> <span class="w">Carp</span><span class="sc">;</span> + 31 <span class="k">use</span> <span class="w">Exporter</span><span class="sc">;</span> + 32 <span class="k">use</span> <span class="w">Graph</span><span class="sc">;</span> + 33 <span class="k">use</span> <span class="w">Graph::Path</span><span class="sc">;</span> + 34 + 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> + 36 + 37 <span class="i">@ISA</span> = <span class="q">qw(Exporter)</span><span class="sc">;</span> + 38 <span class="i">@EXPORT</span> = <span class="q">qw()</span><span class="sc">;</span> + 39 <span class="i">@EXPORT_OK</span> = <span class="q">qw()</span><span class="sc">;</span> + 40 + 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> + 42 + 43 <span class="c"># Setup class variables...</span> + 44 <span class="k">my</span><span class="s">(</span><span class="i">$ClassName</span><span class="s">)</span><span class="sc">;</span> + 45 <span class="i">_InitializeClass</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 46 + 47 <span class="c"># Overload Perl functions...</span> + 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> + 49 + 50 <span class="c"># Class constructor...</span> +<a name="new-"></a> 51 <span class="k">sub </span><span class="m">new</span> <span class="s">{</span> + 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> + 53 + 54 <span class="c"># Initialize object...</span> + 55 <span class="k">my</span> <span class="i">$This</span> = <span class="s">{</span><span class="s">}</span><span class="sc">;</span> + 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> + 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> + 58 + 59 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 60 <span class="s">}</span> + 61 + 62 <span class="c"># Initialize object data...</span> +<a name="_InitializePathsTraversal-"></a> 63 <span class="k">sub </span><span class="m">_InitializePathsTraversal</span> <span class="s">{</span> + 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> + 65 + 66 <span class="c"># Graph object...</span> + 67 <span class="i">$This</span>->{<span class="w">Graph</span>} = <span class="i">$Graph</span><span class="sc">;</span> + 68 + 69 <span class="c"># Traversal mode: Vertex or Path</span> + 70 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">''</span><span class="sc">;</span> + 71 + 72 <span class="c"># Traversal type: DFS, DFSWithLimit, BFS, BFSWithLimit...</span> + 73 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">''</span><span class="sc">;</span> + 74 + 75 <span class="c"># For finding root vertex and controlling search...</span> + 76 <span class="k">my</span><span class="s">(</span><span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 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> + 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> + 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> + 80 + 81 <span class="c"># Root vertex of all visited vertices...</span> + 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> + 83 + 84 <span class="c"># Visited vertices...</span> + 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> + 86 + 87 <span class="c"># Finished vertices...</span> + 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> + 89 + 90 <span class="c"># List of active vertices during DFS/BFS search...</span> + 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> + 92 + 93 <span class="c"># List of ordered vertices traversed during DFS/BFS search...</span> + 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> + 95 + 96 <span class="c"># Vertex neighbors during traversal...</span> + 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> + 98 + 99 <span class="c"># Vertices depth from root...</span> + 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> + 101 + 102 <span class="c"># Predecessor of each vertex during vertex traversal. For root vertex, it's root itself...</span> + 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> + 104 + 105 <span class="c"># Successors of each vertex during vertex traversal...</span> + 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> + 107 + 108 <span class="c"># Vertices at different neighborhood levels during vertex traversal...</span> + 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> + 110 + 111 <span class="c"># Vertices, along with their successors, at different neighborhood levels during vertex traversal...</span> + 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> + 113 + 114 <span class="c"># Visited edges during Path TraversalMode...</span> + 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> + 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> + 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> + 118 + 119 <span class="c"># Vertex path during Path TraversalMode...</span> + 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> + 121 + 122 <span class="c"># Allow cycles in paths during VertexNeighborhood TraversalMode. By default, cycles are not allowed</span> + 123 <span class="c"># during vertex traversal: a vertex is only visited once during BFS search for neighborhoods. For</span> + 124 <span class="c"># neighborhood vertices search during successors identification, vertex cycles are explicity allowed</span> + 125 <span class="c"># to indentify all successors.</span> + 126 <span class="i">$This</span>->{<span class="w">AllowVertexCycles</span>} = <span class="n">0</span><span class="sc">;</span> + 127 + 128 <span class="c"># Allow cycles in paths during Path TraversalMode...</span> + 129 <span class="i">$This</span>->{<span class="w">AllowPathCycles</span>} = <span class="n">1</span><span class="sc">;</span> + 130 + 131 <span class="c"># Cycle closure vertices during Path TraversalMode...</span> + 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> + 133 + 134 <span class="c"># Paths traversed during search...</span> + 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> + 136 + 137 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 138 <span class="s">}</span> + 139 + 140 <span class="c"># Initialize class ...</span> +<a name="_InitializeClass-"></a> 141 <span class="k">sub </span><span class="m">_InitializeClass</span> <span class="s">{</span> + 142 <span class="c">#Class name...</span> + 143 <span class="i">$ClassName</span> = <span class="w">__PACKAGE__</span><span class="sc">;</span> + 144 <span class="s">}</span> + 145 + 146 <span class="c"># Perform a depth first search (DFS)...</span> + 147 <span class="c">#</span> +<a name="PerformDepthFirstSearch-"></a> 148 <span class="k">sub </span><span class="m">PerformDepthFirstSearch</span> <span class="s">{</span> + 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> + 150 + 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> + 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> + 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> + 154 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 155 <span class="s">}</span> + 156 <span class="s">}</span> + 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> + 158 <span class="s">}</span> + 159 + 160 <span class="c"># Perform a depth first search (DFS) with limit on depth...</span> + 161 <span class="c">#</span> +<a name="PerformDepthFirstSearchWithLimit-"></a> 162 <span class="k">sub </span><span class="m">PerformDepthFirstSearchWithLimit</span> <span class="s">{</span> + 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> + 164 + 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> + 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> + 167 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 168 <span class="s">}</span> + 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> + 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> + 171 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 172 <span class="s">}</span> + 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> + 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> + 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> + 176 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 177 <span class="s">}</span> + 178 <span class="s">}</span> + 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> + 180 <span class="s">}</span> + 181 + 182 <span class="c"># Perform a breadth first search (BFS)...</span> + 183 <span class="c">#</span> +<a name="PerformBreadthFirstSearch-"></a> 184 <span class="k">sub </span><span class="m">PerformBreadthFirstSearch</span> <span class="s">{</span> + 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> + 186 + 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> + 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> + 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> + 190 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 191 <span class="s">}</span> + 192 <span class="s">}</span> + 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> + 194 <span class="s">}</span> + 195 + 196 <span class="c"># Perform a breadth first search (BFS) with limit...</span> + 197 <span class="c">#</span> +<a name="PerformBreadthFirstSearchWithLimit-"></a> 198 <span class="k">sub </span><span class="m">PerformBreadthFirstSearchWithLimit</span> <span class="s">{</span> + 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> + 200 + 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> + 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> + 203 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 204 <span class="s">}</span> + 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> + 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> + 207 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 208 <span class="s">}</span> + 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> + 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> + 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> + 212 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 213 <span class="s">}</span> + 214 <span class="s">}</span> + 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> + 216 <span class="s">}</span> + 217 + 218 <span class="c"># Perform appropriate vertex search...</span> + 219 <span class="c">#</span> +<a name="_PerformVertexSearch-"></a> 220 <span class="k">sub </span><span class="m">_PerformVertexSearch</span> <span class="s">{</span> + 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> + 222 + 223 <span class="c"># Setup search...</span> + 224 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'Vertex'</span><span class="sc">;</span> + 225 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="i">$SearchType</span><span class="sc">;</span> + 226 + 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> + 228 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> + 229 <span class="s">}</span> + 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> + 231 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> + 232 <span class="s">}</span> + 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> + 234 <span class="i">$This</span>->{<span class="w">TargetVertex</span>} = <span class="i">$TargetVertexID</span><span class="sc">;</span> + 235 <span class="s">}</span> + 236 + 237 <span class="c"># Perform search...</span> + 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> + 239 <span class="s">}</span> + 240 + 241 <span class="c"># Perform DFS or BFS traversal with or without any limits...</span> + 242 <span class="c">#</span> +<a name="_TraverseGraph-"></a> 243 <span class="k">sub </span><span class="m">_TraverseGraph</span> <span class="s">{</span> + 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> + 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> + 246 + 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> + 248 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 249 <span class="s">}</span> + 250 + 251 <span class="i">$ProcessingVertices</span> = <span class="n">1</span><span class="sc">;</span> + 252 + 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> + 254 <span class="c"># Set root vertex...</span> + 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> + 256 <span class="k">my</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> + 257 + 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> + 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> + 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> + 261 <span class="s">}</span> + 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> + 263 <span class="s">}</span> + 264 + 265 <span class="c"># Get current active vertex...</span> + 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> + 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> + 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> + 269 <span class="s">}</span> + 270 + 271 <span class="c"># Get next available neighbor of current vertex...</span> + 272 <span class="c">#</span> + 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> + 274 + 275 <span class="c"># Process neighbor or current vertex...</span> + 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> + 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> + 278 <span class="s">}</span> + 279 <span class="k">else</span> <span class="s">{</span> + 280 <span class="c"># Finished with all neighbors for current vertex...</span> + 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> + 282 <span class="s">}</span> + 283 <span class="s">}</span> + 284 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 285 <span class="s">}</span> + 286 + 287 <span class="c"># Get root vertex to start the search...</span> + 288 <span class="c">#</span> + 289 <span class="c"># Notes:</span> + 290 <span class="c"># . User specification of root vertex forces traversal in a specific connected component</span> + 291 <span class="c"># of graph; To traverse find all connected components, perform traversal without specification of</span> + 292 <span class="c"># a root vertex.</span> + 293 <span class="c">#</span> +<a name="_GetRootVertex-"></a> 294 <span class="k">sub </span><span class="m">_GetRootVertex</span> <span class="s">{</span> + 295 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 296 <span class="k">my</span><span class="s">(</span><span class="i">$RootVertexID</span><span class="s">)</span><span class="sc">;</span> + 297 + 298 <span class="c"># Check for specified root vertex and constrain traversal to specific connected</span> + 299 <span class="c"># component by setting root limit...</span> + 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> + 301 <span class="i">$RootVertexID</span> = <span class="i">$This</span>->{<span class="w">RootVertex</span>}<span class="sc">;</span> + 302 <span class="k">delete</span> <span class="i">$This</span>->{<span class="w">RootVertex</span>}<span class="sc">;</span> + 303 <span class="i">$This</span>->{<span class="w">RootVertexSpecified</span>} = <span class="n">1</span><span class="sc">;</span> + 304 + 305 <span class="k">return</span> <span class="i">$RootVertexID</span><span class="sc">;</span> + 306 <span class="s">}</span> + 307 <span class="c"># Traversal limited to connected component containing specified root vertex...</span> + 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> + 309 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 310 <span class="s">}</span> + 311 + 312 <span class="c"># Use first vertex in sorted available vertices list to get root vertex. Vertex</span> + 313 <span class="c"># with largest degree could also be used as root vertex. However, for all</span> + 314 <span class="c"># practical purposes, any arbitrary vertex can be used as root vertex to</span> + 315 <span class="c"># start search for another disconnected component of the graph.</span> + 316 <span class="c">#</span> + 317 <span class="k">my</span><span class="s">(</span><span class="i">@VerticesToVisit</span><span class="s">)</span><span class="sc">;</span> + 318 + 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> + 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> + 321 <span class="k">if</span> <span class="s">(</span><span class="i">@VerticesToVisit</span><span class="s">)</span> <span class="s">{</span> + 322 <span class="i">$RootVertexID</span> = <span class="i">$VerticesToVisit</span>[<span class="n">0</span>]<span class="sc">;</span> + 323 <span class="s">}</span> + 324 <span class="k">return</span> <span class="i">$RootVertexID</span><span class="sc">;</span> + 325 <span class="s">}</span> + 326 + 327 <span class="c"># Get current or new active vertex for DFS/BFS traversals...</span> + 328 <span class="c">#</span> +<a name="_GetActiveVertex-"></a> 329 <span class="k">sub </span><span class="m">_GetActiveVertex</span> <span class="s">{</span> + 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> + 331 <span class="k">my</span><span class="s">(</span><span class="i">$ActiveVertexID</span><span class="s">)</span><span class="sc">;</span> + 332 + 333 <span class="i">$ActiveVertexID</span> = <span class="k">undef</span><span class="sc">;</span> + 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> + 335 <span class="c"># For DFS, it's last vertex in LIFO queue...</span> + 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> + 337 <span class="s">}</span> + 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> + 339 <span class="c"># For BFS, it's first vertex in FIFO queue...</span> + 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> + 341 <span class="s">}</span> + 342 <span class="k">return</span> <span class="i">$ActiveVertexID</span><span class="sc">;</span> + 343 <span class="s">}</span> + 344 + 345 <span class="c"># Get available neigbor of specified vertex...</span> + 346 <span class="c">#</span> +<a name="_GetNeighborVertex-"></a> 347 <span class="k">sub </span><span class="m">_GetNeighborVertex</span> <span class="s">{</span> + 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> + 349 + 350 <span class="c"># Retrieve neighbors for vertex...</span> + 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> + 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> + 353 + 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> + 355 <span class="c"># Only collect neighbors to visit below specified depth limit...</span> + 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> + 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> + 358 <span class="s">}</span> + 359 <span class="k">else</span> <span class="s">{</span> + 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> + 361 <span class="c"># Mark all other downstream neighbor vertices to be ignored from any further</span> + 362 <span class="c"># processing and avoid selection of a new root...</span> + 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> + 364 <span class="s">}</span> + 365 <span class="s">}</span> + 366 <span class="s">}</span> + 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> + 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> + 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> + 370 <span class="s">}</span> + 371 <span class="s">}</span> + 372 <span class="k">else</span> <span class="s">{</span> + 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> + 374 <span class="s">}</span> + 375 <span class="s">}</span> + 376 + 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> + 378 <span class="c"># Get available neighbor for path search...</span> + 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> + 380 <span class="s">}</span> + 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> + 382 <span class="c"># Get unvisited neighbor for vertex search...</span> + 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> + 384 <span class="s">}</span> + 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> + 386 <span class="c"># Get available neighbor during vertex neighborhood search...</span> + 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> + 388 <span class="s">}</span> + 389 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 390 <span class="s">}</span> + 391 + 392 <span class="c"># Get unvisited neighbor of specified vertex during vertex traversal...</span> + 393 <span class="c">#</span> +<a name="_GetNeighborVertexDuringVertexTraversal-"></a> 394 <span class="k">sub </span><span class="m">_GetNeighborVertexDuringVertexTraversal</span> <span class="s">{</span> + 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> + 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> + 397 + 398 <span class="c"># Get unvisited neighbor...</span> + 399 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="k">undef</span><span class="sc">;</span> + 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> + 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> + 402 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> + 403 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 404 <span class="s">}</span> + 405 <span class="s">}</span> + 406 <span class="k">return</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="sc">;</span> + 407 <span class="s">}</span> + 408 + 409 <span class="c"># Get available neighbor of specified vertex during vertex neighborhood traversal...</span> + 410 <span class="c">#</span> +<a name="_GetNeighborVertexDuringVertexNeighborhoodTraversal-"></a> 411 <span class="k">sub </span><span class="m">_GetNeighborVertexDuringVertexNeighborhoodTraversal</span> <span class="s">{</span> + 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> + 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> + 414 + 415 <span class="c"># Get available neighbor...</span> + 416 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="k">undef</span><span class="sc">;</span> + 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> + 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> + 419 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> + 420 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 421 <span class="s">}</span> + 422 <span class="c"># Look for any unvisited edge back to visited vertex...</span> + 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> + 424 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 425 <span class="s">}</span> + 426 <span class="c"># Check its depth...</span> + 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> + 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> + 429 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 430 <span class="s">}</span> + 431 <span class="s">}</span> + 432 <span class="c"># Its an edge that makes a cycle during BFS search...</span> + 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> + 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> + 435 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> + 436 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 437 <span class="s">}</span> + 438 <span class="s">}</span> + 439 <span class="k">return</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="sc">;</span> + 440 <span class="s">}</span> + 441 + 442 <span class="c"># Get available neighbor of specified vertex during path traversal...</span> + 443 <span class="c">#</span> +<a name="_GetNeighborVertexDuringPathTraversal-"></a> 444 <span class="k">sub </span><span class="m">_GetNeighborVertexDuringPathTraversal</span> <span class="s">{</span> + 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> + 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> + 447 + 448 <span class="c"># Get unvisited neighbor...</span> + 449 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="k">undef</span><span class="sc">;</span> + 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> + 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> + 452 <span class="c"># An unvisited vertex...</span> + 453 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> + 454 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 455 <span class="s">}</span> + 456 <span class="c"># Look for any unvisited edge back to visited vertex...</span> + 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> + 458 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 459 <span class="s">}</span> + 460 <span class="c"># Check its depth...</span> + 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> + 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> + 463 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 464 <span class="s">}</span> + 465 <span class="s">}</span> + 466 + 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> + 468 <span class="c"># part of the path from a different direction in a cycle or a left over vertex during Limit search.</span> + 469 <span class="c">#</span> + 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> + 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> + 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> + 473 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> + 474 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 475 <span class="s">}</span> + 476 <span class="s">}</span> + 477 <span class="k">else</span> <span class="s">{</span> + 478 <span class="i">$UnvisitedNeighborVertexID</span> = <span class="i">$NeighborVertexID</span><span class="sc">;</span> + 479 <span class="k">last</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 480 <span class="s">}</span> + 481 <span class="s">}</span> + 482 <span class="k">return</span> <span class="i">$UnvisitedNeighborVertexID</span><span class="sc">;</span> + 483 <span class="s">}</span> + 484 + 485 <span class="c"># Process visited vertex...</span> + 486 <span class="c">#</span> +<a name="_ProcessVisitedVertex-"></a> 487 <span class="k">sub </span><span class="m">_ProcessVisitedVertex</span> <span class="s">{</span> + 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> + 489 + 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> + 491 <span class="c"># Add it to active vertices list...</span> + 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> + 493 + 494 <span class="c"># Mark vertex as visited vertex and take it out from the list of vertices to visit...</span> + 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> + 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> + 497 <span class="s">}</span> + 498 + 499 <span class="c"># Set up root vertex, predecessor vertex and distance from root...</span> + 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> + 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> + 502 + 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> + 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> + 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> + 506 <span class="s">}</span> + 507 + 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> + 509 + 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> + 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> + 512 <span class="s">}</span> + 513 <span class="s">}</span> + 514 <span class="k">else</span> <span class="s">{</span> + 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> + 516 + 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> + 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> + 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> + 520 <span class="s">}</span> + 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> + 522 + 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> + 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> + 525 <span class="s">}</span> + 526 + 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> + 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> + 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> + 530 <span class="s">}</span> + 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> + 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> + 533 <span class="s">}</span> + 534 <span class="s">}</span> + 535 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 536 <span class="s">}</span> + 537 + 538 <span class="c"># Process visited path...</span> + 539 <span class="c">#</span> +<a name="_ProcessVisitedPath-"></a> 540 <span class="k">sub </span><span class="m">_ProcessVisitedPath</span> <span class="s">{</span> + 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> + 542 + 543 <span class="c"># Initialize VerticesPath...</span> + 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> + 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> + 546 <span class="s">}</span> + 547 + 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> + 549 <span class="c"># Starting of a path from root...</span> + 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> + 551 <span class="s">}</span> + 552 <span class="k">else</span> <span class="s">{</span> + 553 <span class="c"># Setup path for a vertex using path information from predecessor vertex...</span> + 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> + 555 <span class="c"># Start of a new path from predecessor vertex...</span> + 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> + 557 <span class="s">}</span> + 558 <span class="k">else</span> <span class="s">{</span> + 559 <span class="k">my</span><span class="s">(</span><span class="i">$PredecessorVertexPath</span><span class="s">)</span><span class="sc">;</span> + 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> + 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> + 562 <span class="s">}</span> + 563 <span class="s">}</span> + 564 <span class="s">}</span> + 565 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 566 <span class="s">}</span> + 567 + 568 <span class="c"># Process visited edge...</span> + 569 <span class="c">#</span> +<a name="_ProcessVisitedEdge-"></a> 570 <span class="k">sub </span><span class="m">_ProcessVisitedEdge</span> <span class="s">{</span> + 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> + 572 + 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> + 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> + 575 <span class="s">}</span> + 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> + 577 + 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> + 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> + 580 <span class="s">}</span> + 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> + 582 + 583 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 584 <span class="s">}</span> + 585 + 586 <span class="c"># Finished processing active vertex...</span> + 587 <span class="c">#</span> +<a name="_ProcessFinishedVertex-"></a> 588 <span class="k">sub </span><span class="m">_ProcessFinishedVertex</span> <span class="s">{</span> + 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> + 590 + 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> + 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> + 593 <span class="c"># Add vertex to list of vertices found by traversal...</span> + 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> + 595 <span class="s">}</span> + 596 + 597 <span class="c"># Any active vertices left...</span> + 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> + 599 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 600 <span class="s">}</span> + 601 + 602 <span class="c"># Take it off active vertices list...</span> + 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> + 604 <span class="c"># For DFS, it's last vertex in LIFO queue...</span> + 605 <span class="k">pop</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}}<span class="sc">;</span> + 606 <span class="s">}</span> + 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> + 608 <span class="c"># For BFS, it's first vertex in FIFO queue...</span> + 609 <span class="k">shift</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ActiveVertices</span>}}<span class="sc">;</span> + 610 <span class="s">}</span> + 611 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 612 <span class="s">}</span> + 613 + 614 <span class="c"># Mark all other downstream neighbor vertices to be ignored from any further</span> + 615 <span class="c"># processing...</span> + 616 <span class="c">#</span> +<a name="_IgnoreDownstreamNeighbors-"></a> 617 <span class="k">sub </span><span class="m">_IgnoreDownstreamNeighbors</span> <span class="s">{</span> + 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> + 619 + 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> + 621 <span class="c"># Mark vertex as visited vertex and take it out from the list of vertices to visit...</span> + 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> + 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> + 624 + 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> + 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> + 627 <span class="s">}</span> + 628 <span class="s">}</span> + 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> + 630 + 631 <span class="i">@NeighborsVertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 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> + 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> + 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> + 635 <span class="c"># Avoid going back to predecessor vertex which has already been ignored...</span> + 636 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> + 637 <span class="s">}</span> + 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> + 639 <span class="s">}</span> + 640 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 641 <span class="s">}</span> + 642 + 643 <span class="c"># Is it a visited edge?</span> + 644 <span class="c">#</span> +<a name="_IsVisitedEdge-"></a> 645 <span class="k">sub </span><span class="m">_IsVisitedEdge</span> <span class="s">{</span> + 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> + 647 + 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> + 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> + 650 <span class="k">return</span> <span class="n">1</span><span class="sc">;</span> + 651 <span class="s">}</span> + 652 <span class="s">}</span> + 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> + 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> + 655 <span class="k">return</span> <span class="n">1</span><span class="sc">;</span> + 656 <span class="s">}</span> + 657 <span class="s">}</span> + 658 <span class="k">return</span> <span class="n">0</span><span class="sc">;</span> + 659 <span class="s">}</span> + 660 + 661 <span class="c"># Is it a cycle closure edge?</span> + 662 <span class="c">#</span> + 663 <span class="c"># Notes:</span> + 664 <span class="c"># . Presence of VertexID2 in DFS path traversed for VertexID1 make it a cycle</span> + 665 <span class="c"># closure edge...</span> + 666 <span class="c">#</span> +<a name="_IsCycleClosureEdge-"></a> 667 <span class="k">sub </span><span class="m">_IsCycleClosureEdge</span> <span class="s">{</span> + 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> + 669 + 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> + 671 <span class="k">return</span> <span class="n">0</span><span class="sc">;</span> + 672 <span class="s">}</span> + 673 <span class="k">my</span><span class="s">(</span><span class="i">$Path</span><span class="s">)</span><span class="sc">;</span> + 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> + 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> + 676 <span class="k">return</span> <span class="n">1</span><span class="sc">;</span> + 677 <span class="s">}</span> + 678 <span class="s">}</span> + 679 <span class="k">return</span> <span class="n">0</span><span class="sc">;</span> + 680 <span class="s">}</span> + 681 + 682 <span class="c"># Search paths starting from a specified vertex with no sharing of edges in paths traversed.</span> + 683 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 684 <span class="c"># completing the cycle.</span> + 685 <span class="c">#</span> +<a name="PerformPathsSearch-"></a> 686 <span class="k">sub </span><span class="m">PerformPathsSearch</span> <span class="s">{</span> + 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> + 688 + 689 <span class="c"># Make sure start vertex is defined...</span> + 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> + 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> + 692 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 693 <span class="s">}</span> + 694 + 695 <span class="c"># Make sure start vertex is valid...</span> + 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> + 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> + 698 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 699 <span class="s">}</span> + 700 + 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> + 702 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> + 703 <span class="s">}</span> + 704 + 705 <span class="c"># Perform paths search...</span> + 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> + 707 <span class="s">}</span> + 708 + 709 <span class="c"># Search paths starting from a specified vertex with length upto a specified length</span> + 710 <span class="c"># with no sharing of edges in paths traversed...</span> + 711 <span class="c">#</span> + 712 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 713 <span class="c"># completing the cycle.</span> + 714 <span class="c">#</span> +<a name="PerformPathsSearchWithLengthUpto-"></a> 715 <span class="k">sub </span><span class="m">PerformPathsSearchWithLengthUpto</span> <span class="s">{</span> + 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> + 717 + 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> + 719 <span class="s">}</span> + 720 + 721 <span class="c"># Search paths starting from a specified vertex with specified length</span> + 722 <span class="c"># with no sharing of edges in paths traversed...</span> + 723 <span class="c">#</span> + 724 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 725 <span class="c"># completing the cycle.</span> + 726 <span class="c">#</span> +<a name="PerformPathsSearchWithLength-"></a> 727 <span class="k">sub </span><span class="m">PerformPathsSearchWithLength</span> <span class="s">{</span> + 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> + 729 + 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> + 731 <span class="s">}</span> + 732 + 733 + 734 <span class="c"># Search paths starting from a specified vertex with length upto a specified length</span> + 735 <span class="c"># with no sharing of edges in paths traversed...</span> + 736 <span class="c">#</span> + 737 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 738 <span class="c"># completing the cycle.</span> + 739 <span class="c">#</span> +<a name="_PerformPathsSearchWithLength-"></a> 740 <span class="k">sub </span><span class="m">_PerformPathsSearchWithLength</span> <span class="s">{</span> + 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> + 742 + 743 <span class="c"># Make sure both start vertex and length are defined...</span> + 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> + 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> + 746 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 747 <span class="s">}</span> + 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> + 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> + 750 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 751 <span class="s">}</span> + 752 + 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> + 754 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> + 755 <span class="s">}</span> + 756 + 757 <span class="c"># Make sure both start vertex and length are valid...</span> + 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> + 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> + 760 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 761 <span class="s">}</span> + 762 + 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> + 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> + 765 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 766 <span class="s">}</span> + 767 + 768 <span class="c"># Perform paths search...</span> + 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> + 770 <span class="s">}</span> + 771 + 772 <span class="c"># Search all paths starting from a specified vertex with sharing of edges in paths traversed...</span> + 773 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 774 <span class="c"># completing the cycle.</span> + 775 <span class="c">#</span> +<a name="PerformAllPathsSearch-"></a> 776 <span class="k">sub </span><span class="m">PerformAllPathsSearch</span> <span class="s">{</span> + 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> + 778 + 779 <span class="c"># Make sure start vertex is defined...</span> + 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> + 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> + 782 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 783 <span class="s">}</span> + 784 + 785 <span class="c"># Make sure start vertex is valid...</span> + 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> + 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> + 788 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 789 <span class="s">}</span> + 790 + 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> + 792 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> + 793 <span class="s">}</span> + 794 + 795 <span class="c"># Perform paths search...</span> + 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> + 797 <span class="s">}</span> + 798 + 799 <span class="c"># Search all paths starting from a specified vertex with length upto a specified length with sharing of</span> + 800 <span class="c"># edges in paths traversed.</span> + 801 <span class="c">#</span> + 802 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 803 <span class="c"># completing the cycle.</span> + 804 <span class="c">#</span> +<a name="PerformAllPathsSearchWithLengthUpto-"></a> 805 <span class="k">sub </span><span class="m">PerformAllPathsSearchWithLengthUpto</span> <span class="s">{</span> + 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> + 807 + 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> + 809 <span class="s">}</span> + 810 + 811 <span class="c"># Search all paths starting from a specified vertex with specified length with sharing of</span> + 812 <span class="c"># edges in paths traversed.</span> + 813 <span class="c">#</span> + 814 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 815 <span class="c"># completing the cycle.</span> + 816 <span class="c">#</span> +<a name="PerformAllPathsSearchWithLength-"></a> 817 <span class="k">sub </span><span class="m">PerformAllPathsSearchWithLength</span> <span class="s">{</span> + 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> + 819 + 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> + 821 <span class="s">}</span> + 822 + 823 <span class="c"># Search all paths starting from a specified vertex with length upto a specified length with sharing of</span> + 824 <span class="c"># edges in paths traversed.</span> + 825 <span class="c">#</span> + 826 <span class="c"># By default, cycles are included in paths. A path containing a cycle is terminated at a vertex</span> + 827 <span class="c"># completing the cycle.</span> + 828 <span class="c">#</span> +<a name="_PerformAllPathsSearchWithLength-"></a> 829 <span class="k">sub </span><span class="m">_PerformAllPathsSearchWithLength</span> <span class="s">{</span> + 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> + 831 + 832 <span class="c"># Make sure both start vertex and length are defined...</span> + 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> + 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> + 835 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 836 <span class="s">}</span> + 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> + 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> + 839 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 840 <span class="s">}</span> + 841 + 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> + 843 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> + 844 <span class="s">}</span> + 845 + 846 <span class="c"># Make sure both start vertex and length are valid...</span> + 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> + 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> + 849 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 850 <span class="s">}</span> + 851 + 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> + 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> + 854 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 855 <span class="s">}</span> + 856 + 857 <span class="c"># Perform paths search...</span> + 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> + 859 <span class="s">}</span> + 860 + 861 <span class="c"># Search paths between two vertices...</span> + 862 <span class="c">#</span> +<a name="PerformPathsSearchBetween-"></a> 863 <span class="k">sub </span><span class="m">PerformPathsSearchBetween</span> <span class="s">{</span> + 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> + 865 + 866 <span class="c"># Make sure start and end vertices are defined...</span> + 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> + 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> + 869 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 870 <span class="s">}</span> + 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> + 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> + 873 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 874 <span class="s">}</span> + 875 <span class="c"># Make sure start and end vertices are valid...</span> + 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> + 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> + 878 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 879 <span class="s">}</span> + 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> + 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> + 882 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> + 883 <span class="s">}</span> + 884 + 885 <span class="c"># Perform paths search...</span> + 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> + 887 <span class="s">}</span> + 888 + 889 <span class="c"># Search paths starting from root vertex with no sharing of edges...</span> + 890 <span class="c">#</span> + 891 <span class="c"># Notes:</span> + 892 <span class="c"># . Possible paths searche modes are: DFSPathsWithLimit, DFSPaths. And each</span> + 893 <span class="c"># of these modes supports any combination of two options: CommonEdges, Cycles.</span> + 894 <span class="c"># Default for CommonEdges - No; Cycles - No.</span> + 895 <span class="c">#</span> +<a name="_PerformPathsSearch-"></a> 896 <span class="k">sub </span><span class="m">_PerformPathsSearch</span> <span class="s">{</span> + 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> + 898 + 899 <span class="c"># Perform DFS path search...</span> + 900 + 901 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'Path'</span><span class="sc">;</span> + 902 + 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> + 904 <span class="k">my</span><span class="s">(</span><span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> + 905 + 906 <span class="i">$DepthLimit</span> = <span class="i">$Length</span> - <span class="n">1</span><span class="sc">;</span> + 907 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFSWithLimit'</span><span class="sc">;</span> + 908 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> + 909 <span class="s">}</span> + 910 <span class="k">else</span> <span class="s">{</span> + 911 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFS'</span><span class="sc">;</span> + 912 <span class="s">}</span> + 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> + 914 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> + 915 <span class="s">}</span> + 916 + 917 <span class="i">$This</span>->{<span class="w">AllowPathCycles</span>} = <span class="i">$AllowCycles</span><span class="sc">;</span> + 918 + 919 <span class="c"># Perform search...</span> + 920 <span class="i">$This</span><span class="i">->_TraverseGraph</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 921 + 922 <span class="c"># Make sure traversal did get the root vertex...</span> + 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> + 924 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 925 <span class="s">}</span> + 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> + 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> + 928 <span class="s">}</span> + 929 <span class="k">else</span> <span class="s">{</span> + 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> + 931 <span class="s">}</span> + 932 + 933 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 934 <span class="s">}</span> + 935 + 936 <span class="c"># Search all paths starting from root vertex with sharing of edges...</span> + 937 <span class="c">#</span> +<a name="_PerformAllPathsSearch-"></a> 938 <span class="k">sub </span><span class="m">_PerformAllPathsSearch</span> <span class="s">{</span> + 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> + 940 + 941 <span class="c"># Perform DFS path search...</span> + 942 + 943 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'AllPaths'</span><span class="sc">;</span> + 944 + 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> + 946 <span class="k">my</span><span class="s">(</span><span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> + 947 + 948 <span class="i">$DepthLimit</span> = <span class="i">$Length</span> - <span class="n">1</span><span class="sc">;</span> + 949 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFSWithLimit'</span><span class="sc">;</span> + 950 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> + 951 <span class="s">}</span> + 952 <span class="k">else</span> <span class="s">{</span> + 953 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="q">'DFS'</span><span class="sc">;</span> + 954 <span class="s">}</span> + 955 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> + 956 <span class="i">$This</span>->{<span class="w">AllowPathCycles</span>} = <span class="i">$AllowCycles</span><span class="sc">;</span> + 957 + 958 <span class="c"># Traverse all paths search using DFS search...</span> + 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> + 960 + 961 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 962 <span class="s">}</span> + 963 + 964 <span class="c"># Travese all paths in graph starting from a specified root vertex...</span> + 965 <span class="c">#</span> +<a name="_TraverseAllPathsInGraph-"></a> 966 <span class="k">sub </span><span class="m">_TraverseAllPathsInGraph</span> <span class="s">{</span> + 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> + 968 + 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> + 970 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 971 <span class="s">}</span> + 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> + 973 + 974 <span class="i">$CurrentVertexID</span> = <span class="i">$This</span>->{<span class="w">RootVertex</span>}<span class="sc">;</span> + 975 <span class="i">$PredecessorVertexID</span> = <span class="i">$CurrentVertexID</span><span class="sc">;</span> + 976 <span class="i">$CurrentDepth</span> = <span class="n">0</span><span class="sc">;</span> + 977 <span class="i">$CurrentPath</span> = <span class="q">"$CurrentVertexID"</span><span class="sc">;</span> + 978 + 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> + 980 + 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> + 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> + 983 <span class="s">}</span> + 984 <span class="k">else</span> <span class="s">{</span> + 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> + 986 <span class="s">}</span> + 987 + 988 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 989 <span class="s">}</span> + 990 + 991 <span class="c"># Traverse and collect all paths recuresively..</span> + 992 <span class="c">#</span> +<a name="_TraverseAllPaths-"></a> 993 <span class="k">sub </span><span class="m">_TraverseAllPaths</span> <span class="s">{</span> + 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> + 995 + 996 <span class="c"># Save path traversed for current vertex..</span> + 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> + 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> + 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> +1000 <span class="s">}</span> +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> +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> +1003 +1004 <span class="i">$CurrentDepth</span>++<span class="sc">;</span> +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> +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> +1007 <span class="c"># Nothing more to do...</span> +1008 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> +1009 <span class="s">}</span> +1010 <span class="s">}</span> +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> +1012 +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> +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> +1015 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> +1016 <span class="s">}</span> +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> +1018 <span class="c"># It's a cycle...</span> +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> +1020 <span class="i">$NewPath</span> = <span class="q">"${CurrentPath}-${NeighborVertexID}"</span><span class="sc">;</span> +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> +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> +1023 <span class="s">}</span> +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> +1025 <span class="s">}</span> +1026 <span class="k">next</span> <span class="j">NEIGHBOR</span><span class="sc">;</span> +1027 <span class="s">}</span> +1028 <span class="i">$NewPath</span> = <span class="q">"${CurrentPath}-${NeighborVertexID}"</span><span class="sc">;</span> +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> +1030 <span class="s">}</span> +1031 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> +1032 <span class="s">}</span> +1033 +1034 <span class="c"># Is vertex already in traversed path?</span> +1035 <span class="c">#</span> +<a name="_IsVertexInTraversedPath-"></a>1036 <span class="k">sub </span><span class="m">_IsVertexInTraversedPath</span> <span class="s">{</span> +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> +1038 +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> +1040 <span class="s">}</span> +1041 +1042 <span class="c"># Collect all paths traversed during Path TraversalMode and sort 'em in</span> +1043 <span class="c"># ascending order of lengths</span> +1044 <span class="c">#</span> +<a name="_CollectPathsTraversedDuringPathsSearch-"></a>1045 <span class="k">sub </span><span class="m">_CollectPathsTraversedDuringPathsSearch</span> <span class="s">{</span> +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> +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> +1048 +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> +1050 +1051 <span class="c"># Create path objects from path vertex strings...</span> +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> +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> +1054 <span class="s">}</span> +1055 +1056 <span class="c"># Sort paths in ascending order of lengths...</span> +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> +1058 +1059 <span class="k">return</span> <span class="i">@SortedPaths</span><span class="sc">;</span> +1060 <span class="s">}</span> +1061 +1062 <span class="c"># Collect paths traversed during Path TraversalMode with specific length...</span> +1063 <span class="c">#</span> +<a name="_CollectPathsTraversedDuringPathsSearchWithLength-"></a>1064 <span class="k">sub </span><span class="m">_CollectPathsTraversedDuringPathsSearchWithLength</span> <span class="s">{</span> +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> +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> +1067 +1068 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +1069 <span class="i">$Depth</span> = <span class="i">$Length</span> - <span class="n">1</span><span class="sc">;</span> +1070 +1071 <span class="c"># Create path objects from path vertex strings...</span> +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> +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> +1074 <span class="k">next</span> <span class="j">VERTEXID</span><span class="sc">;</span> +1075 <span class="s">}</span> +1076 <span class="c"># For vertices involved in cycles, the path might also contain some shorter paths. So check</span> +1077 <span class="c"># the lengths before its collection...</span> +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> +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> +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> +1081 <span class="k">next</span> <span class="j">PATHSTRING</span><span class="sc">;</span> +1082 <span class="s">}</span> +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> +1084 <span class="s">}</span> +1085 <span class="s">}</span> +1086 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> +1087 <span class="s">}</span> +1088 +1089 <span class="c"># Collect paths traversed during Vertex TraversalMode...</span> +1090 <span class="c">#</span> +<a name="_CollectPathsTraversedDuringVertexSearch-"></a>1091 <span class="k">sub </span><span class="m">_CollectPathsTraversedDuringVertexSearch</span> <span class="s">{</span> +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> +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> +1094 <span class="i">@Paths</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +1095 +1096 <span class="c"># Get vertices at specific depths...</span> +1097 <span class="i">@VerticesAtDepth</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +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> +1099 <span class="k">if</span> <span class="s">(</span>!<span class="i">@VerticesAtDepth</span><span class="s">)</span> <span class="s">{</span> +1100 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> +1101 <span class="s">}</span> +1102 +1103 <span class="c"># Make sure search found only one root vertex and it corresponds to</span> +1104 <span class="c"># what was specified...</span> +1105 <span class="i">$Depth</span> = <span class="n">0</span><span class="sc">;</span> +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> +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> +1108 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> +1109 <span class="s">}</span> +1110 +1111 <span class="c"># Setup root vertex at depth 0. And set its path...</span> +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> +1113 <span class="i">%PathAtVertex</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +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> +1115 +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> +1117 <span class="c"># Go over all vertices at current depth...</span> +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> +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> +1120 <span class="k">next</span> <span class="j">VERTEX</span><span class="sc">;</span> +1121 <span class="s">}</span> +1122 <span class="c"># Get vertices for current path...</span> +1123 <span class="i">@VertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +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> +1125 +1126 <span class="c"># Expand path to successor vertex found during traversal...</span> +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> +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> +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> +1130 <span class="i">$PathAtVertex</span>{<span class="i">$SuccessorVertexID</span>} = <span class="i">$Path</span><span class="sc">;</span> +1131 <span class="s">}</span> +1132 <span class="s">}</span> +1133 <span class="s">}</span> +1134 <span class="c"># Sort paths in ascending order of lengths...</span> +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> +1136 +1137 <span class="k">return</span> <span class="i">@Paths</span><span class="sc">;</span> +1138 <span class="s">}</span> +1139 +1140 <span class="c"># Collect vertices at specific depths. Depth values start from 0...</span> +1141 <span class="c">#</span> +<a name="_CollectVerticesAtSpecificDepths-"></a>1142 <span class="k">sub </span><span class="m">_CollectVerticesAtSpecificDepths</span> <span class="s">{</span> +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> +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> +1145 +1146 <span class="i">@VerticesAtDepth</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +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> +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> +1149 <span class="s">}</span> +1150 <span class="k">return</span> <span class="i">@VerticesAtDepth</span><span class="sc">;</span> +1151 <span class="s">}</span> +1152 +1153 <span class="c"># Collect vertices, along with their successors, at specific depths and return a list containing references to</span> +1154 <span class="c"># lists with first value corresponding to vertex ID and second value a reference to a list containing</span> +1155 <span class="c"># its successors.</span> +1156 <span class="c">#</span> +1157 <span class="c"># Depth values start from 0...</span> +1158 <span class="c">#</span> +<a name="_CollectVerticesWithSuccessorsAtSpecificDepths-"></a>1159 <span class="k">sub </span><span class="m">_CollectVerticesWithSuccessorsAtSpecificDepths</span> <span class="s">{</span> +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> +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> +1162 +1163 <span class="i">@VerticesWithSuccessorsAtDepth</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +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> +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> +1166 +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> +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> +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> +1170 <span class="s">}</span> +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> +1172 <span class="c"># Multiple entries for a vertex and its successors could be present at a specific depth...</span> +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> +1174 <span class="s">}</span> +1175 <span class="k">return</span> <span class="i">@VerticesWithSuccessorsAtDepth</span><span class="sc">;</span> +1176 <span class="s">}</span> +1177 +1178 <span class="c"># Search paths between two vertices...</span> +1179 <span class="c">#</span> +<a name="_PerformPathsSearchBetween-"></a>1180 <span class="k">sub </span><span class="m">_PerformPathsSearchBetween</span> <span class="s">{</span> +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> +1182 <span class="k">my</span><span class="s">(</span><span class="i">$DepthLimit</span><span class="s">)</span><span class="sc">;</span> +1183 +1184 <span class="c"># Perform a targeted DFS search...</span> +1185 <span class="i">$DepthLimit</span> = <span class="k">undef</span><span class="sc">;</span> +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> +1187 +1188 <span class="k">my</span><span class="s">(</span><span class="i">$Path</span><span class="s">)</span><span class="sc">;</span> +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> +1190 +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> +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> +1193 <span class="s">}</span> +1194 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> +1195 <span class="s">}</span> +1196 +1197 <span class="c"># Collect path between root and target vertex after the search...</span> +1198 <span class="c">#</span> +<a name="_CollectPathBetween-"></a>1199 <span class="k">sub </span><span class="m">_CollectPathBetween</span> <span class="s">{</span> +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> +1201 +1202 <span class="c"># Does a path from root to target vertex exist?</span> +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> +1204 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1205 <span class="s">}</span> +1206 +1207 <span class="c"># Add target vertex ID path vertices...</span> +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> +1209 <span class="i">@VertexIDs</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +1210 <span class="i">$VertexID</span> = <span class="i">$TargetVertexID</span><span class="sc">;</span> +1211 <span class="k">push</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> +1212 +1213 <span class="c"># Backtrack to root vertex ID...</span> +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> +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> +1216 <span class="k">push</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="sc">;</span> +1217 <span class="s">}</span> +1218 +1219 <span class="c"># Create path from target to root and reverse it...</span> +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> +1221 <span class="i">$Path</span><span class="i">->Reverse</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> +1222 +1223 <span class="k">return</span> <span class="i">$Path</span><span class="sc">;</span> +1224 <span class="s">}</span> +1225 +1226 <span class="c"># Search vertices around specified root vertex with in specific neighborhood radius...</span> +1227 <span class="c">#</span> +<a name="PerformNeighborhoodVerticesSearchWithRadiusUpto-"></a>1228 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearchWithRadiusUpto</span> <span class="s">{</span> +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> +1230 +1231 <span class="c"># Make sure both start vertex and radius are defined...</span> +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> +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> +1234 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1235 <span class="s">}</span> +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> +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> +1238 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1239 <span class="s">}</span> +1240 +1241 <span class="c"># Make sure both start vertex and length are valid...</span> +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> +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> +1244 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1245 <span class="s">}</span> +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> +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> +1248 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1249 <span class="s">}</span> +1250 +1251 <span class="c"># Perform vertices search...</span> +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> +1253 <span class="s">}</span> +1254 +1255 <span class="c"># Search vertices around specified root vertex...</span> +1256 <span class="c">#</span> +<a name="PerformNeighborhoodVerticesSearch-"></a>1257 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearch</span> <span class="s">{</span> +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> +1259 +1260 <span class="c"># Make sure start vertex is defined...</span> +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> +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> +1263 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1264 <span class="s">}</span> +1265 +1266 <span class="c"># Make sure start vertex is valid...</span> +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> +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> +1269 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1270 <span class="s">}</span> +1271 <span class="c"># Perform vertices search...</span> +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> +1273 <span class="s">}</span> +1274 +1275 <span class="c"># Search vertices around specified root vertex with in specific neighborhood radius along with</span> +1276 <span class="c"># identification of successors of each vertex found during the search...</span> +1277 <span class="c">#</span> +<a name="PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto-"></a>1278 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto</span> <span class="s">{</span> +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> +1280 +1281 <span class="c"># Make sure both start vertex and radius are defined...</span> +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> +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> +1284 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1285 <span class="s">}</span> +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> +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> +1288 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1289 <span class="s">}</span> +1290 +1291 <span class="c"># Make sure both start vertex and length are valid...</span> +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> +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> +1294 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1295 <span class="s">}</span> +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> +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> +1298 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1299 <span class="s">}</span> +1300 +1301 <span class="c"># Perform vertices search...</span> +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> +1303 <span class="s">}</span> +1304 +1305 <span class="c"># Search vertices around specified root vertex along with identification of</span> +1306 <span class="c"># successors of each vertex found during the search...</span> +1307 <span class="c">#</span> +<a name="PerformNeighborhoodVerticesSearchWithSuccessors-"></a>1308 <span class="k">sub </span><span class="m">PerformNeighborhoodVerticesSearchWithSuccessors</span> <span class="s">{</span> +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> +1310 +1311 <span class="c"># Make sure start vertex is defined...</span> +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> +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> +1314 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1315 <span class="s">}</span> +1316 +1317 <span class="c"># Make sure start vertex is valid...</span> +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> +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> +1320 <span class="k">return</span> <span class="k">undef</span><span class="sc">;</span> +1321 <span class="s">}</span> +1322 <span class="c"># Perform vertices search...</span> +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> +1324 <span class="s">}</span> +1325 +1326 <span class="c"># Search vertices at successive neighborhood radii levels...</span> +1327 <span class="c">#</span> +<a name="_PerformNeighborhoodVerticesSearch-"></a>1328 <span class="k">sub </span><span class="m">_PerformNeighborhoodVerticesSearch</span> <span class="s">{</span> +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> +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> +1331 +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> +1333 <span class="i">$AllowCycles</span> = <span class="k">undef</span><span class="sc">;</span> +1334 +1335 <span class="c"># Perform BFS search...</span> +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> +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> +1338 <span class="s">}</span> +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> +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> +1341 <span class="s">}</span> +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> +1343 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> +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> +1345 <span class="s">}</span> +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> +1347 <span class="i">$AllowCycles</span> = <span class="n">1</span><span class="sc">;</span> +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> +1349 <span class="s">}</span> +1350 +1351 <span class="c"># Make sure traversal did get the root vertex...</span> +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> +1353 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> +1354 <span class="s">}</span> +1355 +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> +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> +1358 <span class="s">}</span> +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> +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> +1361 <span class="s">}</span> +1362 +1363 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> +1364 <span class="s">}</span> +1365 +1366 <span class="c"># Perform appropriate vertex search...</span> +1367 <span class="c">#</span> +<a name="_PerformVertexNeighborhoodSearch-"></a>1368 <span class="k">sub </span><span class="m">_PerformVertexNeighborhoodSearch</span> <span class="s">{</span> +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> +1370 +1371 <span class="c"># Setup search...</span> +1372 <span class="i">$This</span>->{<span class="w">TraversalMode</span>} = <span class="q">'VertexNeighborhood'</span><span class="sc">;</span> +1373 <span class="i">$This</span>->{<span class="w">TraversalType</span>} = <span class="i">$SearchType</span><span class="sc">;</span> +1374 +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> +1376 <span class="i">$This</span>->{<span class="w">RootVertex</span>} = <span class="i">$RootVertexID</span><span class="sc">;</span> +1377 <span class="s">}</span> +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> +1379 <span class="i">$This</span>->{<span class="w">DepthLimit</span>} = <span class="i">$DepthLimit</span><span class="sc">;</span> +1380 <span class="s">}</span> +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> +1382 <span class="i">$This</span>->{<span class="w">AllowVertexCycles</span>} = <span class="i">$AllowCycles</span><span class="sc">;</span> +1383 <span class="s">}</span> +1384 +1385 <span class="c"># Perform search...</span> +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> +1387 <span class="s">}</span> +1388 +1389 <span class="c"># Get orderded list of vertices after DFS/BFS search...</span> +1390 <span class="c">#</span> +<a name="GetVertices-"></a>1391 <span class="k">sub </span><span class="m">GetVertices</span> <span class="s">{</span> +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> +1393 +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> +1395 <span class="s">}</span> +1396 +1397 <span class="c"># Get a hash list containing vertex and root vertex as key/value pair for all vertices</span> +1398 <span class="c"># ordered using DFS/BFS search available via GetVertices method...</span> +1399 <span class="c">#</span> +<a name="GetVerticesRoots-"></a>1400 <span class="k">sub </span><span class="m">GetVerticesRoots</span> <span class="s">{</span> +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> +1402 +1403 <span class="k">return</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesRoots</span>}}<span class="sc">;</span> +1404 <span class="s">}</span> +1405 +1406 <span class="c"># Get a list containing lists of vertices in connected components of graph after DFS/BFS</span> +1407 <span class="c"># search...</span> +1408 <span class="c">#</span> +1409 <span class="c"># Note:</span> +1410 <span class="c"># . List is sorted in descending order of number of vertices in each connected component.</span> +1411 <span class="c">#</span> +<a name="GetConnectedComponentsVertices-"></a>1412 <span class="k">sub </span><span class="m">GetConnectedComponentsVertices</span> <span class="s">{</span> +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> +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> +1415 +1416 <span class="i">@ConnectedVertices</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +1417 <span class="i">%VerticesAtRoot</span> = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> +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> +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> +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> +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> +1422 <span class="s">}</span> +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> +1424 <span class="s">}</span> +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> +1426 +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> +1428 <span class="s">}</span> +1429 +1430 <span class="c"># Get predecessor vertices...</span> +1431 <span class="c">#</span> +<a name="GetVerticesPredecessors-"></a>1432 <span class="k">sub </span><span class="m">GetVerticesPredecessors</span> <span class="s">{</span> +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> +1434 +1435 <span class="k">return</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesPredecessors</span>}}<span class="sc">;</span> +1436 <span class="s">}</span> +1437 +1438 <span class="c"># Get a hash list containing vertex and depth from root vertex as key/value pair for all vertices</span> +1439 <span class="c"># ordered using DFS/BFS search available via GetVertices method...</span> +1440 <span class="c">#</span> +<a name="GetVerticesDepth-"></a>1441 <span class="k">sub </span><span class="m">GetVerticesDepth</span> <span class="s">{</span> +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> +1443 +1444 <span class="k">return</span> <span class="i">%</span>{<span class="i">$This</span>->{<span class="w">VerticesDepth</span>}}<span class="sc">;</span> +1445 <span class="s">}</span> +1446 +1447 <span class="c"># Get paths found during paths search...</span> +1448 <span class="c">#</span> +<a name="GetPaths-"></a>1449 <span class="k">sub </span><span class="m">GetPaths</span> <span class="s">{</span> +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> +1451 +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> +1453 <span class="s">}</span> +1454 +1455 <span class="c"># Get vertices collected at various neighborhood radii...</span> +1456 <span class="c">#</span> +<a name="GetVerticesNeighborhoods-"></a>1457 <span class="k">sub </span><span class="m">GetVerticesNeighborhoods</span> <span class="s">{</span> +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> +1459 +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> +1461 <span class="s">}</span> +1462 +1463 <span class="c"># Get vertices, along with their successor vertices, collected at various neighborhood radii as</span> +1464 <span class="c"># a list containing references to lists with first value corresponding to vertex ID and second value</span> +1465 <span class="c"># a reference to a list containing its successors.</span> +1466 <span class="c">#</span> +<a name="GetVerticesNeighborhoodsWithSuccessors-"></a>1467 <span class="k">sub </span><span class="m">GetVerticesNeighborhoodsWithSuccessors</span> <span class="s">{</span> +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> +1469 +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> +1471 <span class="s">}</span> +1472 +1473 <span class="c"># Return a string containg data for PathsTraversal object...</span> +<a name="StringifyPathsTraversal-"></a>1474 <span class="k">sub </span><span class="m">StringifyPathsTraversal</span> <span class="s">{</span> +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> +1476 <span class="k">my</span><span class="s">(</span><span class="i">$PathsTraversalString</span><span class="s">)</span><span class="sc">;</span> +1477 +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> +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> +1480 +1481 <span class="c"># Vertices ordered by traversal...</span> +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> +1483 +1484 <span class="c"># Stringify depths of vertices...</span> +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> +1486 +1487 <span class="c"># Stringify roots of vertices...</span> +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> +1489 +1490 <span class="c"># Stringify predecessor of vertices...</span> +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> +1492 +1493 <span class="c"># Stringify successor vertices...</span> +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> +1495 +1496 <span class="c"># Stringify paths...</span> +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> +1498 +1499 <span class="c"># Stringify vertices neighborhoods...</span> +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> +1501 +1502 <span class="c"># Stringify vertices neighborhoods with successors...</span> +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> +1504 +1505 <span class="k">return</span> <span class="i">$PathsTraversalString</span><span class="sc">;</span> +1506 <span class="s">}</span> +1507 +1508 <span class="c"># Stringify vertices depth...</span> +1509 <span class="c">#</span> +<a name="StringifyVerticesDepth-"></a>1510 <span class="k">sub </span><span class="m">StringifyVerticesDepth</span> <span class="s">{</span> +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> +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> +1513 +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> +1515 <span class="i">$DepthString</span> = <span class="q">"<Vertex-Depth>: None"</span><span class="sc">;</span> +1516 <span class="k">return</span> <span class="i">$DepthString</span><span class="sc">;</span> +1517 <span class="s">}</span> +1518 +1519 <span class="i">$DepthString</span> = <span class="q">"<Vertex-Depth>: "</span><span class="sc">;</span> +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> +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> +1522 <span class="i">$DepthString</span> .= <span class="q">" <$VertexID-$VertexDepth>"</span><span class="sc">;</span> +1523 <span class="s">}</span> +1524 <span class="k">return</span> <span class="i">$DepthString</span><span class="sc">;</span> +1525 <span class="s">}</span> +1526 +1527 <span class="c"># Stringify roots of vertices...</span> +1528 <span class="c">#</span> +<a name="StringifyVerticesRoots-"></a>1529 <span class="k">sub </span><span class="m">StringifyVerticesRoots</span> <span class="s">{</span> +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> +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> +1532 +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> +1534 <span class="i">$RootsString</span> = <span class="q">"<Vertex-RootVertex>: None"</span><span class="sc">;</span> +1535 <span class="k">return</span> <span class="i">$RootsString</span><span class="sc">;</span> +1536 <span class="s">}</span> +1537 +1538 <span class="i">$RootsString</span> = <span class="q">"<Vertex-RootVertex>: "</span><span class="sc">;</span> +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> +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> +1541 <span class="i">$RootsString</span> .= <span class="q">" <$VertexID-$RootVertexID>"</span><span class="sc">;</span> +1542 <span class="s">}</span> +1543 <span class="k">return</span> <span class="i">$RootsString</span><span class="sc">;</span> +1544 <span class="s">}</span> +1545 +1546 <span class="c"># Stringify predecessor of vertices...</span> +1547 <span class="c">#</span> +<a name="StringifyVerticesPredecessors-"></a>1548 <span class="k">sub </span><span class="m">StringifyVerticesPredecessors</span> <span class="s">{</span> +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> +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> +1551 +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> +1553 <span class="i">$PredecessorString</span> = <span class="q">"<Vertex-PredecessorVertex>: None"</span><span class="sc">;</span> +1554 <span class="k">return</span> <span class="i">$PredecessorString</span><span class="sc">;</span> +1555 <span class="s">}</span> +1556 +1557 <span class="i">$PredecessorString</span> = <span class="q">"<Vertex-PredecessorVertex>: "</span><span class="sc">;</span> +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> +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> +1560 <span class="i">$PredecessorString</span> .= <span class="q">" <$VertexID-$PredecessorVertexID>"</span><span class="sc">;</span> +1561 <span class="s">}</span> +1562 <span class="k">return</span> <span class="i">$PredecessorString</span><span class="sc">;</span> +1563 <span class="s">}</span> +1564 +1565 <span class="c"># Stringify successor vertices...</span> +1566 <span class="c">#</span> +<a name="StringifyVerticesSuccessors-"></a>1567 <span class="k">sub </span><span class="m">StringifyVerticesSuccessors</span> <span class="s">{</span> +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> +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> +1570 +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> +1572 <span class="i">$SuccessorString</span> = <span class="q">"<Vertex-VerticesSuccessorsList>: None"</span><span class="sc">;</span> +1573 <span class="k">return</span> <span class="i">$SuccessorString</span><span class="sc">;</span> +1574 <span class="s">}</span> +1575 +1576 <span class="i">$SuccessorString</span> = <span class="q">"<Vertex-VerticesSuccessorsList>: "</span><span class="sc">;</span> +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> +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> +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> +1580 <span class="s">}</span> +1581 <span class="k">else</span> <span class="s">{</span> +1582 <span class="i">$VerticesSuccessorsString</span> = <span class="q">"None"</span><span class="sc">;</span> +1583 <span class="s">}</span> +1584 <span class="i">$SuccessorString</span> .= <span class="q">" <$VertexID-$VerticesSuccessorsString>"</span><span class="sc">;</span> +1585 <span class="s">}</span> +1586 <span class="k">return</span> <span class="i">$SuccessorString</span><span class="sc">;</span> +1587 <span class="s">}</span> +1588 +1589 <span class="c"># Strinigify paths...</span> +1590 <span class="c">#</span> +<a name="StringifyPaths-"></a>1591 <span class="k">sub </span><span class="m">StringifyPaths</span> <span class="s">{</span> +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> +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> +1594 +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> +1596 <span class="i">$PathsString</span> = <span class="q">"Paths: None"</span><span class="sc">;</span> +1597 <span class="k">return</span> <span class="i">$PathsString</span><span class="sc">;</span> +1598 <span class="s">}</span> +1599 +1600 <span class="k">my</span><span class="s">(</span><span class="i">$FirstPath</span><span class="s">)</span><span class="sc">;</span> +1601 <span class="i">$PathsString</span> = <span class="q">"Paths: "</span><span class="sc">;</span> +1602 <span class="i">$FirstPath</span> = <span class="n">1</span><span class="sc">;</span> +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> +1604 <span class="k">if</span> <span class="s">(</span><span class="i">$FirstPath</span><span class="s">)</span> <span class="s">{</span> +1605 <span class="i">$FirstPath</span> = <span class="n">0</span><span class="sc">;</span> +1606 <span class="s">}</span> +1607 <span class="k">else</span> <span class="s">{</span> +1608 <span class="i">$PathsString</span> .= <span class="q">" "</span><span class="sc">;</span> +1609 <span class="s">}</span> +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> +1611 <span class="s">}</span> +1612 <span class="k">return</span> <span class="i">$PathsString</span><span class="sc">;</span> +1613 <span class="s">}</span> +1614 +1615 <span class="c"># Strinigify vertices neighborhoods...</span> +1616 <span class="c">#</span> +<a name="StringifyVerticesNeighborhoods-"></a>1617 <span class="k">sub </span><span class="m">StringifyVerticesNeighborhoods</span> <span class="s">{</span> +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> +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> +1620 +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> +1622 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVerticesList>: None"</span><span class="sc">;</span> +1623 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> +1624 <span class="s">}</span> +1625 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVerticesList>:"</span><span class="sc">;</span> +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> +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> +1628 <span class="i">$NeighborhoodsString</span> .= <span class="q">" <$Radius-$NeighborhoodVerticesString>"</span><span class="sc">;</span> +1629 <span class="s">}</span> +1630 +1631 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> +1632 <span class="s">}</span> +1633 +1634 <span class="c"># Strinigify vertices neighborhoods...</span> +1635 <span class="c">#</span> +<a name="StringifyVerticesNeighborhoodsWithSuccessors-"></a>1636 <span class="k">sub </span><span class="m">StringifyVerticesNeighborhoodsWithSuccessors</span> <span class="s">{</span> +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> +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> +1639 +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> +1641 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None"</span><span class="sc">;</span> +1642 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> +1643 <span class="s">}</span> +1644 <span class="i">$NeighborhoodsString</span> = <span class="q">"<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None"</span><span class="sc">;</span> +1645 +1646 <span class="i">$Radius</span> = <span class="n">0</span><span class="sc">;</span> +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> +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> +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> +1650 <span class="i">$NeighborhoodVertexSuccessorsString</span> = <span class="q">'None'</span><span class="sc">;</span> +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> +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> +1653 <span class="s">}</span> +1654 <span class="i">$NeighborhoodsString</span> .= <span class="q">" <$Radius-$VertexID-$NeighborhoodVertexSuccessorsString>"</span><span class="sc">;</span> +1655 <span class="s">}</span> +1656 <span class="i">$Radius</span>++<span class="sc">;</span> +1657 <span class="s">}</span> +1658 <span class="k">return</span> <span class="i">$NeighborhoodsString</span><span class="sc">;</span> +1659 <span class="s">}</span> +1660 +1661 <span class="c"># Return a reference to new paths traversal object...</span> +<a name="Copy-"></a>1662 <span class="k">sub </span><span class="m">Copy</span> <span class="s">{</span> +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> +1664 <span class="k">my</span><span class="s">(</span><span class="i">$NewPathsTraversal</span><span class="s">)</span><span class="sc">;</span> +1665 +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> +1667 +1668 <span class="k">return</span> <span class="i">$NewPathsTraversal</span><span class="sc">;</span> +1669 <span class="s">}</span> +1670 +<a name="EOF-"></a></pre> +<p> </p> +<br /> +<center> +<img src="../../../images/h2o2.png"> +</center> +</body> +</html>