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