annotate mayachemtools/lib/Graph/GraphMatrix.pm @ 5:9a001a14a022 draft

Deleted selected files
author deepakjadmin
date Thu, 15 Dec 2016 14:04:29 -0500
parents 73ae111cf86f
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
1 package Graph::GraphMatrix;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
2 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
3 # $RCSfile: GraphMatrix.pm,v $
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
4 # $Date: 2015/02/28 20:49:06 $
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
5 # $Revision: 1.17 $
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
6 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
7 # Author: Manish Sud <msud@san.rr.com>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
8 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
9 # Copyright (C) 2015 Manish Sud. All rights reserved.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
10 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
11 # This file is part of MayaChemTools.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
12 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
13 # MayaChemTools is free software; you can redistribute it and/or modify it under
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
14 # the terms of the GNU Lesser General Public License as published by the Free
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
15 # Software Foundation; either version 3 of the License, or (at your option) any
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
16 # later version.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
17 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
18 # MayaChemTools is distributed in the hope that it will be useful, but without
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
19 # any warranty; without even the implied warranty of merchantability of fitness
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
20 # for a particular purpose. See the GNU Lesser General Public License for more
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
21 # details.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
22 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
23 # You should have received a copy of the GNU Lesser General Public License
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
24 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
25 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
26 # Boston, MA, 02111-1307, USA.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
27 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
28
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
29 use strict;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
30 use Carp;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
31 use Exporter;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
32 use Graph;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
33 use Matrix;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
34 use Constants;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
35
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
36 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
37
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
38 @ISA = qw(Exporter);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
39 @EXPORT = qw();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
40 @EXPORT_OK = qw();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
41
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
42 %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
43
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
44 # Setup class variables...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
45 my($ClassName);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
46 _InitializeClass();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
47
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
48 # Overload Perl functions...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
49 use overload '""' => 'StringifyGraphMatrix';
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
50
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
51 # Class constructor...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
52 sub new {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
53 my($Class, $Graph) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
54
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
55 # Initialize object...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
56 my $This = {};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
57 bless $This, ref($Class) || $Class;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
58 $This->_InitializeGraphMatrix($Graph);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
59
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
60 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
61 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
62
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
63 # Initialize object data...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
64 sub _InitializeGraphMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
65 my($This, $Graph) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
66
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
67 # Specified graph object...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
68 $This->{Graph} = $Graph;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
69
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
70 # Generated matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
71 $This->{Matrix} = undef;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
72 $This->{MatrixType} = undef;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
73
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
74 # Row and columns IDs...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
75 @{$This->{RowIDs}} = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
76 @{$This->{ColumnIDs}} = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
77
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
78 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
79 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
80
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
81 # Initialize class ...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
82 sub _InitializeClass {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
83 #Class name...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
84 $ClassName = __PACKAGE__;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
85 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
86
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
87 # Generate the adjacency matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
88 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
89 # For a simple graph G with n vertices, the adjacency matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
90 # its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
91 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
92 # . 0 if i == j
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
93 # . 1 if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
94 # . 0 if i != j and vertex Vi is not adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
95 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
96 sub GenerateAdjacencyMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
97 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
98 my($Graph, $NumOfVertices, @VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
99
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
100 # Get graph vertices...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
101 $Graph = $This->{Graph};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
102 @VertexIDs = $Graph->GetVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
103 $NumOfVertices = scalar @VertexIDs;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
104
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
105 if ($NumOfVertices == 0) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
106 carp "Warning: ${ClassName}->GenerateAdjacencyMatrix: Specified graph doesn't contain any vertices: No matrix generated...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
107 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
108 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
109
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
110 # Create adjacency matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
111 my($Matrix, $RowIndex, $ColIndex, $RowVertexID, $ColVertexID, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
112
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
113 $Matrix = new Matrix($NumOfVertices, $NumOfVertices);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
114 $SkipIndexCheck = 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
115
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
116 for $RowIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
117 $RowVertexID = $VertexIDs[$RowIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
118 for $ColIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
119 $ColVertexID = $VertexIDs[$ColIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
120 $Value = ($RowIndex == $ColIndex) ? 0 : ($Graph->HasEdge($RowVertexID, $ColVertexID) ? 1 : 0);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
121 $Matrix->SetValue($RowIndex, $ColIndex, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
122 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
123 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
124 $This->_SetMatrixAndAssociatedInformation($Matrix, "AdjacencyMatrix", \@VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
125
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
126 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
127 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
128
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
129 # Generate the Siedel adjacency matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
130 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
131 # For a simple graph G with n vertices, the Siedal adjacency matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
132 # its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
133 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
134 # . 0 if i == j
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
135 # . -1 if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
136 # . 1 if i != j and vertex Vi is not adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
137 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
138 sub GenerateSiedelAdjacencyMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
139 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
140 my($Graph, $NumOfVertices, @VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
141
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
142 # Get graph vertices...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
143 $Graph = $This->{Graph};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
144 @VertexIDs = $Graph->GetVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
145 $NumOfVertices = scalar @VertexIDs;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
146
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
147 if ($NumOfVertices == 0) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
148 carp "Warning: ${ClassName}->GenerateSiedelAdjacencyMatrix: Specified graph doesn't contain any vertices: No matrix generated...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
149 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
150 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
151
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
152 # Create Siedel adjacency matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
153 my($Matrix, $RowIndex, $ColIndex, $RowVertexID, $ColVertexID, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
154
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
155 $Matrix = new Matrix($NumOfVertices, $NumOfVertices);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
156 $SkipIndexCheck = 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
157
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
158 for $RowIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
159 $RowVertexID = $VertexIDs[$RowIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
160 for $ColIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
161 $ColVertexID = $VertexIDs[$ColIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
162 $Value = ($RowIndex == $ColIndex) ? 0 : ($Graph->HasEdge($RowVertexID, $ColVertexID) ? -1 : 1);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
163 $Matrix->SetValue($RowIndex, $ColIndex, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
164 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
165 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
166 $This->_SetMatrixAndAssociatedInformation($Matrix, "SiedelAdjacencyMatrix", \@VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
167
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
168 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
169 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
170
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
171 # Generate distance matrix for a simple graph using Floyd-Marshall algorithm [Ref 67].
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
172 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
173 # For a simple graph G with n vertices, the distance matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
174 # its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
175 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
176 # . 0 if i == j
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
177 # . d if i != j and d is the shortest distance between vertex Vi and vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
178 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
179 # Note:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
180 # . In the final matrix, BigNumber values correspond to vertices with no edges.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
181 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
182 sub GenerateDistanceMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
183 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
184 my($Graph, $NumOfVertices, @VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
185
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
186 # Get graph vertices...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
187 $Graph = $This->{Graph};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
188 @VertexIDs = $Graph->GetVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
189 $NumOfVertices = scalar @VertexIDs;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
190
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
191 if ($NumOfVertices == 0) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
192 carp "Warning: ${ClassName}->GenerateDistanceMatrix: Specified graph doesn't contain any vertices: No matrix generated...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
193 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
194 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
195
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
196 # Initialize matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
197 my($Matrix, $MatrixValuesRef, $RowIndex, $ColIndex, $RowVertexID, $ColVertexID, $Value);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
198
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
199 $Matrix = new Matrix($NumOfVertices, $NumOfVertices);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
200 $MatrixValuesRef = $Matrix->GetMatrixValuesReference();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
201
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
202 for $RowIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
203 $RowVertexID = $VertexIDs[$RowIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
204 for $ColIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
205 $ColVertexID = $VertexIDs[$ColIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
206 $Value = ($RowIndex == $ColIndex) ? 0 : ($Graph->HasEdge($RowVertexID, $ColVertexID) ? 1 : BigNumber);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
207 $MatrixValuesRef->[$RowIndex][$ColIndex] = $Value;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
208 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
209 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
210
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
211 # Create distance matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
212 my($i, $j, $k, $Valuejk);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
213
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
214 for $i (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
215 for $j (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
216 for $k (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
217 $Valuejk = $MatrixValuesRef->[$j][$i] + $MatrixValuesRef->[$i][$k];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
218 if ($Valuejk < $MatrixValuesRef->[$j][$k]) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
219 $MatrixValuesRef->[$j][$k] = $Valuejk;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
220 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
221 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
222 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
223 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
224 $This->_SetMatrixAndAssociatedInformation($Matrix, "DistanceMatrix", \@VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
225
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
226 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
227 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
228
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
229 # Generate the incidence matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
230 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
231 # For a simple graph G with n vertices and e edges, the incidence matrix for G is a n x e matrix
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
232 # its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
233 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
234 # . 1 if vertex Vi and the edge Ej are incident; in other words, Vi and Ej are related
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
235 # . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
236 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
237 sub GenerateIncidenceMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
238 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
239 my($Graph, $NumOfVertices, $NumOfEdges, @VertexIDs, @EdgeVertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
240
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
241 # Get graph vertices and edges...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
242 $Graph = $This->{Graph};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
243 @VertexIDs = $Graph->GetVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
244 $NumOfVertices = scalar @VertexIDs;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
245
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
246 @EdgeVertexIDs = $Graph->GetEdges();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
247 $NumOfEdges = @EdgeVertexIDs/2;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
248
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
249 if ($NumOfVertices == 0) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
250 carp "Warning: ${ClassName}->GenerateIncidenceMatrix: Specified graph doesn't contain any vertices: No matrix generated...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
251 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
252 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
253
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
254 # Create incidence matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
255 my($Matrix, $RowIndex, $ColIndex, $EdgeVertexIndex, $VertexID, $EdgeVertexID1, $EdgeVertexID2, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
256
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
257 $Matrix = new Matrix($NumOfVertices, $NumOfEdges);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
258
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
259 $SkipIndexCheck = 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
260 for $RowIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
261 $VertexID = $VertexIDs[$RowIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
262 $EdgeVertexIndex = 0;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
263 for $ColIndex (0 .. ($NumOfEdges - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
264 $EdgeVertexID1 = $EdgeVertexIDs[$EdgeVertexIndex]; $EdgeVertexIndex++;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
265 $EdgeVertexID2 = $EdgeVertexIDs[$EdgeVertexIndex]; $EdgeVertexIndex++;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
266
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
267 $Value = ($VertexID == $EdgeVertexID1 || $VertexID == $EdgeVertexID2) ? 1 : 0;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
268 $Matrix->SetValue($RowIndex, $ColIndex, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
269 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
270 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
271 $This->_SetMatrixAndAssociatedInformation($Matrix, "IncidenceMatrix", \@VertexIDs, \@EdgeVertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
272
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
273 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
274 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
275
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
276 # Generate the degree matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
277 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
278 # For a simple graph G with n vertices, the degree matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
279 # its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
280 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
281 # . deg(Vi) if i == j and deg(Vi) is the degree of vertex Vi
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
282 # . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
283 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
284 sub GenerateDegreeMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
285 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
286 my($Graph, $NumOfVertices, @VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
287
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
288 # Get graph vertices...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
289 $Graph = $This->{Graph};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
290 @VertexIDs = $Graph->GetVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
291 $NumOfVertices = scalar @VertexIDs;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
292
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
293 if ($NumOfVertices == 0) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
294 carp "Warning: ${ClassName}->GenerateDegreeMatrix: Specified graph doesn't contain any vertices: No matrix generated...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
295 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
296 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
297
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
298 # Create degree matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
299 my($Matrix, $Index, $VertexID, $Degree, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
300
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
301 $Matrix = new Matrix($NumOfVertices, $NumOfVertices);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
302 $SkipIndexCheck = 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
303
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
304 for $Index (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
305 $VertexID = $VertexIDs[$Index];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
306 $Degree = $Graph->GetDegree($VertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
307 $Matrix->SetValue($Index, $Index, $Degree, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
308 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
309 $This->_SetMatrixAndAssociatedInformation($Matrix, "DegreeMatrix", \@VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
310
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
311 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
312 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
313
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
314 # Generate the Laplacian matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
315 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
316 # For a simple graph G with n vertices, the Laplacian matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
317 # its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
318 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
319 # . deg(Vi) if i == j and deg(Vi) is the degree of vertex Vi
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
320 # . -1 if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
321 # . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
322 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
323 # Note: The Laplacian matrix is the difference between the degree matrix and adjacency matrix.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
324 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
325 sub GenerateLaplacianMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
326 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
327 my($Graph, $NumOfVertices, @VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
328
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
329 # Get graph vertices...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
330 $Graph = $This->{Graph};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
331 @VertexIDs = $Graph->GetVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
332 $NumOfVertices = scalar @VertexIDs;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
333
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
334 if ($NumOfVertices == 0) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
335 carp "Warning: ${ClassName}->GenerateLaplacianMatrix: Specified graph doesn't contain any vertices: No matrix generated...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
336 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
337 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
338
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
339 # Create adjacency matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
340 my($Matrix, $RowIndex, $ColIndex, $RowVertexID, $ColVertexID, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
341
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
342 $Matrix = new Matrix($NumOfVertices, $NumOfVertices);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
343 $SkipIndexCheck = 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
344
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
345 for $RowIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
346 $RowVertexID = $VertexIDs[$RowIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
347 for $ColIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
348 $ColVertexID = $VertexIDs[$ColIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
349 $Value = ($RowIndex == $ColIndex) ? $Graph->GetDegree($RowVertexID) : ($Graph->HasEdge($RowVertexID, $ColVertexID) ? -1 : 0);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
350 $Matrix->SetValue($RowIndex, $ColIndex, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
351 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
352 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
353 $This->_SetMatrixAndAssociatedInformation($Matrix, "LaplacianMatrix", \@VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
354
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
355 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
356 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
357
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
358 # Generate the normalized Laplacian matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
359 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
360 # For a simple graph G with n vertices, the normalized Laplacian matrix L for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
361 # its elements Lij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
362 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
363 # . 1 if i == j and deg(Vi) != 0
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
364 # . -1/SQRT(deg(Vi) * deg(Vj)) if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
365 # . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
366 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
367 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
368 sub GenerateNormalizedLaplacianMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
369 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
370 my($Graph, $NumOfVertices, @VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
371
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
372 # Get graph vertices...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
373 $Graph = $This->{Graph};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
374 @VertexIDs = $Graph->GetVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
375 $NumOfVertices = scalar @VertexIDs;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
376
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
377 if ($NumOfVertices == 0) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
378 carp "Warning: ${ClassName}->GenerateNormalizedLaplacianMatrix: Specified graph doesn't contain any vertices: No matrix generated...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
379 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
380 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
381
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
382 # Create adjacency matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
383 my($Matrix, $RowIndex, $ColIndex, $RowVertexID, $ColVertexID, $RowVertexDegree, $ColVertexDegree, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
384
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
385 $Matrix = new Matrix($NumOfVertices, $NumOfVertices);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
386 $SkipIndexCheck = 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
387
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
388 for $RowIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
389 $RowVertexID = $VertexIDs[$RowIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
390 $RowVertexDegree = $Graph->GetDegree($RowVertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
391 for $ColIndex (0 .. ($NumOfVertices - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
392 $ColVertexID = $VertexIDs[$ColIndex];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
393 $Value = 0;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
394 if ($RowIndex == $ColIndex) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
395 $Value = ($RowVertexDegree == 0) ? 0 : 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
396 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
397 else {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
398 $ColVertexDegree = $Graph->GetDegree($ColVertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
399 $Value = $Graph->HasEdge($RowVertexID, $ColVertexID) ? (-1/sqrt($RowVertexDegree * $ColVertexDegree)) : 0;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
400 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
401 $Matrix->SetValue($RowIndex, $ColIndex, $Value, $SkipIndexCheck);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
402 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
403 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
404 $This->_SetMatrixAndAssociatedInformation($Matrix, "NormalizedLaplacianMatrix", \@VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
405
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
406 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
407 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
408
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
409 # Generate the admittance matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
410 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
411 sub GenerateAdmittanceMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
412 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
413
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
414 $This->GenerateLaplacianMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
415 $This->{MatrixType} = "AdmittanceMatrix";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
416
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
417 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
418 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
419
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
420 # Generate the Kirchhoff matrix for a simple graph.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
421 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
422 sub GenerateKirchhoffMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
423 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
424
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
425 $This->GenerateLaplacianMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
426 $This->{MatrixType} = "KirchhoffMatrix";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
427
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
428 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
429 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
430
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
431 # Get generated matrix...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
432 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
433 sub GetMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
434 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
435
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
436 return $This->{Matrix};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
437 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
438
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
439 # Get matrix type...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
440 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
441 sub GetMatrixType {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
442 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
443
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
444 return $This->{MatrixType};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
445 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
446
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
447 # Get row IDs...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
448 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
449 sub GetRowIDs {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
450 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
451
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
452 return @{$This->{RowIDs}};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
453 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
454
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
455 # Get column IDs...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
456 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
457 sub GetColumnIDs {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
458 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
459
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
460 return @{$This->{ColumnIDs}};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
461 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
462
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
463
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
464 # Setup matrix and other associated information...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
465 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
466 sub _SetMatrixAndAssociatedInformation {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
467 my($This, $Matrix, $MatrixType, $VertexIDsRef, $EdgeVertexIDsRef) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
468
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
469 $This->{Matrix} = $Matrix;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
470 $This->{MatrixType} = $MatrixType;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
471
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
472 @{$This->{RowIDs}} = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
473 @{$This->{ColumnIDs}} = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
474
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
475 @{$This->{RowIDs}} = @{$VertexIDsRef};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
476
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
477 if ($MatrixType =~ /^IncidenceMatrix$/i) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
478 # Setup column IDs using edge vertex IDs...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
479 my($NumOfEdges, $EdgeVertexIndex, $ColIndex, $EdgeVertexID1, $EdgeVertexID2, $EdgeID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
480
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
481 $NumOfEdges = (scalar @{$EdgeVertexIDsRef})/2;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
482 $EdgeVertexIndex = 0;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
483
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
484 for $ColIndex (0 .. ($NumOfEdges - 1)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
485 $EdgeVertexID1 = $EdgeVertexIDsRef->[$EdgeVertexIndex]; $EdgeVertexIndex++;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
486 $EdgeVertexID2 = $EdgeVertexIDsRef->[$EdgeVertexIndex]; $EdgeVertexIndex++;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
487 $EdgeID = ($EdgeVertexID1 < $EdgeVertexID2) ? "${EdgeVertexID1}-${EdgeVertexID2}" : "${EdgeVertexID2}-${EdgeVertexID1}";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
488
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
489 push @{$This->{ColumnIDs}}, $EdgeID;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
490 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
491 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
492 else {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
493 push @{$This->{ColumnIDs}}, @{$VertexIDsRef};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
494 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
495 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
496 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
497
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
498 # Return a string containg data for GraphMatrix object...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
499 sub StringifyGraphMatrix {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
500 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
501 my($GraphMatrixString, $RowIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
502
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
503 $GraphMatrixString = "GraphMatrix:";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
504
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
505 $GraphMatrixString .= (defined $This->{MatrixType}) ? " MatrixType: $This->{MatrixType}" : "MatrixType: <Undefined>";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
506 $GraphMatrixString .= (scalar @{$This->{RowIDs}}) ? "; RowIDs: @{$This->{RowIDs}}" : "; RowIDs: <Undefined>";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
507 $GraphMatrixString .= (scalar @{$This->{ColumnIDs}}) ? "; ColumnIDs: @{$This->{ColumnIDs}}" : "; ColumnIDs: <Undefined>";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
508
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
509 $GraphMatrixString .= (defined $This->{Matrix}) ? "; Matrix: $This->{Matrix}" : "; Matrix: <Undefined>";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
510
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
511 return $GraphMatrixString;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
512 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
513
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
514 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
515
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
516 __END__
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
517
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
518 =head1 NAME
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
519
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
520 GraphMatrix
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
521
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
522 =head1 SYNOPSIS
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
523
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
524 use Graph::GraphMatrix;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
525
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
526 use Graph::GraphMatrix qw(:all);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
527
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
528 =head1 DESCRIPTION
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
529
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
530 B<GraphMatrix> class provides the following methods:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
531
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
532 new, GenerateAdjacencyMatrix, GenerateAdmittanceMatrix, GenerateDegreeMatrix,
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
533 GenerateDistanceMatrix, GenerateIncidenceMatrix, GenerateKirchhoffMatrix,
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
534 GenerateLaplacianMatrix, GenerateNormalizedLaplacianMatrix,
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
535 GenerateSiedelAdjacencyMatrix, GetColumnIDs, GetMatrix, GetMatrixType, GetRowIDs,
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
536 StringifyGraphMatrix
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
537
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
538 =head2 METHODS
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
539
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
540 =over 4
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
541
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
542 =item B<new>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
543
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
544 $NewGraphMatrix = new Graph::GraphMatrix($Graph);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
545
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
546 Using specified I<Graph>, B<new> method creates a new B<GraphMatrix> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
547 newly created B<GraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
548
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
549 =item B<GenerateAdjacencyMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
550
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
551 $AdjacencyGraphMatrix = $GraphMatrix->GenerateAdjacencyMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
552
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
553 Generates a new I<AdjacencyGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
554 I<AdjacencyGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
555
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
556 For a simple graph G with n vertices, the adjacency matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
557 its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
558
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
559 . 0 if i == j
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
560 . 1 if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
561 . 0 if i != j and vertex Vi is not adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
562
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
563 =item B<GenerateAdmittanceMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
564
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
565 $AdmittanceGraphMatrix = $GraphMatrix->GenerateAdmittanceMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
566
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
567 Generates a new I<AdmittanceGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
568 I<AdmittanceGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
569
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
570 B<AdmittanceMatrix> is another name for B<LaplacianMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
571
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
572 =item B<GenerateDegreeMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
573
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
574 $DegreeGraphMatrix = $GraphMatrix->GenerateDegreeMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
575
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
576 Generates a new I<DegreeGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
577 I<DegreeGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
578
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
579 For a simple graph G with n vertices, the degree matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
580 its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
581
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
582 . deg(Vi) if i == j and deg(Vi) is the degree of vertex Vi
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
583 . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
584
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
585 =item B<GenerateDistanceMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
586
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
587 $DistanceGraphMatrix = $GraphMatrix->GenerateDistanceMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
588
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
589 Generates a new I<DistanceGraphMatrix> for specified B<Graph> using Floyd-Marshall
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
590 algorithm [Ref 67] and returns I<DistanceGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
591
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
592 For a simple graph G with n vertices, the distance matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
593 its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
594
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
595 . 0 if i == j
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
596 . d if i != j and d is the shortest distance between vertex Vi and vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
597
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
598 In the final matrix, value of constant B<BigNumber> defined in B<Constants.pm> module
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
599 corresponds to vertices with no edges.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
600
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
601 =item B<GenerateIncidenceMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
602
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
603 $IncidenceGraphMatrix = $GraphMatrix->GenerateIncidenceMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
604
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
605 Generates a new I<IncidenceGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
606 I<IncidenceGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
607
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
608 For a simple graph G with n vertices and e edges, the incidence matrix for G is a n x e matrix
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
609 its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
610
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
611 . 1 if vertex Vi and the edge Ej are incident; in other words, Vi and Ej are related
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
612 . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
613
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
614 =item B<GenerateKirchhoffMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
615
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
616 $KirchhoffGraphMatrix = $GraphMatrix->GenerateKirchhoffMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
617
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
618 Generates a new I<KirchhoffGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
619 I<KirchhoffGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
620
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
621 B<KirchhoffMatrix> is another name for B<LaplacianMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
622
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
623 =item B<GenerateLaplacianMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
624
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
625 $LaplacianGraphMatrix = $GraphMatrix->GenerateLaplacianMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
626
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
627 Generates a new I<LaplacianGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
628 I<LaplacianGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
629
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
630 For a simple graph G with n vertices, the Laplacian matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
631 its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
632
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
633 . deg(Vi) if i == j and deg(Vi) is the degree of vertex Vi
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
634 . -1 if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
635 . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
636
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
637 The Laplacian matrix is the difference between the degree matrix and adjacency matrix.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
638
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
639 =item B<GenerateNormalizedLaplacianMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
640
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
641 $NormalizedLaplacianGraphMatrix = $GraphMatrix->GenerateNormalizedLaplacianMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
642
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
643 Generates a new I<NormalizedLaplacianGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
644 I<NormalizedLaplacianGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
645
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
646 For a simple graph G with n vertices, the normalized Laplacian matrix L for G is a n x n square
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
647 matrix and its elements Lij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
648
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
649 . 1 if i == j and deg(Vi) != 0
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
650 . -1/SQRT(deg(Vi) * deg(Vj)) if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
651 . 0 otherwise
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
652
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
653 =item B<GenerateSiedelAdjacencyMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
654
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
655 $SiedelAdjacencyGraphMatrix = $GraphMatrix->GenerateSiedelAdjacencyMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
656
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
657 Generates a new I<SiedelAdjacencyGraphMatrix> for specified B<Graph> and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
658 I<SiedelAdjacencyGraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
659
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
660 For a simple graph G with n vertices, the Siedal adjacency matrix for G is a n x n square matrix and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
661 its elements Mij are:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
662
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
663 . 0 if i == j
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
664 . -1 if i != j and vertex Vi is adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
665 . 1 if i != j and vertex Vi is not adjacent to vertex Vj
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
666
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
667 =item B<GetColumnIDs>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
668
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
669 @ColumnIDs = $GraphMatrix->GetColumnIDs();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
670
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
671 Returns an array containing any specified column IDs for I<GraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
672
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
673 =item B<GetMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
674
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
675 $Matrix = $GraphMatrix->GetMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
676
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
677 Returns I<Matrix> object corresponding to I<GraphMatrix> object.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
678
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
679 =item B<GetMatrixType>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
680
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
681 $MatrixType = $GraphMatrix->GetMatrixType();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
682
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
683 Returns B<MatrixType> of I<GraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
684
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
685 =item B<GetRowIDs>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
686
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
687 @RowIDs = $GraphMatrix->GetRowIDs();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
688
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
689 Returns an array containing any specified rowIDs IDs for I<GraphMatrix>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
690
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
691 =item B<StringifyGraphMatrix>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
692
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
693 $String = $GraphMatrix->StringifyGraphMatrix();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
694
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
695 Returns a string containing information about I<GraphMatrix> object.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
696
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
697 =back
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
698
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
699 =head1 AUTHOR
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
700
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
701 Manish Sud <msud@san.rr.com>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
702
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
703 =head1 SEE ALSO
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
704
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
705 Constants.pm, Graph.pm, Matrix.pm
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
706
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
707 =head1 COPYRIGHT
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
708
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
709 Copyright (C) 2015 Manish Sud. All rights reserved.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
710
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
711 This file is part of MayaChemTools.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
712
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
713 MayaChemTools is free software; you can redistribute it and/or modify it under
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
714 the terms of the GNU Lesser General Public License as published by the Free
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
715 Software Foundation; either version 3 of the License, or (at your option)
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
716 any later version.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
717
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
718 =cut