Mercurial > repos > deepakjadmin > mayatool3_test3
diff mayachemtools/docs/modules/html/code/GraphMatrix.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/GraphMatrix.html Wed Jan 20 11:55:01 2016 -0500 @@ -0,0 +1,534 @@ +<html> +<head> +<title>MayaChemTools:Code:Graph::GraphMatrix.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::GraphMatrix-"></a> 1 <span class="k">package </span><span class="i">Graph::GraphMatrix</span><span class="sc">;</span> + 2 <span class="c">#</span> + 3 <span class="c"># $RCSfile: GraphMatrix.pm,v $</span> + 4 <span class="c"># $Date: 2015/02/28 20:49:06 $</span> + 5 <span class="c"># $Revision: 1.17 $</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">Matrix</span><span class="sc">;</span> + 34 <span class="k">use</span> <span class="w">Constants</span><span class="sc">;</span> + 35 + 36 <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> + 37 + 38 <span class="i">@ISA</span> = <span class="q">qw(Exporter)</span><span class="sc">;</span> + 39 <span class="i">@EXPORT</span> = <span class="q">qw()</span><span class="sc">;</span> + 40 <span class="i">@EXPORT_OK</span> = <span class="q">qw()</span><span class="sc">;</span> + 41 + 42 <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> + 43 + 44 <span class="c"># Setup class variables...</span> + 45 <span class="k">my</span><span class="s">(</span><span class="i">$ClassName</span><span class="s">)</span><span class="sc">;</span> + 46 <span class="i">_InitializeClass</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 47 + 48 <span class="c"># Overload Perl functions...</span> + 49 <span class="k">use</span> <span class="w">overload</span> <span class="q">'""'</span> <span class="cm">=></span> <span class="q">'StringifyGraphMatrix'</span><span class="sc">;</span> + 50 + 51 <span class="c"># Class constructor...</span> +<a name="new-"></a> 52 <span class="k">sub </span><span class="m">new</span> <span class="s">{</span> + 53 <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> + 54 + 55 <span class="c"># Initialize object...</span> + 56 <span class="k">my</span> <span class="i">$This</span> = <span class="s">{</span><span class="s">}</span><span class="sc">;</span> + 57 <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> + 58 <span class="i">$This</span><span class="i">->_InitializeGraphMatrix</span><span class="s">(</span><span class="i">$Graph</span><span class="s">)</span><span class="sc">;</span> + 59 + 60 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 61 <span class="s">}</span> + 62 + 63 <span class="c"># Initialize object data...</span> +<a name="_InitializeGraphMatrix-"></a> 64 <span class="k">sub </span><span class="m">_InitializeGraphMatrix</span> <span class="s">{</span> + 65 <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> + 66 + 67 <span class="c"># Specified graph object...</span> + 68 <span class="i">$This</span>->{<span class="w">Graph</span>} = <span class="i">$Graph</span><span class="sc">;</span> + 69 + 70 <span class="c"># Generated matrix...</span> + 71 <span class="i">$This</span>->{<span class="w">Matrix</span>} = <span class="k">undef</span><span class="sc">;</span> + 72 <span class="i">$This</span>->{<span class="w">MatrixType</span>} = <span class="k">undef</span><span class="sc">;</span> + 73 + 74 <span class="c"># Row and columns IDs...</span> + 75 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">RowIDs</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 76 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ColumnIDs</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 77 + 78 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 79 <span class="s">}</span> + 80 + 81 <span class="c"># Initialize class ...</span> +<a name="_InitializeClass-"></a> 82 <span class="k">sub </span><span class="m">_InitializeClass</span> <span class="s">{</span> + 83 <span class="c">#Class name...</span> + 84 <span class="i">$ClassName</span> = <span class="w">__PACKAGE__</span><span class="sc">;</span> + 85 <span class="s">}</span> + 86 + 87 <span class="c"># Generate the adjacency matrix for a simple graph.</span> + 88 <span class="c">#</span> + 89 <span class="c"># For a simple graph G with n vertices, the adjacency matrix for G is a n x n square matrix and</span> + 90 <span class="c"># its elements Mij are:</span> + 91 <span class="c">#</span> + 92 <span class="c"># . 0 if i == j</span> + 93 <span class="c"># . 1 if i != j and vertex Vi is adjacent to vertex Vj</span> + 94 <span class="c"># . 0 if i != j and vertex Vi is not adjacent to vertex Vj</span> + 95 <span class="c">#</span> +<a name="GenerateAdjacencyMatrix-"></a> 96 <span class="k">sub </span><span class="m">GenerateAdjacencyMatrix</span> <span class="s">{</span> + 97 <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> + 98 <span class="k">my</span><span class="s">(</span><span class="i">$Graph</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 99 + 100 <span class="c"># Get graph vertices...</span> + 101 <span class="i">$Graph</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="sc">;</span> + 102 <span class="i">@VertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 103 <span class="i">$NumOfVertices</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 104 + 105 <span class="k">if</span> <span class="s">(</span><span class="i">$NumOfVertices</span> == <span class="n">0</span><span class="s">)</span> <span class="s">{</span> + 106 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->GenerateAdjacencyMatrix: Specified graph doesn't contain any vertices: No matrix generated..."</span><span class="sc">;</span> + 107 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 108 <span class="s">}</span> + 109 + 110 <span class="c"># Create adjacency matrix...</span> + 111 <span class="k">my</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 112 + 113 <span class="i">$Matrix</span> = <span class="i">new</span> <span class="i">Matrix</span><span class="s">(</span><span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="s">)</span><span class="sc">;</span> + 114 <span class="i">$SkipIndexCheck</span> = <span class="n">1</span><span class="sc">;</span> + 115 + 116 <span class="k">for</span> <span class="i">$RowIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 117 <span class="i">$RowVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$RowIndex</span>]<span class="sc">;</span> + 118 <span class="k">for</span> <span class="i">$ColIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 119 <span class="i">$ColVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$ColIndex</span>]<span class="sc">;</span> + 120 <span class="i">$Value</span> = <span class="s">(</span><span class="i">$RowIndex</span> == <span class="i">$ColIndex</span><span class="s">)</span> ? <span class="n">0</span> <span class="co">:</span> <span class="s">(</span><span class="i">$Graph</span><span class="i">->HasEdge</span><span class="s">(</span><span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="s">)</span> ? <span class="n">1</span> <span class="co">:</span> <span class="n">0</span><span class="s">)</span><span class="sc">;</span> + 121 <span class="i">$Matrix</span><span class="i">->SetValue</span><span class="s">(</span><span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 122 <span class="s">}</span> + 123 <span class="s">}</span> + 124 <span class="i">$This</span><span class="i">->_SetMatrixAndAssociatedInformation</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="q">"AdjacencyMatrix"</span><span class="cm">,</span> \<span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 125 + 126 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 127 <span class="s">}</span> + 128 + 129 <span class="c"># Generate the Siedel adjacency matrix for a simple graph.</span> + 130 <span class="c">#</span> + 131 <span class="c"># For a simple graph G with n vertices, the Siedal adjacency matrix for G is a n x n square matrix and</span> + 132 <span class="c"># its elements Mij are:</span> + 133 <span class="c">#</span> + 134 <span class="c"># . 0 if i == j</span> + 135 <span class="c"># . -1 if i != j and vertex Vi is adjacent to vertex Vj</span> + 136 <span class="c"># . 1 if i != j and vertex Vi is not adjacent to vertex Vj</span> + 137 <span class="c">#</span> +<a name="GenerateSiedelAdjacencyMatrix-"></a> 138 <span class="k">sub </span><span class="m">GenerateSiedelAdjacencyMatrix</span> <span class="s">{</span> + 139 <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> + 140 <span class="k">my</span><span class="s">(</span><span class="i">$Graph</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 141 + 142 <span class="c"># Get graph vertices...</span> + 143 <span class="i">$Graph</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="sc">;</span> + 144 <span class="i">@VertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 145 <span class="i">$NumOfVertices</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 146 + 147 <span class="k">if</span> <span class="s">(</span><span class="i">$NumOfVertices</span> == <span class="n">0</span><span class="s">)</span> <span class="s">{</span> + 148 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->GenerateSiedelAdjacencyMatrix: Specified graph doesn't contain any vertices: No matrix generated..."</span><span class="sc">;</span> + 149 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 150 <span class="s">}</span> + 151 + 152 <span class="c"># Create Siedel adjacency matrix...</span> + 153 <span class="k">my</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 154 + 155 <span class="i">$Matrix</span> = <span class="i">new</span> <span class="i">Matrix</span><span class="s">(</span><span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="s">)</span><span class="sc">;</span> + 156 <span class="i">$SkipIndexCheck</span> = <span class="n">1</span><span class="sc">;</span> + 157 + 158 <span class="k">for</span> <span class="i">$RowIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 159 <span class="i">$RowVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$RowIndex</span>]<span class="sc">;</span> + 160 <span class="k">for</span> <span class="i">$ColIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 161 <span class="i">$ColVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$ColIndex</span>]<span class="sc">;</span> + 162 <span class="i">$Value</span> = <span class="s">(</span><span class="i">$RowIndex</span> == <span class="i">$ColIndex</span><span class="s">)</span> ? <span class="n">0</span> <span class="co">:</span> <span class="s">(</span><span class="i">$Graph</span><span class="i">->HasEdge</span><span class="s">(</span><span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="s">)</span> ? <span class="n">-1</span> <span class="co">:</span> <span class="n">1</span><span class="s">)</span><span class="sc">;</span> + 163 <span class="i">$Matrix</span><span class="i">->SetValue</span><span class="s">(</span><span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 164 <span class="s">}</span> + 165 <span class="s">}</span> + 166 <span class="i">$This</span><span class="i">->_SetMatrixAndAssociatedInformation</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="q">"SiedelAdjacencyMatrix"</span><span class="cm">,</span> \<span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 167 + 168 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 169 <span class="s">}</span> + 170 + 171 <span class="c"># Generate distance matrix for a simple graph using Floyd-Marshall algorithm [Ref 67].</span> + 172 <span class="c">#</span> + 173 <span class="c"># For a simple graph G with n vertices, the distance matrix for G is a n x n square matrix and</span> + 174 <span class="c"># its elements Mij are:</span> + 175 <span class="c">#</span> + 176 <span class="c"># . 0 if i == j</span> + 177 <span class="c"># . d if i != j and d is the shortest distance between vertex Vi and vertex Vj</span> + 178 <span class="c">#</span> + 179 <span class="c"># Note:</span> + 180 <span class="c"># . In the final matrix, BigNumber values correspond to vertices with no edges.</span> + 181 <span class="c">#</span> +<a name="GenerateDistanceMatrix-"></a> 182 <span class="k">sub </span><span class="m">GenerateDistanceMatrix</span> <span class="s">{</span> + 183 <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> + 184 <span class="k">my</span><span class="s">(</span><span class="i">$Graph</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 185 + 186 <span class="c"># Get graph vertices...</span> + 187 <span class="i">$Graph</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="sc">;</span> + 188 <span class="i">@VertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 189 <span class="i">$NumOfVertices</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 190 + 191 <span class="k">if</span> <span class="s">(</span><span class="i">$NumOfVertices</span> == <span class="n">0</span><span class="s">)</span> <span class="s">{</span> + 192 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->GenerateDistanceMatrix: Specified graph doesn't contain any vertices: No matrix generated..."</span><span class="sc">;</span> + 193 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 194 <span class="s">}</span> + 195 + 196 <span class="c"># Initialize matrix...</span> + 197 <span class="k">my</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$MatrixValuesRef</span><span class="cm">,</span> <span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="cm">,</span> <span class="i">$Value</span><span class="s">)</span><span class="sc">;</span> + 198 + 199 <span class="i">$Matrix</span> = <span class="i">new</span> <span class="i">Matrix</span><span class="s">(</span><span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="s">)</span><span class="sc">;</span> + 200 <span class="i">$MatrixValuesRef</span> = <span class="i">$Matrix</span><span class="i">->GetMatrixValuesReference</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 201 + 202 <span class="k">for</span> <span class="i">$RowIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 203 <span class="i">$RowVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$RowIndex</span>]<span class="sc">;</span> + 204 <span class="k">for</span> <span class="i">$ColIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 205 <span class="i">$ColVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$ColIndex</span>]<span class="sc">;</span> + 206 <span class="i">$Value</span> = <span class="s">(</span><span class="i">$RowIndex</span> == <span class="i">$ColIndex</span><span class="s">)</span> ? <span class="n">0</span> <span class="co">:</span> <span class="s">(</span><span class="i">$Graph</span><span class="i">->HasEdge</span><span class="s">(</span><span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="s">)</span> ? <span class="n">1</span> <span class="co">:</span> <span class="w">BigNumber</span><span class="s">)</span><span class="sc">;</span> + 207 <span class="i">$MatrixValuesRef</span>->[<span class="i">$RowIndex</span>][<span class="i">$ColIndex</span>] = <span class="i">$Value</span><span class="sc">;</span> + 208 <span class="s">}</span> + 209 <span class="s">}</span> + 210 + 211 <span class="c"># Create distance matrix...</span> + 212 <span class="k">my</span><span class="s">(</span><span class="i">$i</span><span class="cm">,</span> <span class="i">$j</span><span class="cm">,</span> <span class="i">$k</span><span class="cm">,</span> <span class="i">$Valuejk</span><span class="s">)</span><span class="sc">;</span> + 213 + 214 <span class="k">for</span> <span class="i">$i</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 215 <span class="k">for</span> <span class="i">$j</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 216 <span class="k">for</span> <span class="i">$k</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 217 <span class="i">$Valuejk</span> = <span class="i">$MatrixValuesRef</span>->[<span class="i">$j</span>][<span class="i">$i</span>] + <span class="i">$MatrixValuesRef</span>->[<span class="i">$i</span>][<span class="i">$k</span>]<span class="sc">;</span> + 218 <span class="k">if</span> <span class="s">(</span><span class="i">$Valuejk</span> < <span class="i">$MatrixValuesRef</span>->[<span class="i">$j</span>][<span class="i">$k</span>]<span class="s">)</span> <span class="s">{</span> + 219 <span class="i">$MatrixValuesRef</span>->[<span class="i">$j</span>][<span class="i">$k</span>] = <span class="i">$Valuejk</span><span class="sc">;</span> + 220 <span class="s">}</span> + 221 <span class="s">}</span> + 222 <span class="s">}</span> + 223 <span class="s">}</span> + 224 <span class="i">$This</span><span class="i">->_SetMatrixAndAssociatedInformation</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="q">"DistanceMatrix"</span><span class="cm">,</span> \<span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 225 + 226 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 227 <span class="s">}</span> + 228 + 229 <span class="c"># Generate the incidence matrix for a simple graph.</span> + 230 <span class="c">#</span> + 231 <span class="c"># For a simple graph G with n vertices and e edges, the incidence matrix for G is a n x e matrix</span> + 232 <span class="c"># its elements Mij are:</span> + 233 <span class="c">#</span> + 234 <span class="c"># . 1 if vertex Vi and the edge Ej are incident; in other words, Vi and Ej are related</span> + 235 <span class="c"># . 0 otherwise</span> + 236 <span class="c">#</span> +<a name="GenerateIncidenceMatrix-"></a> 237 <span class="k">sub </span><span class="m">GenerateIncidenceMatrix</span> <span class="s">{</span> + 238 <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> + 239 <span class="k">my</span><span class="s">(</span><span class="i">$Graph</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfEdges</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="cm">,</span> <span class="i">@EdgeVertexIDs</span><span class="s">)</span><span class="sc">;</span> + 240 + 241 <span class="c"># Get graph vertices and edges...</span> + 242 <span class="i">$Graph</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="sc">;</span> + 243 <span class="i">@VertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 244 <span class="i">$NumOfVertices</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 245 + 246 <span class="i">@EdgeVertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetEdges</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 247 <span class="i">$NumOfEdges</span> = <span class="i">@EdgeVertexIDs</span>/<span class="n">2</span><span class="sc">;</span> + 248 + 249 <span class="k">if</span> <span class="s">(</span><span class="i">$NumOfVertices</span> == <span class="n">0</span><span class="s">)</span> <span class="s">{</span> + 250 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->GenerateIncidenceMatrix: Specified graph doesn't contain any vertices: No matrix generated..."</span><span class="sc">;</span> + 251 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 252 <span class="s">}</span> + 253 + 254 <span class="c"># Create incidence matrix...</span> + 255 <span class="k">my</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$EdgeVertexIndex</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$EdgeVertexID1</span><span class="cm">,</span> <span class="i">$EdgeVertexID2</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 256 + 257 <span class="i">$Matrix</span> = <span class="i">new</span> <span class="i">Matrix</span><span class="s">(</span><span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfEdges</span><span class="s">)</span><span class="sc">;</span> + 258 + 259 <span class="i">$SkipIndexCheck</span> = <span class="n">1</span><span class="sc">;</span> + 260 <span class="k">for</span> <span class="i">$RowIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 261 <span class="i">$VertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$RowIndex</span>]<span class="sc">;</span> + 262 <span class="i">$EdgeVertexIndex</span> = <span class="n">0</span><span class="sc">;</span> + 263 <span class="k">for</span> <span class="i">$ColIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfEdges</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 264 <span class="i">$EdgeVertexID1</span> = <span class="i">$EdgeVertexIDs</span>[<span class="i">$EdgeVertexIndex</span>]<span class="sc">;</span> <span class="i">$EdgeVertexIndex</span>++<span class="sc">;</span> + 265 <span class="i">$EdgeVertexID2</span> = <span class="i">$EdgeVertexIDs</span>[<span class="i">$EdgeVertexIndex</span>]<span class="sc">;</span> <span class="i">$EdgeVertexIndex</span>++<span class="sc">;</span> + 266 + 267 <span class="i">$Value</span> = <span class="s">(</span><span class="i">$VertexID</span> == <span class="i">$EdgeVertexID1</span> || <span class="i">$VertexID</span> == <span class="i">$EdgeVertexID2</span><span class="s">)</span> ? <span class="n">1</span> <span class="co">:</span> <span class="n">0</span><span class="sc">;</span> + 268 <span class="i">$Matrix</span><span class="i">->SetValue</span><span class="s">(</span><span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 269 <span class="s">}</span> + 270 <span class="s">}</span> + 271 <span class="i">$This</span><span class="i">->_SetMatrixAndAssociatedInformation</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="q">"IncidenceMatrix"</span><span class="cm">,</span> \<span class="i">@VertexIDs</span><span class="cm">,</span> \<span class="i">@EdgeVertexIDs</span><span class="s">)</span><span class="sc">;</span> + 272 + 273 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 274 <span class="s">}</span> + 275 + 276 <span class="c"># Generate the degree matrix for a simple graph.</span> + 277 <span class="c">#</span> + 278 <span class="c"># For a simple graph G with n vertices, the degree matrix for G is a n x n square matrix and</span> + 279 <span class="c"># its elements Mij are:</span> + 280 <span class="c">#</span> + 281 <span class="c"># . deg(Vi) if i == j and deg(Vi) is the degree of vertex Vi</span> + 282 <span class="c"># . 0 otherwise</span> + 283 <span class="c">#</span> +<a name="GenerateDegreeMatrix-"></a> 284 <span class="k">sub </span><span class="m">GenerateDegreeMatrix</span> <span class="s">{</span> + 285 <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> + 286 <span class="k">my</span><span class="s">(</span><span class="i">$Graph</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 287 + 288 <span class="c"># Get graph vertices...</span> + 289 <span class="i">$Graph</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="sc">;</span> + 290 <span class="i">@VertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 291 <span class="i">$NumOfVertices</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 292 + 293 <span class="k">if</span> <span class="s">(</span><span class="i">$NumOfVertices</span> == <span class="n">0</span><span class="s">)</span> <span class="s">{</span> + 294 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->GenerateDegreeMatrix: Specified graph doesn't contain any vertices: No matrix generated..."</span><span class="sc">;</span> + 295 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 296 <span class="s">}</span> + 297 + 298 <span class="c"># Create degree matrix...</span> + 299 <span class="k">my</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$Index</span><span class="cm">,</span> <span class="i">$VertexID</span><span class="cm">,</span> <span class="i">$Degree</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 300 + 301 <span class="i">$Matrix</span> = <span class="i">new</span> <span class="i">Matrix</span><span class="s">(</span><span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="s">)</span><span class="sc">;</span> + 302 <span class="i">$SkipIndexCheck</span> = <span class="n">1</span><span class="sc">;</span> + 303 + 304 <span class="k">for</span> <span class="i">$Index</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 305 <span class="i">$VertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$Index</span>]<span class="sc">;</span> + 306 <span class="i">$Degree</span> = <span class="i">$Graph</span><span class="i">->GetDegree</span><span class="s">(</span><span class="i">$VertexID</span><span class="s">)</span><span class="sc">;</span> + 307 <span class="i">$Matrix</span><span class="i">->SetValue</span><span class="s">(</span><span class="i">$Index</span><span class="cm">,</span> <span class="i">$Index</span><span class="cm">,</span> <span class="i">$Degree</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 308 <span class="s">}</span> + 309 <span class="i">$This</span><span class="i">->_SetMatrixAndAssociatedInformation</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="q">"DegreeMatrix"</span><span class="cm">,</span> \<span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 310 + 311 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 312 <span class="s">}</span> + 313 + 314 <span class="c"># Generate the Laplacian matrix for a simple graph.</span> + 315 <span class="c">#</span> + 316 <span class="c"># For a simple graph G with n vertices, the Laplacian matrix for G is a n x n square matrix and</span> + 317 <span class="c"># its elements Mij are:</span> + 318 <span class="c">#</span> + 319 <span class="c"># . deg(Vi) if i == j and deg(Vi) is the degree of vertex Vi</span> + 320 <span class="c"># . -1 if i != j and vertex Vi is adjacent to vertex Vj</span> + 321 <span class="c"># . 0 otherwise</span> + 322 <span class="c">#</span> + 323 <span class="c"># Note: The Laplacian matrix is the difference between the degree matrix and adjacency matrix.</span> + 324 <span class="c">#</span> +<a name="GenerateLaplacianMatrix-"></a> 325 <span class="k">sub </span><span class="m">GenerateLaplacianMatrix</span> <span class="s">{</span> + 326 <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> + 327 <span class="k">my</span><span class="s">(</span><span class="i">$Graph</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 328 + 329 <span class="c"># Get graph vertices...</span> + 330 <span class="i">$Graph</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="sc">;</span> + 331 <span class="i">@VertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 332 <span class="i">$NumOfVertices</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 333 + 334 <span class="k">if</span> <span class="s">(</span><span class="i">$NumOfVertices</span> == <span class="n">0</span><span class="s">)</span> <span class="s">{</span> + 335 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->GenerateLaplacianMatrix: Specified graph doesn't contain any vertices: No matrix generated..."</span><span class="sc">;</span> + 336 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 337 <span class="s">}</span> + 338 + 339 <span class="c"># Create adjacency matrix...</span> + 340 <span class="k">my</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 341 + 342 <span class="i">$Matrix</span> = <span class="i">new</span> <span class="i">Matrix</span><span class="s">(</span><span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="s">)</span><span class="sc">;</span> + 343 <span class="i">$SkipIndexCheck</span> = <span class="n">1</span><span class="sc">;</span> + 344 + 345 <span class="k">for</span> <span class="i">$RowIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 346 <span class="i">$RowVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$RowIndex</span>]<span class="sc">;</span> + 347 <span class="k">for</span> <span class="i">$ColIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 348 <span class="i">$ColVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$ColIndex</span>]<span class="sc">;</span> + 349 <span class="i">$Value</span> = <span class="s">(</span><span class="i">$RowIndex</span> == <span class="i">$ColIndex</span><span class="s">)</span> ? <span class="i">$Graph</span><span class="i">->GetDegree</span><span class="s">(</span><span class="i">$RowVertexID</span><span class="s">)</span> <span class="co">:</span> <span class="s">(</span><span class="i">$Graph</span><span class="i">->HasEdge</span><span class="s">(</span><span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="s">)</span> ? <span class="n">-1</span> <span class="co">:</span> <span class="n">0</span><span class="s">)</span><span class="sc">;</span> + 350 <span class="i">$Matrix</span><span class="i">->SetValue</span><span class="s">(</span><span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 351 <span class="s">}</span> + 352 <span class="s">}</span> + 353 <span class="i">$This</span><span class="i">->_SetMatrixAndAssociatedInformation</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="q">"LaplacianMatrix"</span><span class="cm">,</span> \<span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 354 + 355 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 356 <span class="s">}</span> + 357 + 358 <span class="c"># Generate the normalized Laplacian matrix for a simple graph.</span> + 359 <span class="c">#</span> + 360 <span class="c"># For a simple graph G with n vertices, the normalized Laplacian matrix L for G is a n x n square matrix and</span> + 361 <span class="c"># its elements Lij are:</span> + 362 <span class="c">#</span> + 363 <span class="c"># . 1 if i == j and deg(Vi) != 0</span> + 364 <span class="c"># . -1/SQRT(deg(Vi) * deg(Vj)) if i != j and vertex Vi is adjacent to vertex Vj</span> + 365 <span class="c"># . 0 otherwise</span> + 366 <span class="c">#</span> + 367 <span class="c">#</span> +<a name="GenerateNormalizedLaplacianMatrix-"></a> 368 <span class="k">sub </span><span class="m">GenerateNormalizedLaplacianMatrix</span> <span class="s">{</span> + 369 <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> + 370 <span class="k">my</span><span class="s">(</span><span class="i">$Graph</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 371 + 372 <span class="c"># Get graph vertices...</span> + 373 <span class="i">$Graph</span> = <span class="i">$This</span>->{<span class="w">Graph</span>}<span class="sc">;</span> + 374 <span class="i">@VertexIDs</span> = <span class="i">$Graph</span><span class="i">->GetVertices</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 375 <span class="i">$NumOfVertices</span> = <span class="k">scalar</span> <span class="i">@VertexIDs</span><span class="sc">;</span> + 376 + 377 <span class="k">if</span> <span class="s">(</span><span class="i">$NumOfVertices</span> == <span class="n">0</span><span class="s">)</span> <span class="s">{</span> + 378 <span class="w">carp</span> <span class="q">"Warning: ${ClassName}->GenerateNormalizedLaplacianMatrix: Specified graph doesn't contain any vertices: No matrix generated..."</span><span class="sc">;</span> + 379 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 380 <span class="s">}</span> + 381 + 382 <span class="c"># Create adjacency matrix...</span> + 383 <span class="k">my</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="cm">,</span> <span class="i">$RowVertexDegree</span><span class="cm">,</span> <span class="i">$ColVertexDegree</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 384 + 385 <span class="i">$Matrix</span> = <span class="i">new</span> <span class="i">Matrix</span><span class="s">(</span><span class="i">$NumOfVertices</span><span class="cm">,</span> <span class="i">$NumOfVertices</span><span class="s">)</span><span class="sc">;</span> + 386 <span class="i">$SkipIndexCheck</span> = <span class="n">1</span><span class="sc">;</span> + 387 + 388 <span class="k">for</span> <span class="i">$RowIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 389 <span class="i">$RowVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$RowIndex</span>]<span class="sc">;</span> + 390 <span class="i">$RowVertexDegree</span> = <span class="i">$Graph</span><span class="i">->GetDegree</span><span class="s">(</span><span class="i">$RowVertexID</span><span class="s">)</span><span class="sc">;</span> + 391 <span class="k">for</span> <span class="i">$ColIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfVertices</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 392 <span class="i">$ColVertexID</span> = <span class="i">$VertexIDs</span>[<span class="i">$ColIndex</span>]<span class="sc">;</span> + 393 <span class="i">$Value</span> = <span class="n">0</span><span class="sc">;</span> + 394 <span class="k">if</span> <span class="s">(</span><span class="i">$RowIndex</span> == <span class="i">$ColIndex</span><span class="s">)</span> <span class="s">{</span> + 395 <span class="i">$Value</span> = <span class="s">(</span><span class="i">$RowVertexDegree</span> == <span class="n">0</span><span class="s">)</span> ? <span class="n">0</span> <span class="co">:</span> <span class="n">1</span><span class="sc">;</span> + 396 <span class="s">}</span> + 397 <span class="k">else</span> <span class="s">{</span> + 398 <span class="i">$ColVertexDegree</span> = <span class="i">$Graph</span><span class="i">->GetDegree</span><span class="s">(</span><span class="i">$ColVertexID</span><span class="s">)</span><span class="sc">;</span> + 399 <span class="i">$Value</span> = <span class="i">$Graph</span><span class="i">->HasEdge</span><span class="s">(</span><span class="i">$RowVertexID</span><span class="cm">,</span> <span class="i">$ColVertexID</span><span class="s">)</span> ? <span class="s">(</span><span class="n">-1</span>/<span class="k">sqrt</span><span class="s">(</span><span class="i">$RowVertexDegree</span> * <span class="i">$ColVertexDegree</span><span class="s">)</span><span class="s">)</span> <span class="co">:</span> <span class="n">0</span><span class="sc">;</span> + 400 <span class="s">}</span> + 401 <span class="i">$Matrix</span><span class="i">->SetValue</span><span class="s">(</span><span class="i">$RowIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$Value</span><span class="cm">,</span> <span class="i">$SkipIndexCheck</span><span class="s">)</span><span class="sc">;</span> + 402 <span class="s">}</span> + 403 <span class="s">}</span> + 404 <span class="i">$This</span><span class="i">->_SetMatrixAndAssociatedInformation</span><span class="s">(</span><span class="i">$Matrix</span><span class="cm">,</span> <span class="q">"NormalizedLaplacianMatrix"</span><span class="cm">,</span> \<span class="i">@VertexIDs</span><span class="s">)</span><span class="sc">;</span> + 405 + 406 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 407 <span class="s">}</span> + 408 + 409 <span class="c"># Generate the admittance matrix for a simple graph.</span> + 410 <span class="c">#</span> +<a name="GenerateAdmittanceMatrix-"></a> 411 <span class="k">sub </span><span class="m">GenerateAdmittanceMatrix</span> <span class="s">{</span> + 412 <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> + 413 + 414 <span class="i">$This</span><span class="i">->GenerateLaplacianMatrix</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 415 <span class="i">$This</span>->{<span class="w">MatrixType</span>} = <span class="q">"AdmittanceMatrix"</span><span class="sc">;</span> + 416 + 417 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 418 <span class="s">}</span> + 419 + 420 <span class="c"># Generate the Kirchhoff matrix for a simple graph.</span> + 421 <span class="c">#</span> +<a name="GenerateKirchhoffMatrix-"></a> 422 <span class="k">sub </span><span class="m">GenerateKirchhoffMatrix</span> <span class="s">{</span> + 423 <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> + 424 + 425 <span class="i">$This</span><span class="i">->GenerateLaplacianMatrix</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 426 <span class="i">$This</span>->{<span class="w">MatrixType</span>} = <span class="q">"KirchhoffMatrix"</span><span class="sc">;</span> + 427 + 428 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 429 <span class="s">}</span> + 430 + 431 <span class="c"># Get generated matrix...</span> + 432 <span class="c">#</span> +<a name="GetMatrix-"></a> 433 <span class="k">sub </span><span class="m">GetMatrix</span> <span class="s">{</span> + 434 <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> + 435 + 436 <span class="k">return</span> <span class="i">$This</span>->{<span class="w">Matrix</span>}<span class="sc">;</span> + 437 <span class="s">}</span> + 438 + 439 <span class="c"># Get matrix type...</span> + 440 <span class="c">#</span> +<a name="GetMatrixType-"></a> 441 <span class="k">sub </span><span class="m">GetMatrixType</span> <span class="s">{</span> + 442 <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> + 443 + 444 <span class="k">return</span> <span class="i">$This</span>->{<span class="w">MatrixType</span>}<span class="sc">;</span> + 445 <span class="s">}</span> + 446 + 447 <span class="c"># Get row IDs...</span> + 448 <span class="c">#</span> +<a name="GetRowIDs-"></a> 449 <span class="k">sub </span><span class="m">GetRowIDs</span> <span class="s">{</span> + 450 <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> + 451 + 452 <span class="k">return</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">RowIDs</span>}}<span class="sc">;</span> + 453 <span class="s">}</span> + 454 + 455 <span class="c"># Get column IDs...</span> + 456 <span class="c">#</span> +<a name="GetColumnIDs-"></a> 457 <span class="k">sub </span><span class="m">GetColumnIDs</span> <span class="s">{</span> + 458 <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> + 459 + 460 <span class="k">return</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ColumnIDs</span>}}<span class="sc">;</span> + 461 <span class="s">}</span> + 462 + 463 + 464 <span class="c"># Setup matrix and other associated information...</span> + 465 <span class="c">#</span> +<a name="_SetMatrixAndAssociatedInformation-"></a> 466 <span class="k">sub </span><span class="m">_SetMatrixAndAssociatedInformation</span> <span class="s">{</span> + 467 <span class="k">my</span><span class="s">(</span><span class="i">$This</span><span class="cm">,</span> <span class="i">$Matrix</span><span class="cm">,</span> <span class="i">$MatrixType</span><span class="cm">,</span> <span class="i">$VertexIDsRef</span><span class="cm">,</span> <span class="i">$EdgeVertexIDsRef</span><span class="s">)</span> = <span class="i">@_</span><span class="sc">;</span> + 468 + 469 <span class="i">$This</span>->{<span class="w">Matrix</span>} = <span class="i">$Matrix</span><span class="sc">;</span> + 470 <span class="i">$This</span>->{<span class="w">MatrixType</span>} = <span class="i">$MatrixType</span><span class="sc">;</span> + 471 + 472 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">RowIDs</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 473 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ColumnIDs</span>}} = <span class="s">(</span><span class="s">)</span><span class="sc">;</span> + 474 + 475 <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">RowIDs</span>}} = <span class="i">@</span>{<span class="i">$VertexIDsRef</span>}<span class="sc">;</span> + 476 + 477 <span class="k">if</span> <span class="s">(</span><span class="i">$MatrixType</span> =~ <span class="q">/^IncidenceMatrix$/i</span><span class="s">)</span> <span class="s">{</span> + 478 <span class="c"># Setup column IDs using edge vertex IDs...</span> + 479 <span class="k">my</span><span class="s">(</span><span class="i">$NumOfEdges</span><span class="cm">,</span> <span class="i">$EdgeVertexIndex</span><span class="cm">,</span> <span class="i">$ColIndex</span><span class="cm">,</span> <span class="i">$EdgeVertexID1</span><span class="cm">,</span> <span class="i">$EdgeVertexID2</span><span class="cm">,</span> <span class="i">$EdgeID</span><span class="s">)</span><span class="sc">;</span> + 480 + 481 <span class="i">$NumOfEdges</span> = <span class="s">(</span><span class="k">scalar</span> <span class="i">@</span>{<span class="i">$EdgeVertexIDsRef</span>}<span class="s">)</span>/<span class="n">2</span><span class="sc">;</span> + 482 <span class="i">$EdgeVertexIndex</span> = <span class="n">0</span><span class="sc">;</span> + 483 + 484 <span class="k">for</span> <span class="i">$ColIndex</span> <span class="s">(</span><span class="n">0</span> .. <span class="s">(</span><span class="i">$NumOfEdges</span> - <span class="n">1</span><span class="s">)</span><span class="s">)</span> <span class="s">{</span> + 485 <span class="i">$EdgeVertexID1</span> = <span class="i">$EdgeVertexIDsRef</span>->[<span class="i">$EdgeVertexIndex</span>]<span class="sc">;</span> <span class="i">$EdgeVertexIndex</span>++<span class="sc">;</span> + 486 <span class="i">$EdgeVertexID2</span> = <span class="i">$EdgeVertexIDsRef</span>->[<span class="i">$EdgeVertexIndex</span>]<span class="sc">;</span> <span class="i">$EdgeVertexIndex</span>++<span class="sc">;</span> + 487 <span class="i">$EdgeID</span> = <span class="s">(</span><span class="i">$EdgeVertexID1</span> < <span class="i">$EdgeVertexID2</span><span class="s">)</span> ? <span class="q">"${EdgeVertexID1}-${EdgeVertexID2}"</span> <span class="co">:</span> <span class="q">"${EdgeVertexID2}-${EdgeVertexID1}"</span><span class="sc">;</span> + 488 + 489 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ColumnIDs</span>}}<span class="cm">,</span> <span class="i">$EdgeID</span><span class="sc">;</span> + 490 <span class="s">}</span> + 491 <span class="s">}</span> + 492 <span class="k">else</span> <span class="s">{</span> + 493 <span class="k">push</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ColumnIDs</span>}}<span class="cm">,</span> <span class="i">@</span>{<span class="i">$VertexIDsRef</span>}<span class="sc">;</span> + 494 <span class="s">}</span> + 495 <span class="k">return</span> <span class="i">$This</span><span class="sc">;</span> + 496 <span class="s">}</span> + 497 + 498 <span class="c"># Return a string containg data for GraphMatrix object...</span> +<a name="StringifyGraphMatrix-"></a> 499 <span class="k">sub </span><span class="m">StringifyGraphMatrix</span> <span class="s">{</span> + 500 <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> + 501 <span class="k">my</span><span class="s">(</span><span class="i">$GraphMatrixString</span><span class="cm">,</span> <span class="i">$RowIDs</span><span class="s">)</span><span class="sc">;</span> + 502 + 503 <span class="i">$GraphMatrixString</span> = <span class="q">"GraphMatrix:"</span><span class="sc">;</span> + 504 + 505 <span class="i">$GraphMatrixString</span> .= <span class="s">(</span><span class="k">defined</span> <span class="i">$This</span>->{<span class="w">MatrixType</span>}<span class="s">)</span> ? <span class="q">" MatrixType: $This->{MatrixType}"</span> <span class="co">:</span> <span class="q">"MatrixType: <Undefined>"</span><span class="sc">;</span> + 506 <span class="i">$GraphMatrixString</span> .= <span class="s">(</span><span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">RowIDs</span>}}<span class="s">)</span> ? <span class="q">"; RowIDs: @{$This->{RowIDs}}"</span> <span class="co">:</span> <span class="q">"; RowIDs: <Undefined>"</span><span class="sc">;</span> + 507 <span class="i">$GraphMatrixString</span> .= <span class="s">(</span><span class="k">scalar</span> <span class="i">@</span>{<span class="i">$This</span>->{<span class="w">ColumnIDs</span>}}<span class="s">)</span> ? <span class="q">"; ColumnIDs: @{$This->{ColumnIDs}}"</span> <span class="co">:</span> <span class="q">"; ColumnIDs: <Undefined>"</span><span class="sc">;</span> + 508 + 509 <span class="i">$GraphMatrixString</span> .= <span class="s">(</span><span class="k">defined</span> <span class="i">$This</span>->{<span class="w">Matrix</span>}<span class="s">)</span> ? <span class="q">"; Matrix: $This->{Matrix}"</span> <span class="co">:</span> <span class="q">"; Matrix: <Undefined>"</span><span class="sc">;</span> + 510 + 511 <span class="k">return</span> <span class="i">$GraphMatrixString</span><span class="sc">;</span> + 512 <span class="s">}</span> + 513 +<a name="EOF-"></a></pre> +<p> </p> +<br /> +<center> +<img src="../../../images/h2o2.png"> +</center> +</body> +</html>