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