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