       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