MayaChemTools

   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