       1 package Graph::GraphMatrix;
       2 #
       3 # File: GraphMatrix.pm
       4 # Author: Manish Sud <msud@san.rr.com>
       5 #
       6 # Copyright (C) 2018 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