       1 package Graph;
       2 #
       3 # File: Graph.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 Storable ();
      30 use Scalar::Util ();
      31 use Graph::CyclesDetection;
      32 use Graph::PathsTraversal;
      33 use Graph::GraphMatrix;
      34
      35 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
      36
      37 @ISA = qw(Exporter);
      38 @EXPORT = qw(IsGraph);
      39 @EXPORT_OK = qw();
      40
      41 %EXPORT_TAGS = (all  => [@EXPORT, @EXPORT_OK]);
      42
      43 # Setup class variables...
      44 my($ClassName);
      45 _InitializeClass();
      46
      47 # Overload Perl functions...
      48 use overload '""' => 'StringifyGraph';
      49
      50 # Class constructor...
      51 sub new {
      52   my($Class, @VertexIDs) = @_;
      53
      54   # Initialize object...
      55   my $This = {};
      56   bless $This, ref($Class) || $Class;
      57   $This->_InitializeGraph();
      58
      59   if (@VertexIDs) { $This->AddVertices(@VertexIDs); }
      60
      61   return $This;
      62 }
      63
      64 # Initialize object data...
      65 sub _InitializeGraph {
      66   my($This) = @_;
      67
      68   %{$This->{Vertices}} = ();
      69
      70   %{$This->{Edges}} = ();
      71   %{$This->{Edges}->{From}} = ();
      72   %{$This->{Edges}->{To}} = ();
      73
      74   %{$This->{Properties}} = ();
      75   %{$This->{Properties}->{Graph}} = ();
      76   %{$This->{Properties}->{Vertices}} = ();
      77   %{$This->{Properties}->{Edges}} = ();
      78 }
      79
      80 # Initialize class ...
      81 sub _InitializeClass {
      82   #Class name...
      83   $ClassName = __PACKAGE__;
      84 }
      85
      86 # Add a vertex...
      87 sub AddVertex {
      88   my($This, $VertexID) = @_;
      89
      90   if (!defined $VertexID ) {
      91     carp "Warning: ${ClassName}->AddVertex: No vertex added: Vertex ID must be specified...";
      92     return undef;
      93   }
      94   if (exists $This->{Vertices}->{$VertexID}) {
      95     carp "Warning: ${ClassName}->AddVertex: Didn't add vertex $VertexID: Already exists in the graph...";
      96     return undef;
      97   }
      98
      99   $This->{Vertices}->{$VertexID} = $VertexID;
     100
     101   return $This;
     102 }
     103
     104 # Add vertices to the graph and return graph...
     105 sub AddVertices {
     106   my($This, @VertexIDs) = @_;
     107
     108   if (!@VertexIDs) {
     109     carp "Warning: ${ClassName}->AddVertices: No vertices added: Vertices list is empty...";
     110     return undef;
     111   }
     112
     113   my($VertexID);
     114   for $VertexID (@VertexIDs) {
     115     $This->AddVertex($VertexID);
     116   }
     117
     118   return $This;
     119 }
     120
     121 # Delete a vertex...
     122 sub DeleteVertex {
     123   my($This, $VertexID) = @_;
     124
     125   if (!defined $VertexID ) {
     126     carp "Warning: ${ClassName}->DeleteVertex: No vertex deleted: Vertex ID must be specified...";
     127     return undef;
     128   }
     129   if (!$This->HasVertex($VertexID)) {
     130     carp "Warning: ${ClassName}->DeleteVertex: Didn't delete vertex $VertexID: Vertex $VertexID doesn't exist...";
     131     return undef;
     132   }
     133   $This->_DeleteVertex($VertexID);
     134
     135   return $This;
     136 }
     137
     138 # Delete vertex...
     139 sub _DeleteVertex {
     140   my($This, $VertexID) = @_;
     141
     142   # Delete corresponding edges; the corresponding edge properties are deleted during
     143   # edges deletetion...
     144   my(@VertexIDs);
     145   @VertexIDs = $This->GetEdges($VertexID);
     146   if (@VertexIDs) {
     147     $This->DeleteEdges(@VertexIDs);
     148   }
     149
     150   # Delete the vertex and any properties associated with vertex...
     151   $This->DeleteVertexProperties($VertexID);
     152   delete $This->{Vertices}->{$VertexID};
     153 }
     154
     155 # Delete vertices...
     156 sub DeleteVertices {
     157   my($This, @VertexIDs) = @_;
     158
     159   if (!@VertexIDs) {
     160     carp "Warning: ${ClassName}->DeleteVertices: No vertices deleted: Vertices list is empty...";
     161     return undef;
     162   }
     163   my($VertexID);
     164   for $VertexID (@VertexIDs) {
     165     $This->DeleteVertex($VertexID);
     166   }
     167
     168   return $This;
     169 }
     170
     171 # Get vertex data...
     172 sub GetVertex {
     173   my($This, $VertexID) = @_;
     174
     175   if (!defined $VertexID) {
     176     return undef;
     177   }
     178
     179   return (exists $This->{Vertices}->{$VertexID}) ? $This->{Vertices}->{$VertexID} : undef;
     180 }
     181
     182 # Get data for all vertices or those specifed in the list. In scalar context, returned
     183 # the number of vertices found.
     184 #
     185 sub GetVertices {
     186   my($This, @VertexIDs) = @_;
     187   my($ValuesCount, @VertexValues);
     188
     189   @VertexValues = ();
     190   if (@VertexIDs) {
     191     @VertexValues = map { $This->GetVertex($_) } @VertexIDs;
     192     $ValuesCount = grep { 1 } @VertexValues;
     193   }
     194   else {
     195     @VertexValues = sort { $a <=> $b } keys %{$This->{Vertices}};
     196     $ValuesCount = @VertexValues;
     197   }
     198
     199   return wantarray ? @VertexValues : $ValuesCount;
     200 }
     201
     202 # Is this vertex present?
     203 sub HasVertex {
     204   my($This, $VertexID) = @_;
     205
     206   if (!defined $VertexID) {
     207     return 0;
     208   }
     209   return (exists $This->{Vertices}->{$VertexID}) ? 1 : 0;
     210 }
     211
     212 # Are these vertices present? Return an array containing 1 or 0  for each vertex.
     213 # In scalar context, return number of vertices found.
     214 sub HasVertices {
     215   my($This, @VertexIDs) = @_;
     216
     217   if (!@VertexIDs) {
     218     return undef;
     219   }
     220   my($VerticesCount, @VerticesStatus);
     221
     222   @VerticesStatus = map { $This->HasVertex($_) } @VertexIDs;
     223   $VerticesCount = grep { 1 }  @VerticesStatus;
     224
     225   return wantarray ? @VerticesStatus : $VerticesCount;
     226 }
     227
     228 # Add an edge...
     229 sub AddEdge {
     230   my($This, $VertexID1, $VertexID2) = @_;
     231
     232   if (!(defined($VertexID1) && defined($VertexID2))) {
     233     carp "Warning: ${ClassName}->AddEdge: No edge added: Both vertices must be defined...";
     234     return undef;
     235   }
     236   if (!$This->HasVertex($VertexID1)) {
     237     carp "Warning: ${ClassName}->AddEdge: Didn't add edge between vertices $VertexID1 and $VertexID2: Vertex $VertexID1 doesn's exist...";
     238     return undef;
     239   }
     240   if (!$This->HasVertex($VertexID2)) {
     241     carp "Warning: ${ClassName}->AddEdge: Didn't add edge between vertices $VertexID1 and $VertexID2: Vertex $VertexID2 doesn's exist...";
     242     return undef;
     243   }
     244   if ($VertexID1 == $VertexID2) {
     245     carp "Warning: ${ClassName}->AddEdge: Didn't add edge between vertices $VertexID1 and $VertexID2: Vertices must be different...";
     246     return undef;
     247   }
     248   if ($This->HasEdge($VertexID1, $VertexID2)) {
     249     carp "Warning: ${ClassName}->AddEdge: Didn't add edge between vertices $VertexID1 and $VertexID2: Edge already exists...";
     250     return undef;
     251   }
     252
     253   if (!exists $This->{Edges}->{From}->{$VertexID1}) {
     254     %{$This->{Edges}->{From}->{$VertexID1}} = ();
     255   }
     256   $This->{Edges}->{From}->{$VertexID1}->{$VertexID2} = $VertexID2;
     257
     258   if (!exists $This->{Edges}->{To}->{$VertexID2}) {
     259     %{$This->{Edges}->{To}->{$VertexID2}} = ();
     260   }
     261   $This->{Edges}->{To}->{$VertexID2}->{$VertexID1} = $VertexID1;
     262
     263   return $This;
     264 }
     265
     266 # Add edges...
     267 sub AddEdges {
     268   my($This, @VertexIDs) = @_;
     269
     270   if (!@VertexIDs) {
     271     carp "Warning: ${ClassName}->AddEdges: No edges added: Vertices list is empty...";
     272     return undef;
     273   }
     274   if (@VertexIDs % 2) {
     275     carp "Warning: ${ClassName}->AddEdges: No edges added: Invalid vertices data: Input list must contain even number of vertex IDs...";
     276     return undef;
     277   }
     278   my($VertexID1, $VertexID2, $Index);
     279   for ($Index = 0; $Index < $#VertexIDs; $Index += 2) {
     280     $VertexID1 = $VertexIDs[$Index]; $VertexID2 = $VertexIDs[$Index + 1];
     281     $This->AddEdge($VertexID1, $VertexID2);
     282   }
     283
     284   return $This;
     285 }
     286
     287 # Delete an edge...
     288 sub DeleteEdge {
     289   my($This, $VertexID1, $VertexID2) = @_;
     290
     291   if (!(defined($VertexID1) && defined($VertexID2))) {
     292     carp "Warning: ${ClassName}->Delete: No edge deleted: Both vertices must be defined...";
     293     return undef;
     294   }
     295   if (!$This->HasVertex($VertexID1)) {
     296     carp "Warning: ${ClassName}->DeleteEdge: Didn't delete edge between vertices $VertexID1 and $VertexID2: Vertex $VertexID1 doesn's exist...";
     297     return undef;
     298   }
     299   if (!$This->HasVertex($VertexID2)) {
     300     carp "Warning: ${ClassName}->DeleteEdge: Didn't delete edge between vertices $VertexID1 and $VertexID2: Vertex $VertexID2 doesn's exist...";
     301     return undef;
     302   }
     303   if (!$This->HasEdge($VertexID1, $VertexID2)) {
     304     carp "Warning: ${ClassName}->DeleteEdge: Didn't delete edge between vertices $VertexID1 and $VertexID2: Edge doesn't exist...";
     305     return undef;
     306   }
     307   $This->_DeleteEdge($VertexID1, $VertexID2);
     308   $This->_DeleteEdge($VertexID2, $VertexID1);
     309 }
     310
     311 # Delete edge...
     312 sub _DeleteEdge {
     313   my($This, $VertexID1, $VertexID2) = @_;
     314
     315   # Delete the edge...
     316   if (exists $This->{Edges}->{From}->{$VertexID1}) {
     317     if (exists $This->{Edges}->{From}->{$VertexID1}->{$VertexID2}) {
     318       delete $This->{Edges}->{From}->{$VertexID1}->{$VertexID2};
     319     }
     320     if (! keys %{$This->{Edges}->{From}->{$VertexID1}}) {
     321       delete $This->{Edges}->{From}->{$VertexID1};
     322     }
     323   }
     324
     325   if (exists $This->{Edges}->{To}->{$VertexID2}) {
     326     if (exists $This->{Edges}->{To}->{$VertexID2}->{$VertexID1}) {
     327       delete $This->{Edges}->{To}->{$VertexID2}->{$VertexID1};
     328     }
     329     if (! keys %{$This->{Edges}->{To}->{$VertexID2}}) {
     330       delete $This->{Edges}->{To}->{$VertexID2};
     331     }
     332   }
     333
     334   # Delete properties associated with the edge...
     335   $This->DeleteEdgeProperties($VertexID1, $VertexID2);
     336 }
     337
     338 # Delete edges...
     339 sub DeleteEdges {
     340   my($This, @VertexIDs) = @_;
     341
     342   if (!@VertexIDs) {
     343     carp "Warning: ${ClassName}->DeleteEdges: No edges deleted: Vertices list is empty...";
     344     return undef;
     345   }
     346   if (@VertexIDs % 2) {
     347     carp "Warning: ${ClassName}->DeleteEdges: No edges deleted: Invalid vertices data: Input list must contain even number of vertex IDs...";
     348     return undef;
     349   }
     350   my($VertexID1, $VertexID2, $Index);
     351   for ($Index = 0; $Index < $#VertexIDs; $Index += 2) {
     352     $VertexID1 = $VertexIDs[$Index]; $VertexID2 = $VertexIDs[$Index + 1];
     353     $This->DeleteEdge($VertexID1, $VertexID2);
     354   }
     355
     356   return $This;
     357 }
     358
     359 # Does the edge defiend by a vertex pair exists? Edges defined from VertexID1 to VertecID2
     360 # and VertexID2 to VertexID1 are considered equivalent...
     361 sub HasEdge {
     362   my($This, $VertexID1, $VertexID2) = @_;
     363
     364   if (!(defined($VertexID1) && defined($VertexID2))) {
     365     return 0;
     366   }
     367
     368   return ($This->_HasEdge($VertexID1, $VertexID2) || $This->_HasEdge($VertexID2, $VertexID1)) ? 1 : 0;
     369 }
     370
     371 # Does edge exists?
     372 sub _HasEdge {
     373   my($This, $VertexID1, $VertexID2) = @_;
     374
     375   if (exists $This->{Edges}->{From}->{$VertexID1}) {
     376     if (exists $This->{Edges}->{From}->{$VertexID1}->{$VertexID2}) {
     377       return 1;
     378     }
     379   }
     380   elsif (exists $This->{Edges}->{To}->{$VertexID2}) {
     381     if (exists $This->{Edges}->{To}->{$VertexID2}->{$VertexID1}) {
     382       return 1;
     383     }
     384   }
     385   return 0;
     386 }
     387
     388 # Do the edges defiend by vertex pairs exist? In scalar context, return the number
     389 # of edges found...
     390 sub HasEdges {
     391   my($This, @VertexIDs) = @_;
     392
     393   if (!@VertexIDs) {
     394     return 0;
     395   }
     396   if (@VertexIDs % 2) {
     397     return 0;
     398   }
     399   my($VertexID1, $VertexID2, $Index, $Status, $EdgesCount, @EdgesStatus);
     400   @EdgesStatus = ();
     401   $EdgesCount = 0;
     402   for ($Index = 0; $Index < $#VertexIDs; $Index += 2) {
     403     $VertexID1 = $VertexIDs[$Index]; $VertexID2 = $VertexIDs[$Index + 1];
     404     $Status = $This->HasEdge($VertexID1, $VertexID2);
     405     push @EdgesStatus, ($Status);
     406     if (defined($Status) && $Status) {
     407       $EdgesCount++;
     408     }
     409   }
     410   return wantarray ? @EdgesStatus : $EdgesCount;
     411 }
     412
     413 # Get edges for a vertex ID or retrieve all the edges. In scalar context,
     414 #  return the number of edges.
     415 #
     416 sub GetEdges {
     417   my($This, $VertexID) = @_;
     418   my(@VertexIDs);
     419
     420   @VertexIDs = ();
     421   if (defined $VertexID) {
     422     push @VertexIDs, ($This->_GetEdgesFrom($VertexID), $This->_GetEdgesTo($VertexID))
     423   }
     424   else {
     425     push @VertexIDs, $This->_GetEdges();
     426   }
     427   return (wantarray ? @VertexIDs : @VertexIDs/2);
     428 }
     429
     430 # Get edge starting from the vertex to its successor vertices...
     431 sub _GetEdgesFrom {
     432   my($This, $VertexID1) = @_;
     433   my($VertexID2) = undef;
     434
     435   return $This->_GetEdges($VertexID1, $VertexID2);
     436 }
     437
     438 # Get edge starting from predecessors to the vertex...
     439 sub _GetEdgesTo {
     440   my($This, $VertexID2) = @_;
     441   my($VertexID1) = undef;
     442
     443   return $This->_GetEdges($VertexID1, $VertexID2);
     444 }
     445
     446 # Get edges as pair of vertex IDs. Edges data can be retrieved in three
     447 # different ways:
     448 #
     449 # Both vertex IDs are defined: Returns existing edge between the vertices
     450 # Only first vertex ID defined: Returns all edges at the vertex
     451 # Only second vertex defined: Returns all edges at the vertex
     452 # No vertex IDs defined: Returns all edges
     453 #
     454 sub _GetEdges {
     455   my($This, $VertexID1, $VertexID2) = @_;
     456   my($VertexID, @VertexIDs);
     457
     458   @VertexIDs = ();
     459
     460   if (defined($VertexID1) && defined($VertexID2)) {
     461     if ($This->HasEdge($VertexID1, $VertexID2)) {
     462       push @VertexIDs, ($VertexID1, $VertexID2);
     463     }
     464   }
     465   elsif (defined($VertexID1)) {
     466     for $VertexID ($This->_GetNeighborsFrom($VertexID1)) {
     467       push @VertexIDs, $This->_GetEdges($VertexID1, $VertexID);
     468     }
     469   }
     470   elsif (defined($VertexID2)) {
     471     for $VertexID ($This->_GetNeighborsTo($VertexID2)) {
     472       push @VertexIDs, $This->_GetEdges($VertexID, $VertexID2);
     473     }
     474   }
     475   else {
     476     for $VertexID ($This->GetVertices()) {
     477       push @VertexIDs, $This->_GetEdges($VertexID);
     478     }
     479   }
     480
     481   return @VertexIDs;
     482 }
     483
     484 # Add edges between successive pair of vertex IDs......
     485 sub AddPath {
     486   my($This, @VertexIDs) = @_;
     487
     488   if (!@VertexIDs) {
     489     carp "Warning: ${ClassName}->AddPath: No path added: Vertices list is empty...";
     490     return undef;
     491   }
     492   if (@VertexIDs == 1) {
     493     carp "Warning: ${ClassName}->AddPath: No path added: Invalid vertices data: Input list must contain more than on vertex ID...";
     494     return undef;
     495   }
     496   if (!$This->HasVertices(@VertexIDs)) {
     497     carp "Warning: ${ClassName}->AddPath: No path added: Some of the vertex IDs don't exist in the graph...";
     498     return undef;
     499   }
     500   if ($This->HasPath(@VertexIDs)) {
     501     carp "Warning: ${ClassName}->AddPath: No path added: Path already exist in the graph...";
     502     return undef;
     503   }
     504   my(@PathVertexIDs);
     505   @PathVertexIDs =$This-> _SetupPathVertices(@VertexIDs);
     506
     507   return $This->AddEdges(@PathVertexIDs);
     508 }
     509
     510
     511 # Delete edges between successive pair of vertex IDs......
     512 sub DeletePath {
     513   my($This, @VertexIDs) = @_;
     514
     515   if (!@VertexIDs) {
     516     carp "Warning: ${ClassName}->DeletePath: No path deleted: Vertices list is empty...";
     517     return undef;
     518   }
     519   if (@VertexIDs == 1) {
     520     carp "Warning: ${ClassName}->DeletePath: No path deleted: Invalid vertices data: Input list must contain more than on vertex ID...";
     521     return undef;
     522   }
     523   if (!$This->HasVertices(@VertexIDs)) {
     524     carp "Warning: ${ClassName}->DeletePath: No path deleted: Some of the vertex IDs don't exist in the graph...";
     525     return undef;
     526   }
     527   if (!$This->HasPath(@VertexIDs)) {
     528     carp "Warning: ${ClassName}->DeletePath: No path deleted: Path doesn't exist in the graph...";
     529     return undef;
     530   }
     531   my(@PathVertexIDs);
     532   @PathVertexIDs = $This->_SetupPathVertices(@VertexIDs);
     533
     534   return $This->DeleteEdges(@PathVertexIDs);
     535 }
     536
     537 # Does the path defiend by edges between successive pairs of vertex IDs exist?
     538 sub HasPath {
     539   my($This, @VertexIDs) = @_;
     540
     541   if (!@VertexIDs) {
     542     return 0;
     543   }
     544   if (@VertexIDs == 1) {
     545     return 0;
     546   }
     547   if (!$This->HasVertices(@VertexIDs)) {
     548     return 0;
     549   }
     550   my($Status, @PathVertexIDs);
     551   @PathVertexIDs = $This->_SetupPathVertices(@VertexIDs);
     552   $Status = ($This->HasEdges(@PathVertexIDs) == (@PathVertexIDs/2)) ? 1 : 0;
     553
     554   return $Status;
     555 }
     556
     557 # Setup vertices for the path to define edges between successive pair of vertex IDs...
     558 sub _SetupPathVertices {
     559   my($This, @VertexIDs) = @_;
     560   my($VertexID1, $VertexID2, $Index, @PathVertexIDs);
     561
     562   @PathVertexIDs = ();
     563   for $Index (0 .. ($#VertexIDs - 1)) {
     564     $VertexID1 = $VertexIDs[$Index];
     565     $VertexID2 = $VertexIDs[$Index + 1];
     566     push @PathVertexIDs, ($VertexID1, $VertexID2);
     567   }
     568
     569   return @PathVertexIDs;
     570 }
     571
     572 # Add edges between successive pair of vertex IDs and an additional edge from the last to
     573 # the first ID to complete the cycle......
     574 sub AddCycle {
     575   my($This, @VertexIDs) = @_;
     576
     577   if (!@VertexIDs) {
     578     carp "Warning: ${ClassName}->AddCycle: No cycle added: Vertices list is empty...";
     579     return undef;
     580   }
     581   if (@VertexIDs == 1) {
     582     carp "Warning: ${ClassName}->AddCycle: No cycle added: Invalid vertices data: Input list must contain more than on vertex ID...";
     583     return undef;
     584   }
     585   if (!$This->HasVertices(@VertexIDs)) {
     586     carp "Warning: ${ClassName}->AddCycle: No cycle added: Some of the vertex IDs don't exist in the graph...";
     587     return undef;
     588   }
     589   my($FirstVertextID) = $VertexIDs[0];
     590   push @VertexIDs, ($FirstVertextID);
     591
     592   if ($This->HasCycle(@VertexIDs)) {
     593     carp "Warning: ${ClassName}->AddCycle: No cycle added: Cycle already exist in the graph...";
     594     return undef;
     595   }
     596
     597   return $This->AddPath(@VertexIDs);
     598 }
     599
     600 # Delete edges between successive pair of vertex IDs and an additional edge from the last to
     601 # the first ID to complete the cycle......
     602 sub DeleteCycle {
     603   my($This, @VertexIDs) = @_;
     604
     605   if (!@VertexIDs) {
     606     carp "Warning: ${ClassName}->DeleteCycle: No cycle deleted: Vertices list is empty...";
     607     return undef;
     608   }
     609   if (@VertexIDs == 1) {
     610     carp "Warning: ${ClassName}->DeleteCycle: No cycle deleted: Invalid vertices data: Input list must contain more than on vertex ID...";
     611     return undef;
     612   }
     613   if (!$This->HasVertices(@VertexIDs)) {
     614     carp "Warning: ${ClassName}->DeleteCycle: No cycle deleted: Some of the vertex IDs don't exist in the graph...";
     615     return undef;
     616   }
     617   if (!$This->HasCycle(@VertexIDs)) {
     618     carp "Warning: ${ClassName}->DeleteCycle: No cycle deleted: Cycle doesn't exist in the graph...";
     619     return undef;
     620   }
     621
     622   my($FirstVertextID) = $VertexIDs[0];
     623   push @VertexIDs, ($FirstVertextID);
     624
     625   return $This->DeletePath(@VertexIDs);
     626 }
     627
     628 # Does the cycle defiend by edges between successive pairs of vertex IDs along with an additional
     629 # edge from last to first vertex ID exist?
     630 sub HasCycle {
     631   my($This, @VertexIDs) = @_;
     632
     633   if (!@VertexIDs) {
     634     return 0;
     635   }
     636   if (@VertexIDs == 1) {
     637     return 0;
     638   }
     639   my($FirstVertextID) = $VertexIDs[0];
     640   push @VertexIDs, ($FirstVertextID);
     641
     642   return $This->HasPath(@VertexIDs);
     643 }
     644
     645 # Get neighbors...
     646 sub GetNeighbors {
     647   my($This, $VertexID) = @_;
     648
     649   if (!defined $VertexID) {
     650     return undef;
     651   }
     652   if (! exists $This->{Vertices}->{$VertexID}) {
     653     return undef;
     654   }
     655
     656   # Get a list of unsorted vertices and sort 'em once before returning...
     657   #
     658   my($VerticesCount, $SortVertices, @VertexIDs);
     659
     660   $SortVertices = 0;
     661   @VertexIDs = ();
     662
     663   push @VertexIDs, $This->_GetNeighborsFrom($VertexID, $SortVertices);
     664   push @VertexIDs, $This->_GetNeighborsTo($VertexID, $SortVertices);
     665   $VerticesCount = @VertexIDs;
     666
     667   return wantarray ? sort {$a <=> $b} @VertexIDs : $VerticesCount;
     668 }
     669
     670 # Get neighbors added by defining edges from the vertex. For undirected graph, it has no
     671 # strict meaning...
     672 sub _GetNeighborsFrom {
     673   my($This, $VertexID, $SortVertices) = @_;
     674   my(@VertexIDs);
     675
     676   $SortVertices = defined $SortVertices ? $SortVertices : 1;
     677   @VertexIDs = ();
     678
     679   if (exists $This->{Edges}->{From}->{$VertexID}) {
     680     push @VertexIDs, map { $This->{Edges}->{From}->{$VertexID}->{$_} }  keys %{$This->{Edges}->{From}->{$VertexID}};
     681   }
     682   return $SortVertices ? sort {$a <=> $b} @VertexIDs : @VertexIDs;
     683 }
     684
     685 # Get neighbors added by defining edges to the vertex. For undirected graphs, it has no
     686 # strict meaning.
     687 sub _GetNeighborsTo {
     688   my($This, $VertexID, $SortVertices) = @_;
     689   my(@VertexIDs);
     690
     691   $SortVertices = defined $SortVertices ? $SortVertices : 1;
     692   @VertexIDs = ();
     693
     694   if (exists $This->{Edges}->{To}->{$VertexID}) {
     695     push @VertexIDs, map { $This->{Edges}->{To}->{$VertexID}->{$_} } keys %{$This->{Edges}->{To}->{$VertexID}};
     696   }
     697   return $SortVertices ? sort {$a <=> $b} @VertexIDs : @VertexIDs;
     698 }
     699
     700 # Get vertex degree...
     701 #
     702 sub GetDegree {
     703   my($This, $VertexID) = @_;
     704
     705   if (!defined $VertexID) {
     706     return undef;
     707   }
     708   if (! exists $This->{Vertices}->{$VertexID}) {
     709     return undef;
     710   }
     711   my($Degree);
     712   $Degree = $This->_GetInDegree($VertexID) + $This->_GetOutDegree($VertexID);
     713
     714   return $Degree;
     715 }
     716
     717 # Get in degree added by defining edges to the vertex. For undirected graphs, it has no
     718 # strict meaning.
     719 #
     720 sub _GetInDegree {
     721   my($This, $VertexID) = @_;
     722   my($Degree);
     723
     724   $Degree = 0;
     725   if (exists $This->{Edges}->{To}->{$VertexID}) {
     726     $Degree = keys %{$This->{Edges}->{To}->{$VertexID}};
     727   }
     728   return $Degree;
     729 }
     730
     731 # Get out degree added by defining edges from the vertex. For undirected graphs, it has no
     732 # strict meaning.
     733 #
     734 sub _GetOutDegree {
     735   my($This, $VertexID) = @_;
     736   my($Degree);
     737
     738   $Degree = 0;
     739   if (exists $This->{Edges}->{From}->{$VertexID}) {
     740     $Degree = keys %{$This->{Edges}->{From}->{$VertexID}};
     741   }
     742   return $Degree;
     743 }
     744
     745 # Get vertex with smallest degree...
     746 #
     747 sub GetVertexWithSmallestDegree {
     748   my($This) = @_;
     749   my($Degree, $SmallestDegree, $SmallestDegreeVertexID, $VertexID, @VertexIDs);
     750
     751   @VertexIDs = ();
     752   @VertexIDs = $This->GetVertices();
     753   if (! @VertexIDs) {
     754     return undef;
     755   }
     756   $SmallestDegree = 99999; $SmallestDegreeVertexID = undef;
     757
     758   for $VertexID (@VertexIDs) {
     759     $Degree = $This->_GetInDegree($VertexID) + $This->_GetOutDegree($VertexID);
     760     if ($Degree < $SmallestDegree) {
     761       $SmallestDegree = $Degree;
     762       $SmallestDegreeVertexID = $VertexID;
     763     }
     764   }
     765   return $SmallestDegreeVertexID;
     766 }
     767
     768 # Get vertex with largest degree...
     769 #
     770 sub GetVertexWithLargestDegree {
     771   my($This) = @_;
     772   my($Degree, $LargestDegree, $LargestDegreeVertexID, $VertexID, @VertexIDs);
     773
     774   @VertexIDs = ();
     775   @VertexIDs = $This->GetVertices();
     776   if (! @VertexIDs) {
     777     return undef;
     778   }
     779   $LargestDegree = 0; $LargestDegreeVertexID = undef;
     780
     781   for $VertexID (@VertexIDs) {
     782     $Degree = $This->_GetInDegree($VertexID) + $This->_GetOutDegree($VertexID);
     783     if ($Degree > $LargestDegree) {
     784       $LargestDegree = $Degree;
     785       $LargestDegreeVertexID = $VertexID;
     786     }
     787   }
     788   return $LargestDegreeVertexID;
     789 }
     790
     791 # Get maximum degree in the graph...
     792 #
     793 sub GetMaximumDegree {
     794   my($This) = @_;
     795   my($Degree, $MaximumDegree, $VertexID, @VertexIDs);
     796
     797   @VertexIDs = ();
     798   @VertexIDs = $This->GetVertices();
     799   if (! @VertexIDs) {
     800     return undef;
     801   }
     802   $MaximumDegree = 0;
     803
     804   for $VertexID (@VertexIDs) {
     805     $Degree = $This->GetDegree($VertexID);
     806     if ($Degree > $MaximumDegree) {
     807       $MaximumDegree = $Degree;
     808     }
     809   }
     810   return $MaximumDegree;
     811 }
     812
     813 # Get minimum degree in the graph...
     814 #
     815 sub GetMininumDegree {
     816   my($This) = @_;
     817   my($Degree, $MininumDegree, $VertexID, @VertexIDs);
     818
     819   @VertexIDs = ();
     820   @VertexIDs = $This->GetVertices();
     821   if (! @VertexIDs) {
     822     return undef;
     823   }
     824   $MininumDegree = 99999;
     825
     826   for $VertexID (@VertexIDs) {
     827     $Degree = $This->GetDegree($VertexID);
     828     if ($Degree < $MininumDegree) {
     829       $MininumDegree = $Degree;
     830     }
     831   }
     832   return $MininumDegree;
     833 }
     834
     835 # Is it a isolated vertex?
     836 #
     837 sub IsIsolatedVertex {
     838   my($This, $VertexID) = @_;
     839
     840   if (!defined $VertexID) {
     841     return undef;
     842   }
     843   if (! exists $This->{Vertices}->{$VertexID}) {
     844     return undef;
     845   }
     846   return ($This->GetDegree() == 0) ? 1 : 0;
     847 }
     848
     849 # Get all isolated vertices...
     850 #
     851 sub GetIsolatedVertices {
     852   my($This) = @_;
     853
     854   return $This->GetVerticesWithDegreeLessThan(1);
     855 }
     856
     857 # Is it a leaf vertex?
     858 #
     859 sub IsLeafVertex {
     860   my($This, $VertexID) = @_;
     861
     862   if (!defined $VertexID) {
     863     return undef;
     864   }
     865   if (! exists $This->{Vertices}->{$VertexID}) {
     866     return undef;
     867   }
     868   return ($This->GetDegree() == 1) ? 1 : 0;
     869 }
     870
     871 # Get all leaf vertices...
     872 #
     873 sub GetLeafVertices {
     874   my($This) = @_;
     875
     876   return $This->GetVerticesWithDegreeLessThan(2);
     877 }
     878
     879 # Get vertices  with degree less than a specified value...
     880 #
     881 sub GetVerticesWithDegreeLessThan {
     882   my($This, $SpecifiedDegree) = @_;
     883   my($Degree, $VertexID, @VertexIDs, @FilteredVertexIDs);
     884
     885   @VertexIDs = (); @FilteredVertexIDs = ();
     886
     887   @VertexIDs = $This->GetVertices();
     888   if (! @VertexIDs) {
     889     return @FilteredVertexIDs;
     890   }
     891
     892   for $VertexID (@VertexIDs) {
     893     $Degree = $This->_GetInDegree($VertexID) + $This->_GetOutDegree($VertexID);
     894     if ($Degree < $SpecifiedDegree) {
     895       push @FilteredVertexIDs, $VertexID;
     896     }
     897   }
     898   return @FilteredVertexIDs;
     899 }
     900
     901 # Set a property for graph...
     902 sub SetGraphProperty {
     903   my($This, $Name, $Value) = @_;
     904
     905   if (!(defined($Name) && defined($Value))) {
     906     carp "Warning: ${ClassName}->SetGraphProperty: Didn't set property: Both property name and value should be specified...";
     907     return undef;
     908   }
     909   if (exists $This->{Properties}->{Graph}->{$Name}) {
     910     carp "Warning: ${ClassName}->SetGraphProperty: Didn't set property $Name: Already exists in the graph...";
     911     return undef;
     912   }
     913
     914   $This->{Properties}->{Graph}->{$Name} = $Value;
     915
     916   return $This;
     917 }
     918
     919 # Set a properties for graph...
     920 sub SetGraphProperties {
     921   my($This, %NamesAndValues) = @_;
     922
     923   if (!(keys %NamesAndValues)) {
     924     carp "Warning: ${ClassName}->SetGraphProperties: Didn't set properties: Names and values list is empty...";
     925     return undef;
     926   }
     927
     928   my($Name, $Value);
     929   while (($Name, $Value) = each  %NamesAndValues) {
     930     $This->SetGraphProperty($Name, $Value);
     931   }
     932
     933   return $This;
     934 }
     935
     936 # Get a property value for graph...
     937 sub GetGraphProperty {
     938   my($This, $Name) = @_;
     939
     940   if (!$This->HasGraphProperty($Name)) {
     941     return undef;
     942   }
     943
     944   return $This->{Properties}->{Graph}->{$Name};
     945 }
     946
     947 # Get all poperty name/value pairs for graph...
     948 sub GetGraphProperties {
     949   my($This) = @_;
     950
     951   return %{$This->{Properties}->{Graph}};
     952 }
     953
     954 # Delete a property for graph...
     955 sub DeleteGraphProperty {
     956   my($This, $Name) = @_;
     957
     958   if (!defined $Name) {
     959     carp "Warning: ${ClassName}->DeleteGraphProperty: Didn't delete graph property: Name must be specified...";
     960     return undef;
     961   }
     962   if (!$This->HasGraphProperty($Name)) {
     963     carp "Warning: ${ClassName}-> DeleteGraphProperty: Didn't delete graph property $Name: Property doesn't exist...";
     964     return undef;
     965   }
     966   delete $This->{Properties}->{Graph}->{$Name};
     967
     968   return $This;
     969 }
     970
     971 # Delete graph properites...
     972 sub DeleteGraphProperties {
     973   my($This) = @_;
     974
     975   %{$This->{Properties}->{Graph}} = ();
     976
     977   return $This;
     978 }
     979
     980
     981 # Is this property associated with graph?
     982 sub HasGraphProperty {
     983   my($This, $Name) = @_;
     984
     985   if (!defined $Name) {
     986     return 0;
     987   }
     988   return (exists $This->{Properties}->{Graph}->{$Name}) ? 1 : 0;
     989 }
     990
     991 # Set a property for vertex...
     992 sub SetVertexProperty {
     993   my($This, $Name, $Value, $VertexID) = @_;
     994
     995   if (!(defined($Name) && defined($Value) && defined($VertexID))) {
     996     carp "Warning: ${ClassName}->SetVertexProperty: Didn't set property: Property name, value and vertexID should be specified...";
     997     return undef;
     998   }
     999   if (!$This->HasVertex($VertexID)) {
    1000     carp "Warning: ${ClassName}->SetVertexProperty: Didn't set property $Name for vertex $VertexID: Vertex doesn't exist...";
    1001     return undef;
    1002   }
    1003   if ($This->HasVertexProperty($Name, $VertexID)) {
    1004     carp "Warning: ${ClassName}->SetVertexProperty: Didn't set property $Name for vertex $VertexID: Property already exists...";
    1005     return undef;
    1006   }
    1007
    1008   $This->_SetVertexProperty($Name, $Value, $VertexID);
    1009
    1010   return $This;
    1011 }
    1012
    1013 # Update a property for vertex...
    1014 sub UpdateVertexProperty {
    1015   my($This, $Name, $Value, $VertexID) = @_;
    1016
    1017   if (!(defined($Name) && defined($Value) && defined($VertexID))) {
    1018     carp "Warning: ${ClassName}->UpdateVextexProperty: Didn't update property: Property name, value and vertexID should be specified...";
    1019     return undef;
    1020   }
    1021   if (!$This->HasVertex($VertexID)) {
    1022     carp "Warning: ${ClassName}->UpdateVextexProperty: Didn't update property $Name for vertex $VertexID: Vertex doesn't exist...";
    1023     return undef;
    1024   }
    1025   if (!$This->HasVertexProperty($Name, $VertexID)) {
    1026     carp "Warning: ${ClassName}->UpdateVextexProperty: Didn't update property $Name for vertex $VertexID: Property doesn't exists...";
    1027     return undef;
    1028   }
    1029   $This->_SetVertexProperty($Name, $Value, $VertexID);
    1030
    1031   return $This;
    1032 }
    1033
    1034 # Set a vextex property...
    1035 sub _SetVertexProperty {
    1036   my($This, $Name, $Value, $VertexID) = @_;
    1037
    1038   if (!exists $This->{Properties}->{Vertices}->{$VertexID}) {
    1039     %{$This->{Properties}->{Vertices}->{$VertexID}} = ();
    1040   }
    1041   $This->{Properties}->{Vertices}->{$VertexID}->{$Name} = $Value;
    1042
    1043   return $This;
    1044 }
    1045
    1046 # Set a properties for vertex..
    1047 sub SetVertexProperties {
    1048   my($This, $VertexID, @NamesAndValues) = @_;
    1049
    1050   if (!defined $VertexID) {
    1051     carp "Warning: ${ClassName}->SetVertexProperties: Didn't set property: VertexID should be specified...";
    1052     return undef;
    1053   }
    1054   if (!@NamesAndValues) {
    1055     carp "Warning: ${ClassName}->SetVertexProperties: Didn't set property: Names and values list is empty...";
    1056     return undef;
    1057   }
    1058   if (@NamesAndValues % 2) {
    1059     carp "Warning: ${ClassName}->SetVertexProperties: Didn't set property: Invalid property name and values IDs data: Input list must contain even number of values...";
    1060     return undef;
    1061   }
    1062
    1063   my($Name, $Value, $Index);
    1064   for ($Index = 0; $Index < $#NamesAndValues; $Index += 2) {
    1065     $Name = $NamesAndValues[$Index]; $Value = $NamesAndValues[$Index + 1];
    1066     $This->SetVertexProperty($Name, $Value, $VertexID);
    1067   }
    1068
    1069   return $This;
    1070 }
    1071
    1072
    1073 # Set a property for vertices...
    1074 sub SetVerticesProperty {
    1075   my($This, $Name, @ValuesAndVertexIDs) = @_;
    1076
    1077   if (!defined $Name) {
    1078     carp "Warning: ${ClassName}->SetVerticesProperty: Didn't set property: Property name should be specified...";
    1079     return undef;
    1080   }
    1081   if (!@ValuesAndVertexIDs) {
    1082     carp "Warning: ${ClassName}->SetVerticesProperty: Didn't set property: Values and vertex IDs list is empty...";
    1083     return undef;
    1084   }
    1085   if (@ValuesAndVertexIDs % 2) {
    1086     carp "Warning: ${ClassName}->SetVerticesProperty: Didn't set property: Invalid property values and vertex IDs data: Input list must contain even number of values...";
    1087     return undef;
    1088   }
    1089
    1090   my($Value, $VertexID, $Index);
    1091   for ($Index = 0; $Index < $#ValuesAndVertexIDs; $Index += 2) {
    1092     $Value = $ValuesAndVertexIDs[$Index]; $VertexID = $ValuesAndVertexIDs[$Index + 1];
    1093     $This->SetVertexProperty($Name, $Value, $VertexID);
    1094   }
    1095
    1096   return $This;
    1097 }
    1098
    1099 # Get a property value for vertex...
    1100 sub GetVertexProperty {
    1101   my($This, $Name, $VertexID) = @_;
    1102
    1103   if (!$This->HasVertexProperty($Name, $VertexID)) {
    1104     return undef;
    1105   }
    1106
    1107   return $This->{Properties}->{Vertices}->{$VertexID}->{$Name};
    1108 }
    1109
    1110 # Get a property values for vertices...
    1111 sub GetVerticesProperty {
    1112   my($This, $Name, @VertexIDs) = @_;
    1113   my($ValuesCount, @Values);
    1114
    1115   if (!@VertexIDs) {
    1116     @VertexIDs = ();
    1117     @VertexIDs = $This->GetVertices();
    1118   }
    1119   @Values = ();
    1120   @Values = map { $This->GetVertexProperty($Name, $_ ) } @VertexIDs;
    1121   $ValuesCount = grep { defined($_) } @Values;
    1122
    1123   return wantarray ? @Values : $ValuesCount;
    1124 }
    1125
    1126 # Get all property name/values pairs for vertex...
    1127 sub GetVertexProperties {
    1128   my($This, $VertexID) = @_;
    1129
    1130   if (!$This->HasVertex($VertexID)) {
    1131     return ();
    1132   }
    1133
    1134   if (exists $This->{Properties}->{Vertices}->{$VertexID}) {
    1135     return %{$This->{Properties}->{Vertices}->{$VertexID}};
    1136   }
    1137   else {
    1138     return ();
    1139   }
    1140 }
    1141
    1142
    1143 # Delete a property for vertex...
    1144 sub DeleteVertexProperty {
    1145   my($This, $Name, $VertexID) = @_;
    1146
    1147   if (!(defined($Name) && defined($VertexID))) {
    1148     carp "Warning: ${ClassName}->DeleteVertexProperty: Didn't delete property: Property name and vertex ID must be defined...";
    1149     return undef;
    1150   }
    1151   if (!$This->HasVertexProperty($Name, $VertexID)) {
    1152     carp "Warning: ${ClassName}->DeleteVertexProperty: Didn't delete property $Name for vertex $VertexID: Vertex property doesn't exist...";
    1153     return undef;
    1154   }
    1155   $This->_DeleteVertexProperty($VertexID, $Name);
    1156
    1157   return $This;
    1158 }
    1159
    1160 # Delete vertex property or all properties...
    1161 sub _DeleteVertexProperty {
    1162   my($This, $VertexID, $Name) = @_;
    1163
    1164   if (exists $This->{Properties}->{Vertices}->{$VertexID}) {
    1165     if (defined $Name) {
    1166       if (exists $This->{Properties}->{Vertices}->{$VertexID}->{$Name}) {
    1167         delete $This->{Properties}->{Vertices}->{$VertexID}->{$Name};
    1168       }
    1169     }
    1170     else {
    1171       %{$This->{Properties}->{Vertices}->{$VertexID}} = ();
    1172     }
    1173     if (! keys %{$This->{Properties}->{Vertices}->{$VertexID}}) {
    1174       delete $This->{Properties}->{Vertices}->{$VertexID};
    1175     }
    1176   }
    1177   return $This;
    1178 }
    1179
    1180 # Delete a property for specified vertices or all the vertices...
    1181 sub DeleteVerticesProperty {
    1182   my($This, $Name, @VertexIDs) = @_;
    1183
    1184   if (!defined $Name) {
    1185     carp "Warning: ${ClassName}->DeleteVerticesProperty: Didn't delete property: Property name should be specified...";
    1186     return undef;
    1187   }
    1188   if (!@VertexIDs) {
    1189     @VertexIDs = ();
    1190     @VertexIDs = $This->GetVertices();
    1191   }
    1192   my($VertexID);
    1193   for $VertexID (@VertexIDs) {
    1194     $This->DeleteVertexProperty($Name, $VertexID);
    1195   }
    1196
    1197   return $This;
    1198 }
    1199
    1200 # Delete all properities for vertex...
    1201 sub DeleteVertexProperties {
    1202   my($This, $VertexID) = @_;
    1203
    1204   if (!defined $VertexID) {
    1205     carp "Warning: ${ClassName}->DeleteVertexProperties: Didn't delete properties: Vertex ID must be defined...";
    1206     return undef;
    1207   }
    1208   $This->_DeleteVertexProperty($VertexID);
    1209
    1210   return $This;
    1211 }
    1212
    1213 # Is this property associated with vertex?
    1214 sub HasVertexProperty {
    1215   my($This, $Name, $VertexID) = @_;
    1216
    1217   if (!(defined($Name) && defined($VertexID))) {
    1218     return 0;
    1219   }
    1220
    1221   if (exists $This->{Properties}->{Vertices}->{$VertexID}) {
    1222     if (exists $This->{Properties}->{Vertices}->{$VertexID}->{$Name}) {
    1223       return 1;
    1224     }
    1225   }
    1226   return 0;
    1227 }
    1228
    1229 # Set a property for edge...
    1230 sub SetEdgeProperty {
    1231   my($This, $Name, $Value, $VertexID1, $VertexID2) = @_;
    1232
    1233   if (!(defined($Name) && defined($Value) && defined($VertexID1) && defined($VertexID2))) {
    1234     carp "Warning: ${ClassName}->SetEdgeProperty: Didn't set property: Property name, value, vertexID1 and vertexID2 should be specified...";
    1235     return undef;
    1236   }
    1237   if (!$This->HasEdge($VertexID1, $VertexID2)) {
    1238     carp "Warning: ${ClassName}->SetEdgeProperty: Didn't set property $Name for edge between vertices $VertexID1 and $VertexID2: Edge doesn't exist...";
    1239     return undef;
    1240   }
    1241   if ($This->HasEdgeProperty($Name, $VertexID1, $VertexID2)) {
    1242     carp "Warning: ${ClassName}->SetEdgeProperty: Didn't set property $Name for edge between vertices $VertexID1 and $VertexID2: Edge property already exists...";
    1243     return undef;
    1244   }
    1245   $This->_SetEdgeProperty($Name, $Value, $VertexID1, $VertexID2);
    1246   $This->_SetEdgeProperty($Name, $Value, $VertexID2, $VertexID1);
    1247
    1248   return $This;
    1249 }
    1250
    1251 # Update a property for edge...
    1252 sub UpdateEdgeProperty {
    1253   my($This, $Name, $Value, $VertexID1, $VertexID2) = @_;
    1254
    1255   if (!(defined($Name) && defined($Value) && defined($VertexID1) && defined($VertexID2))) {
    1256     carp "Warning: ${ClassName}->UpdateEdgeProperty: Didn't update property: Property name, value, vertexID1 and vertexID2 should be specified...";
    1257     return undef;
    1258   }
    1259   if (!$This->HasEdge($VertexID1, $VertexID2)) {
    1260     carp "Warning: ${ClassName}->UpdateEdgeProperty: Didn't update property $Name for edge between vertices $VertexID1 and $VertexID2: Edge doesn't exist...";
    1261     return undef;
    1262   }
    1263   if (!$This->HasEdgeProperty($Name, $VertexID1, $VertexID2)) {
    1264     carp "Warning: ${ClassName}->UpdateEdgeProperty: Didn't update property $Name for edge between vertices $VertexID1 and $VertexID2: Edge property doesn't exists...";
    1265     return undef;
    1266   }
    1267   $This->_SetEdgeProperty($Name, $Value, $VertexID1, $VertexID2);
    1268   $This->_SetEdgeProperty($Name, $Value, $VertexID2, $VertexID1);
    1269
    1270   return $This;
    1271 }
    1272 # Set a property for edges...
    1273 sub SetEdgesProperty {
    1274   my($This, $Name, @ValuesAndVertexIDs) = @_;
    1275
    1276   if (!defined $Name) {
    1277     carp "Warning: ${ClassName}->SetEdgesProperty: Didn't set property: Property name should be specified...";
    1278     return undef;
    1279   }
    1280   if (!@ValuesAndVertexIDs) {
    1281     carp "Warning: ${ClassName}->SetEdgesProperty: Didn't set property: Values and vertex IDs list is empty...";
    1282     return undef;
    1283   }
    1284   if (@ValuesAndVertexIDs % 3) {
    1285     carp "Warning: ${ClassName}->SetEdgesProperty: Didn't set property: Invalid property values and vertex IDs data: Input list must contain triplets of values...";
    1286     return undef;
    1287   }
    1288
    1289   my($Value, $VertexID1, $VertexID2, $Index);
    1290   for ($Index = 0; $Index < $#ValuesAndVertexIDs; $Index += 3) {
    1291     $Value = $ValuesAndVertexIDs[$Index];
    1292     $VertexID1 = $ValuesAndVertexIDs[$Index + 1]; $VertexID2 = $ValuesAndVertexIDs[$Index + 2];
    1293     $This->SetEdgeProperty($Name, $Value, $VertexID1, $VertexID2);
    1294   }
    1295
    1296   return $This;
    1297 }
    1298
    1299 # Set a properties for a edge...
    1300 sub SetEdgeProperties {
    1301   my($This, $VertexID1, $VertexID2, @NamesAndValues) = @_;
    1302
    1303   if (!(defined($VertexID1) && defined($VertexID2))) {
    1304     carp "Warning: ${ClassName}->SetEdgeProperties: Didn't set property: Both vertexID1 and vertexID2 should be specified...";
    1305     return undef;
    1306   }
    1307   if (!@NamesAndValues) {
    1308     carp "Warning: ${ClassName}->SetEdgeProperties: Didn't set property: Property name and values ist is empty...";
    1309     return undef;
    1310   }
    1311   if (@NamesAndValues % 2) {
    1312     carp "Warning: ${ClassName}->SetEdgeProperties: Didn't set property: Invalid property name and values data: Input list must contain triplets of values...";
    1313     return undef;
    1314   }
    1315
    1316   my($Name, $Value, $Index);
    1317   for ($Index = 0; $Index < $#NamesAndValues; $Index += 2) {
    1318     $Name = $NamesAndValues[$Index];
    1319     $Value = $NamesAndValues[$Index + 1];
    1320     $This->SetEdgeProperty($Name, $Value, $VertexID1, $VertexID2);
    1321   }
    1322
    1323   return $This;
    1324 }
    1325
    1326 # Set edge property...
    1327 sub _SetEdgeProperty {
    1328   my($This, $Name, $Value, $VertexID1, $VertexID2) = @_;
    1329
    1330   if (!exists $This->{Properties}->{Edges}->{$VertexID1}) {
    1331     %{$This->{Properties}->{Edges}->{$VertexID1}} = ();
    1332   }
    1333   if (!exists $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}) {
    1334     %{$This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}} = ();
    1335   }
    1336   $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}->{$Name} = $Value;
    1337
    1338   return $This;
    1339 }
    1340
    1341 # Get a property value for edge...
    1342 sub GetEdgeProperty {
    1343   my($This, $Name, $VertexID1, $VertexID2) = @_;
    1344
    1345   if (!$This->HasEdgeProperty($Name, $VertexID1, $VertexID2)) {
    1346     return undef;
    1347   }
    1348   return $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}->{$Name};
    1349 }
    1350
    1351 # Get a property values for edges...
    1352 sub GetEdgesProperty {
    1353   my($This, $Name, @VertexIDs) = @_;
    1354
    1355   if (!@VertexIDs) {
    1356     @VertexIDs = ();
    1357     @VertexIDs = $This->GetEdges();
    1358   }
    1359   if (@VertexIDs % 2) {
    1360     return undef;
    1361   }
    1362
    1363   my($VertexID1, $VertexID2, $Index, $ValuesCount, @Values);
    1364   @Values = ();
    1365   for ($Index = 0; $Index < $#VertexIDs; $Index += 2) {
    1366     $VertexID1 = $VertexIDs[$Index]; $VertexID2 = $VertexIDs[$Index + 1];
    1367     push @Values, $This->GetEdgeProperty($Name, $VertexID1, $VertexID2);
    1368   }
    1369   $ValuesCount = grep { defined($_) } @Values;
    1370
    1371   return wantarray ? @Values : $ValuesCount;
    1372 }
    1373
    1374 # Get all property name/value paries for edge...
    1375 sub GetEdgeProperties {
    1376   my($This, $VertexID1, $VertexID2) = @_;
    1377
    1378   if (!(defined($VertexID1) && defined($VertexID2))) {
    1379     return ();
    1380   }
    1381   if (!exists $This->{Properties}->{Edges}->{$VertexID1}) {
    1382     return ();
    1383   }
    1384   if (!exists $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}) {
    1385     return ();
    1386   }
    1387   return %{$This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}};
    1388 }
    1389
    1390 # Delete a property for edge...
    1391 sub DeleteEdgeProperty {
    1392   my($This, $Name, $VertexID1, $VertexID2) = @_;
    1393
    1394   if (!(defined($Name) && defined($VertexID1) && defined($VertexID2))) {
    1395     carp "Warning: ${ClassName}->DeleteEdgeProperty: Didn't delete property: Property name, vertexID1 and vertexID2 should be specified...";
    1396     return undef;
    1397   }
    1398   if (!$This->HasEdgeProperty($Name, $VertexID1, $VertexID2)) {
    1399     carp "Warning: ${ClassName}->DeleteEdgeProperty: Didn't delete property $Name for edge between vertices $VertexID1 and $VertexID2: Edge property doesn't exist...";
    1400     return undef;
    1401   }
    1402   $This->_DeleteEdgeProperty($VertexID1, $VertexID2, $Name);
    1403   $This->_DeleteEdgeProperty($VertexID2, $VertexID1, $Name);
    1404
    1405   return $This;
    1406 }
    1407
    1408 # Delete a property for edges...
    1409 sub DeleteEdgesProperty {
    1410   my($This, $Name, @VertexIDs) = @_;
    1411
    1412   if (!defined $Name) {
    1413     carp "Warning: ${ClassName}->DeleteEdgesProperty: Didn't delete property: Property name should be specified...";
    1414     return undef;
    1415   }
    1416   if (!@VertexIDs) {
    1417     @VertexIDs = ();
    1418     @VertexIDs = $This->GetEdges();
    1419   }
    1420   if (@VertexIDs % 2) {
    1421     carp "Warning: ${ClassName}->DeleteEdgesProperty: Didn't set property: Invalid property values and vertex IDs data: Input list must contain even number of values...";
    1422     return undef;
    1423   }
    1424   my($Index, $VertexID1, $VertexID2);
    1425   for ($Index = 0; $Index < $#VertexIDs; $Index += 2) {
    1426     $VertexID1 = $VertexIDs[$Index]; $VertexID2 = $VertexIDs[$Index + 1];
    1427     $This->DeleteEdgeProperty($Name, $VertexID1, $VertexID2);
    1428   }
    1429
    1430   return $This;
    1431 }
    1432
    1433 # Delete all properties for edge...
    1434 sub DeleteEdgeProperties {
    1435   my($This, $VertexID1, $VertexID2) = @_;
    1436
    1437   if (!(defined($VertexID1) && defined($VertexID2))) {
    1438     carp "Warning: ${ClassName}->DeleteEdgeProperties: Didn't delete property: VertexID1 and vertexID2 should be specified...";
    1439     return undef;
    1440   }
    1441   $This->_DeleteEdgeProperty($VertexID1, $VertexID2);
    1442   $This->_DeleteEdgeProperty($VertexID2, $VertexID1);
    1443
    1444   return $This;
    1445 }
    1446
    1447 # Delete properties for edges...
    1448 sub DeleteEdgesProperties {
    1449   my($This, @VertexIDs) = @_;
    1450
    1451   if (!@VertexIDs) {
    1452     @VertexIDs = ();
    1453     @VertexIDs = $This->GetEdges();
    1454   }
    1455   if (@VertexIDs % 2) {
    1456     carp "Warning: ${ClassName}->DeleteEdgesProperty: Didn't set property: Invalid property values and vertex IDs data: Input list must contain even number of values...";
    1457     return undef;
    1458   }
    1459   my($Index, $VertexID1, $VertexID2);
    1460   for ($Index = 0; $Index < $#VertexIDs; $Index += 2) {
    1461     $VertexID1 = $VertexIDs[$Index]; $VertexID2 = $VertexIDs[$Index + 1];
    1462     $This->DeleteEdgeProperties($VertexID1, $VertexID2);
    1463   }
    1464   return $This;
    1465 }
    1466
    1467
    1468 # Delete a specific edge property or all edge properties...
    1469 sub _DeleteEdgeProperty {
    1470   my($This, $VertexID1, $VertexID2, $Name) = @_;
    1471
    1472   if (exists $This->{Properties}->{Edges}->{$VertexID1}) {
    1473     if (exists $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}) {
    1474       if (defined $Name) {
    1475         if (exists $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}->{$Name}) {
    1476           delete $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}->{$Name};
    1477         }
    1478       }
    1479       else {
    1480         %{$This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}} = ();
    1481       }
    1482       if (! keys %{$This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}}) {
    1483         delete $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2};
    1484       }
    1485     }
    1486     if (! keys %{$This->{Properties}->{Edges}->{$VertexID1}}) {
    1487       delete $This->{Properties}->{Edges}->{$VertexID1};
    1488     }
    1489   }
    1490
    1491   return $This;
    1492 }
    1493
    1494 # Is this property associated with edge?
    1495 sub HasEdgeProperty {
    1496   my($This, $Name, $VertexID1, $VertexID2) = @_;
    1497
    1498   if (!(defined($Name) && defined($VertexID1) && defined($VertexID2))) {
    1499     return 0;
    1500   }
    1501   my($Status);
    1502
    1503   $Status = ($This->_HasEdgeProperty($Name, $VertexID1, $VertexID2) || $This->_HasEdgeProperty($Name, $VertexID2, $VertexID1)) ? 1 : 0;
    1504
    1505   return $Status;
    1506 }
    1507
    1508 # Does edge proprty exists?
    1509 sub _HasEdgeProperty {
    1510   my($This, $Name, $VertexID1, $VertexID2) = @_;
    1511
    1512   if (exists $This->{Properties}->{Edges}->{$VertexID1}) {
    1513     if (exists $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}) {
    1514       if (exists $This->{Properties}->{Edges}->{$VertexID1}->{$VertexID2}->{$Name}) {
    1515         return 1;
    1516       }
    1517     }
    1518   }
    1519   return 0;
    1520 }
    1521
    1522 # Is it a graph object?
    1523 sub IsGraph ($) {
    1524   my($Object) = @_;
    1525
    1526   return _IsGraph($Object);
    1527 }
    1528
    1529 # Return a string containg vertices, edges and other properties...
    1530 sub StringifyGraph {
    1531   my($This) = @_;
    1532   my($GraphString);
    1533
    1534   $GraphString = 'Graph:' . $This->StringifyVerticesAndEdges() . '; ' . $This->StringifyProperties();
    1535
    1536   return $GraphString;
    1537 }
    1538
    1539 # Return a string containg vertices, edges and other properties...
    1540 sub StringifyProperties {
    1541   my($This) = @_;
    1542   my($PropertiesString);
    1543
    1544   $PropertiesString = $This->StringifyGraphProperties() . '; ' . $This->StringifyVerticesProperties(). '; ' . $This->StringifyEdgesProperties();
    1545
    1546   return $PropertiesString;
    1547 }
    1548
    1549 # Return a string containg vertices and edges...
    1550 sub StringifyVerticesAndEdges {
    1551   my($This) = @_;
    1552   my($GraphString, $Index, $VertexID, $VertexID1, $VertexID2, $Count, @EdgeVertexIDs, @VertexIDs);
    1553
    1554   # Get vertices and edges...
    1555   $GraphString = '';
    1556   @VertexIDs = ();
    1557   @VertexIDs = $This->GetVertices();
    1558   $Count = 0;
    1559   for $VertexID (@VertexIDs) {
    1560     $Count++;
    1561     @EdgeVertexIDs = ();
    1562     @EdgeVertexIDs = $This->_GetEdgesFrom($VertexID);
    1563     if (@EdgeVertexIDs) {
    1564       for ($Index = 0; $Index < $#EdgeVertexIDs; $Index += 2) {
    1565         $VertexID1 = $EdgeVertexIDs[$Index]; $VertexID2 = $EdgeVertexIDs[$Index + 1];
    1566         $GraphString .= " ${VertexID1}-${VertexID2}";
    1567       }
    1568     }
    1569     else {
    1570       $GraphString .= " ${VertexID}";
    1571     }
    1572   }
    1573   if (!$Count) {
    1574     $GraphString = 'Graph: None';
    1575   }
    1576   return $GraphString;
    1577 }
    1578
    1579 # Return a string containg graph properties...
    1580 sub StringifyGraphProperties {
    1581   my($This) = @_;
    1582   my($Name, $Value, $Count, $GraphPropertyString, %GraphProperties);
    1583
    1584   $GraphPropertyString = "GraphProperties: ";
    1585   %GraphProperties = ();
    1586   %GraphProperties = $This->GetGraphProperties();
    1587   if (keys %GraphProperties) {
    1588     for $Name (sort keys %GraphProperties) {
    1589       $Value = $GraphProperties{$Name};
    1590       if (ref($Value) =~ /^ARRAY/) {
    1591         if (@{$Value}) {
    1592           $GraphPropertyString .= " ${Name}=(Count: " . scalar @{$Value} . "; " . join(', ', @{$Value}) .  ")";
    1593         }
    1594         else {
    1595           $GraphPropertyString .= " ${Name}=None";
    1596         }
    1597       }
    1598       else {
    1599         $GraphPropertyString .= " ${Name}=${Value}";
    1600       }
    1601     }
    1602   }
    1603   else {
    1604     $GraphPropertyString .= " None";
    1605   }
    1606   return $GraphPropertyString;
    1607 }
    1608
    1609 # Return a string containg vertices  properties...
    1610 sub StringifyVerticesProperties {
    1611   my($This) = @_;
    1612   my($Name, $Value, $Count, $VertexPropertyString, $VertexID, @VertexIDs, %VertexProperties);
    1613
    1614   @VertexIDs = ();
    1615   @VertexIDs = $This->GetVertices();
    1616   $Count = 0;
    1617   $VertexPropertyString = "VertexProperties:";
    1618   for $VertexID (@VertexIDs) {
    1619     %VertexProperties = ();
    1620     %VertexProperties = $This->GetVertexProperties($VertexID);
    1621     if (keys %VertexProperties) {
    1622       $Count++;
    1623       $VertexPropertyString .= " <Vertex ${VertexID}: ";
    1624       for $Name (sort keys %VertexProperties) {
    1625         $Value = $VertexProperties{$Name};
    1626         if (ref($Value) =~ /^ARRAY/) {
    1627           if (@{$Value}) {
    1628             $VertexPropertyString .= " ${Name}=(" . join(', ', @{$Value}) .  ")";
    1629           }
    1630           else {
    1631             $VertexPropertyString .= " ${Name}=None";
    1632           }
    1633         }
    1634         else {
    1635           $VertexPropertyString .= " ${Name}=${Value}";
    1636         }
    1637       }
    1638       $VertexPropertyString .= ">";
    1639     }
    1640   }
    1641   if (!$Count) {
    1642     $VertexPropertyString = "VertexProperties: None";
    1643   }
    1644   return $VertexPropertyString;
    1645 }
    1646
    1647 # Return a string containg edges properties...
    1648 sub StringifyEdgesProperties {
    1649   my($This) = @_;
    1650   my($Name, $Value, $Index, $EdgePropertyString, $Count, $VertexID, $VertexID1, $VertexID2, @EdgesVertexIDs, %EdgeProperties);
    1651
    1652   @EdgesVertexIDs = ();
    1653   @EdgesVertexIDs = $This->GetEdges();
    1654   $Count = 0;
    1655   $EdgePropertyString = "EdgeProperties:";
    1656   for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) {
    1657     $VertexID1 = $EdgesVertexIDs[$Index]; $VertexID2 = $EdgesVertexIDs[$Index + 1];
    1658     %EdgeProperties = ();
    1659     %EdgeProperties = $This->GetEdgeProperties($VertexID1, $VertexID2);
    1660     if (keys %EdgeProperties) {
    1661       $Count++;
    1662       $EdgePropertyString .= " <Edge ${VertexID1}-${VertexID2}:";
    1663       for $Name (sort keys %EdgeProperties) {
    1664         $Value = $EdgeProperties{$Name};
    1665         if (ref($Value) =~ /^ARRAY/) {
    1666           if (@{$Value}) {
    1667             $EdgePropertyString .= " ${Name}=(" . join(', ', @{$Value}) .  ")";
    1668           }
    1669           else {
    1670             $EdgePropertyString .= " ${Name}=None";
    1671           }
    1672         }
    1673         else {
    1674           $EdgePropertyString .= " ${Name}=${Value}";
    1675         }
    1676       }
    1677       $EdgePropertyString .= ">";
    1678     }
    1679   }
    1680   if (!$Count) {
    1681     $EdgePropertyString = "EdgeProperties: None";
    1682   }
    1683
    1684   return $EdgePropertyString;
    1685 }
    1686
    1687 # Is it a graph object?
    1688 sub _IsGraph {
    1689   my($Object) = @_;
    1690
    1691   return (Scalar::Util::blessed($Object) && $Object->isa($ClassName)) ? 1 : 0;
    1692 }
    1693
    1694 # Copy graph and its associated data using Storable::dclone and return a new graph...
    1695 #
    1696 sub Copy {
    1697   my($This) = @_;
    1698   my($NewGraph);
    1699
    1700   $NewGraph = Storable::dclone($This);
    1701
    1702   return $NewGraph;
    1703 }
    1704
    1705 # Copy vertrices and edges from This graph to NewGraph specified...
    1706 #
    1707 sub CopyVerticesAndEdges {
    1708   my($This, $NewGraph) = @_;
    1709
    1710   # Copy vertices and edges...
    1711   my(@Vertices, @Edges);
    1712   @Vertices = $This->GetVertices();
    1713   if (@Vertices) {
    1714     $NewGraph->AddVertices(@Vertices);
    1715   }
    1716   @Edges = $This->GetEdges();
    1717   if (@Edges) {
    1718     $NewGraph->AddEdges(@Edges);
    1719   }
    1720
    1721   return $NewGraph;
    1722 }
    1723
    1724 # Copy properties of vertices from This graph to NewGraph specified...
    1725 #
    1726 sub CopyVerticesProperties {
    1727   my($This, $NewGraph) = @_;
    1728
    1729   my($VertexID, @VertexIDs, %VertexProperties);
    1730   @VertexIDs = ();
    1731   @VertexIDs = $This->GetVertices();
    1732   for $VertexID (@VertexIDs) {
    1733     %VertexProperties = (); %VertexProperties = $This->GetVertexProperties($VertexID);
    1734     if (keys %VertexProperties) {
    1735       $NewGraph->SetVertexProperties($VertexID, %VertexProperties);
    1736     }
    1737   }
    1738   return $NewGraph;
    1739 }
    1740
    1741 # Copy properties of edges from This graph to NewGraph specified...
    1742 #
    1743 sub CopyEdgesProperties {
    1744   my($This, $NewGraph) = @_;
    1745
    1746   my($Index, $VertexID1, $VertexID2, @EdgesVertexIDs, %EdgeProperties);
    1747   @EdgesVertexIDs = ();
    1748   @EdgesVertexIDs = $This->GetEdges();
    1749   for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) {
    1750     $VertexID1 = $EdgesVertexIDs[$Index]; $VertexID2 = $EdgesVertexIDs[$Index + 1];
    1751     %EdgeProperties = (); %EdgeProperties = $This->GetEdgeProperties($VertexID1, $VertexID2);
    1752     if (keys %EdgeProperties) {
    1753       $NewGraph->SetEdgeProperties($VertexID1, $VertexID2, %EdgeProperties);
    1754     }
    1755   }
    1756   return $NewGraph;
    1757 }
    1758
    1759 # Detect cycles and associate 'em to graph as graph property...
    1760 #
    1761 # Note:
    1762 #   . CyclesDetection class detects all cycles in the graph and filters 'em to find
    1763 #     independent cycles.
    1764 #   . All cycles related methods in the graph operate on active cyclic paths. By default,
    1765 #     active cyclic paths correspond to independent cycles. This behavior can be changed
    1766 #     using SetActiveCyclicPaths method.
    1767 #   . For topologically complex graphs containing large number of cycles, DetectCycles method
    1768 #     implemented in CyclesDetection can time out in which case no cycles are detected or
    1769 #     assigned.
    1770 #
    1771 sub DetectCycles {
    1772   my($This) = @_;
    1773   my($CyclesDetection);
    1774
    1775   # Delete existing graph cycles...
    1776   $This->_DeleteCyclesAssociatedWithGraph();
    1777
    1778   # Detect cycles...
    1779   $CyclesDetection = new Graph::CyclesDetection($This);
    1780   if (!$CyclesDetection->DetectCycles()) {
    1781     # Cycles detection didn't finish...
    1782     return undef;
    1783   }
    1784
    1785   # Get cycles and associate 'em to graph as properties...
    1786   my(@AllCyclicPaths, @IndependentCyclicPaths);
    1787   @AllCyclicPaths = $CyclesDetection->GetAllCyclicPaths();
    1788   @IndependentCyclicPaths = $CyclesDetection->GetIndependentCyclicPaths();
    1789
    1790   $This->SetGraphProperty('ActiveCyclicPaths', \@IndependentCyclicPaths);
    1791   $This->SetGraphProperty('AllCyclicPaths', \@AllCyclicPaths);
    1792   $This->SetGraphProperty('IndependentCyclicPaths', \@IndependentCyclicPaths);
    1793
    1794   # Map cycles information to vertices and edges; identify fused cycles as well...
    1795   return $This->_ProcessDetectedCycles();
    1796 }
    1797
    1798 # Delete any cycle properties assigned to graph, vertices and edges during detect cycles operation...
    1799 #
    1800 sub ClearCycles {
    1801   my($This) = @_;
    1802
    1803   # Delete cycle properties associated with graph...
    1804   $This->_DeleteCyclesAssociatedWithGraph();
    1805   $This->_DeleteFusedCyclesAssociatedWithGraph();
    1806
    1807   # Delete cycle properties associated with vertices and edges...
    1808   $This->_DeleteCyclesAssociatedWithVertices();
    1809   $This->_DeleteCyclesAssociatedWithEdges();
    1810
    1811   return $This;
    1812 }
    1813
    1814 # Setup cyclic paths to use during all cycle related methods. Possible values:
    1815 # Independent or All. Default is to use Independent cyclic paths.
    1816 #
    1817 sub SetActiveCyclicPaths {
    1818   my($This, $CyclicPathsType) = @_;
    1819
    1820   if (!defined $CyclicPathsType) {
    1821     carp "Warning: ${ClassName}->SetActiveCyclicPaths: Didn't set active cyclic path: Cyclic path must be specified...";
    1822     return undef;
    1823   }
    1824   if ($CyclicPathsType !~ /^(Independent|All)$/i) {
    1825     carp "Warning: ${ClassName}->SetActiveCyclicPaths: Didn't set active cyclic path: Specified path type, $CyclicPathsType, is not valid. Supported valeus: Independent or All...";
    1826     return undef;
    1827   }
    1828   if (!$This->HasGraphProperty('ActiveCyclicPaths')) {
    1829     carp "Warning: ${ClassName}->SetActiveCyclicPaths: Didn't set active cyclic path: Cycles haven't been detected yet...";
    1830     return undef;
    1831   }
    1832   $This->DeleteGraphProperty('ActiveCyclicPaths');
    1833
    1834   my($ActiveCyclicPathsRef);
    1835   if ($CyclicPathsType =~ /^Independent$/i) {
    1836     $ActiveCyclicPathsRef = $This->GetGraphProperty('IndependentCyclicPaths');
    1837   }
    1838   elsif ($CyclicPathsType =~ /^All$/i) {
    1839     $ActiveCyclicPathsRef = $This->GetGraphProperty('AllCyclicPaths');
    1840   }
    1841   $This->SetGraphProperty('ActiveCyclicPaths', $ActiveCyclicPathsRef);
    1842
    1843   # Map cycles information to vertices and edges; identify fused cycles as well...
    1844   $This->_ProcessDetectedCycles();
    1845
    1846   return $This;
    1847 }
    1848
    1849 # Assign cycles information on to vertices and edges as vertex edge properties properties;
    1850 # identify fused cycles as well...
    1851 #
    1852 sub _ProcessDetectedCycles {
    1853   my($This) = @_;
    1854
    1855   $This->_AssociateCyclesWithVertices();
    1856   $This->_AssociateCyclesWithEdgesAndIdentifyFusedCycles();
    1857
    1858   return $This;
    1859 }
    1860
    1861 # Associate cycles information to vertices as vertex properties...
    1862 #
    1863 sub _AssociateCyclesWithVertices {
    1864   my($This) = @_;
    1865
    1866   # Clear up any exisiting properties...
    1867   $This->_DeleteCyclesAssociatedWithVertices();
    1868
    1869   # Collects CyclicPaths for each vertex...
    1870   my($VertexID, $ActiveCyclicPath, $ActiveCyclicPathsRef, @CyclicPathVertexIDs, %VertexIDToCylicPaths);
    1871
    1872   %VertexIDToCylicPaths = ();
    1873   $ActiveCyclicPathsRef = $This->GetGraphProperty('ActiveCyclicPaths');
    1874
    1875   if (!@{$ActiveCyclicPathsRef}) {
    1876     # No cycles out there...
    1877     return $This;
    1878   }
    1879
    1880   for $ActiveCyclicPath (@{$ActiveCyclicPathsRef}) {
    1881     @CyclicPathVertexIDs = ();
    1882     @CyclicPathVertexIDs = $ActiveCyclicPath->GetVertices();
    1883     # Take out end vertex: It's same as start vertex for cyclic path...
    1884     pop @CyclicPathVertexIDs;
    1885     for $VertexID (@CyclicPathVertexIDs) {
    1886       if (!exists $VertexIDToCylicPaths{$VertexID}) {
    1887         @{$VertexIDToCylicPaths{$VertexID}} = ();
    1888       }
    1889       push @{$VertexIDToCylicPaths{$VertexID}}, $ActiveCyclicPath;
    1890     }
    1891   }
    1892
    1893   # Associate CyclicPaths to vertices...
    1894   for $VertexID (keys %VertexIDToCylicPaths) {
    1895     $This->SetVertexProperty('ActiveCyclicPaths', \@{$VertexIDToCylicPaths{$VertexID}}, $VertexID);
    1896   }
    1897   return $This;
    1898 }
    1899
    1900 # Associate cycles information to edges as edge properties and identify fused
    1901 # cycles...
    1902 #
    1903 sub _AssociateCyclesWithEdgesAndIdentifyFusedCycles {
    1904   my($This) = @_;
    1905
    1906   # Delete existing cycles...
    1907   $This->_DeleteCyclesAssociatedWithEdges();
    1908   $This->_DeleteFusedCyclesAssociatedWithGraph();
    1909
    1910   # Collect cyclic paths for each edge...
    1911   my($Index, $VertexID1, $VertexID2, $ActiveCyclicPath, $ActiveCyclicPathsRef, $EdgeID, $EdgeIDDelimiter, $CyclesWithCommonEdgesPresent, @CyclicPathEdgeVertexIDs, %EdgeIDToCylicPaths);
    1912
    1913   %EdgeIDToCylicPaths = ();
    1914   $EdgeIDDelimiter = "~";
    1915   $ActiveCyclicPathsRef = $This->GetGraphProperty('ActiveCyclicPaths');
    1916
    1917   if (!@{$ActiveCyclicPathsRef}) {
    1918     # No cycles out there...
    1919     return $This;
    1920   }
    1921
    1922   $CyclesWithCommonEdgesPresent = 0;
    1923   for $ActiveCyclicPath (@{$ActiveCyclicPathsRef}) {
    1924     @CyclicPathEdgeVertexIDs = ();
    1925     @CyclicPathEdgeVertexIDs = $ActiveCyclicPath->GetEdges();
    1926     for ($Index = 0; $Index < $#CyclicPathEdgeVertexIDs; $Index += 2) {
    1927       $VertexID1 = $CyclicPathEdgeVertexIDs[$Index]; $VertexID2 = $CyclicPathEdgeVertexIDs[$Index + 1];
    1928       $EdgeID = ($VertexID1 < $VertexID2) ? "${VertexID1}${EdgeIDDelimiter}${VertexID2}" : "${VertexID2}${EdgeIDDelimiter}${VertexID1}";
    1929       if (exists $EdgeIDToCylicPaths{$EdgeID}) {
    1930         # A common edge between two cycles indicates a potential fused cycle...
    1931         $CyclesWithCommonEdgesPresent = 1;
    1932       }
    1933       else {
    1934         @{$EdgeIDToCylicPaths{$EdgeID}} = ();
    1935       }
    1936       push @{$EdgeIDToCylicPaths{$EdgeID}}, $ActiveCyclicPath;
    1937     }
    1938   }
    1939
    1940   # Associate CyclicPaths with edges...
    1941   for $EdgeID (keys %EdgeIDToCylicPaths) {
    1942     ($VertexID1, $VertexID2) = split($EdgeIDDelimiter, $EdgeID);
    1943     $This->SetEdgeProperty('ActiveCyclicPaths', \@{$EdgeIDToCylicPaths{$EdgeID}}, $VertexID1, $VertexID2);
    1944   }
    1945
    1946   if ($CyclesWithCommonEdgesPresent) {
    1947     # Identify fused cycles...
    1948     $This->_IdentifyAndAssociateFusedCyclesWithGraph();
    1949   }
    1950
    1951   return $This;
    1952 }
    1953
    1954 # Identify fused cycles and associate them to graph as graph property after cycles
    1955 # have been associated with edges...
    1956 #
    1957 # Note:
    1958 #   . During aromaticity detection, fused cycles are treated as one set for counting
    1959 #     number of available pi electrons to check against Huckel's rule.
    1960 #   . Fused cylce sets contain cycles with at least one common edge between pair
    1961 #     of cycles. A specific pair of cycles might not have a direct common edge, but
    1962 #     ends up in the same set due to a common edge with another cycle.
    1963 #   . Fused cycles are attached to graph as 'FusedActiveCyclicPaths' property with
    1964 #     its value as a reference to list of reference where each refernece corresponds
    1965 #     to a list of cyclic path objects in a fused set.
    1966 #   . For graphs containing fused cycles, non-fused cycles are separeted from fused
    1967 #     cycles and attached to the graph as 'NonFusedActiveCyclicPaths'. It's a reference
    1968 #     to list containing cylic path objects.
    1969 #
    1970 sub _IdentifyAndAssociateFusedCyclesWithGraph {
    1971   my($This) = @_;
    1972
    1973   # Delete exisiting fused and non-fused cycles...
    1974   $This->_DeleteFusedCyclesAssociatedWithGraph();
    1975
    1976   my($ActiveCyclicPathsRef);
    1977   $ActiveCyclicPathsRef = $This->GetGraphProperty('ActiveCyclicPaths');
    1978   if (!@{$ActiveCyclicPathsRef}) {
    1979     # No cycles out there...
    1980     return $This;
    1981   }
    1982
    1983   # Get fused cycle pairs...
    1984   my($FusedCyclePairsRef, $FusedCyclesRef, $InValidFusedCycleRef);
    1985   ($FusedCyclePairsRef, $FusedCyclesRef, $InValidFusedCycleRef) = $This->_GetFusedCyclePairs($ActiveCyclicPathsRef);
    1986
    1987   # Get fused cycle set indices...
    1988   my($FusedCycleSetsIndicesRef, $FusedCycleSetsCommonEdgesRef);
    1989   $FusedCycleSetsIndicesRef = $This->_GetFusedCycleSetsIndices($FusedCyclePairsRef, $FusedCyclesRef);
    1990   if (!@{$FusedCycleSetsIndicesRef}) {
    1991     # No fused cycles out there...
    1992     return $This;
    1993   }
    1994
    1995   # Get fused and non-fused cycles...
    1996   my($FusedCycleSetsRef, $NonFusedCyclesRef);
    1997   ($FusedCycleSetsRef, $NonFusedCyclesRef) = $This->_GetFusedAndNonFusedCycles($ActiveCyclicPathsRef, $FusedCycleSetsIndicesRef, $InValidFusedCycleRef);
    1998   if (!@{$FusedCycleSetsRef}) {
    1999     # No fused cycles out there...
    2000     return $This;
    2001   }
    2002
    2003   # Associate fused and non fused cycles to graph....
    2004   $This->SetGraphProperty('FusedActiveCyclicPaths', $FusedCycleSetsRef);
    2005   $This->SetGraphProperty('NonFusedActiveCyclicPaths', $NonFusedCyclesRef);
    2006
    2007   return $This;
    2008 }
    2009
    2010 # Collect fused cycle pairs...
    2011 #
    2012 sub _GetFusedCyclePairs {
    2013   my($This, $ActiveCyclicPathsRef) = @_;
    2014
    2015   # Setup a CyclicPathID to CyclicPathIndex map...
    2016   my($CyclicPathIndex, $CyclicPathID, $ActiveCyclicPath, %CyclicPathIDToIndex);
    2017
    2018   %CyclicPathIDToIndex = ();
    2019   for $CyclicPathIndex (0 .. $#{$ActiveCyclicPathsRef}) {
    2020     $ActiveCyclicPath = $ActiveCyclicPathsRef->[$CyclicPathIndex];
    2021     $CyclicPathID = "$ActiveCyclicPath";
    2022     $CyclicPathIDToIndex{$CyclicPathID} = $CyclicPathIndex;
    2023   }
    2024   # Go over cycle edges and collect fused cycle pairs...
    2025   my($Index, $VertexID1, $VertexID2, $EdgeCyclicPathsRef, $EdgeID, $CyclicPath1, $CyclicPath2, $CyclicPathID1, $CyclicPathID2, $FusedCyclePairID, $FusedCyclicPath1, $FusedCyclicPath2, $FusedCyclicPathID1, $FusedCyclicPathID2, $FusedCyclicPathIndex1, $FusedCyclicPathIndex2, $FusedCyclePairEdgeCount, @CyclicPathEdgeVertexIDs, %FusedCyclePairs, %CommonEdgeVisited, %CommonEdgesCount, %FusedCycles, %InValidFusedCycles);
    2026
    2027   %FusedCyclePairs = (); %CommonEdgeVisited = ();
    2028   %CommonEdgesCount = ();
    2029   %InValidFusedCycles = (); %FusedCycles = ();
    2030
    2031   for $ActiveCyclicPath (@{$ActiveCyclicPathsRef}) {
    2032     @CyclicPathEdgeVertexIDs = ();
    2033     @CyclicPathEdgeVertexIDs = $ActiveCyclicPath->GetEdges();
    2034     EDGE: for ($Index = 0; $Index < $#CyclicPathEdgeVertexIDs; $Index += 2) {
    2035       $VertexID1 = $CyclicPathEdgeVertexIDs[$Index]; $VertexID2 = $CyclicPathEdgeVertexIDs[$Index + 1];
    2036       $EdgeCyclicPathsRef = $This->GetEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2);
    2037       if (@{$EdgeCyclicPathsRef} != 2) {
    2038         # Not considered a fused edge...
    2039         next EDGE;
    2040       }
    2041       # Set up a fused cycle pair...
    2042       ($FusedCyclicPath1, $FusedCyclicPath2) = @{$EdgeCyclicPathsRef};
    2043       ($FusedCyclicPathID1, $FusedCyclicPathID2) = ("${FusedCyclicPath1}", "${FusedCyclicPath2}");
    2044       ($FusedCyclicPathIndex1, $FusedCyclicPathIndex2) = ($CyclicPathIDToIndex{$FusedCyclicPathID1}, $CyclicPathIDToIndex{$FusedCyclicPathID2});
    2045       $FusedCyclePairID = ($FusedCyclicPathIndex1 < $FusedCyclicPathIndex2) ? "${FusedCyclicPathIndex1}-${FusedCyclicPathIndex2}" : "${FusedCyclicPathIndex2}-${FusedCyclicPathIndex1}";
    2046       $EdgeID = ($VertexID1 < $VertexID2) ? "${VertexID1}-${VertexID2}" : "${VertexID2}-${VertexID1}";
    2047
    2048       if (exists $FusedCyclePairs{$FusedCyclePairID}) {
    2049         if (exists $CommonEdgeVisited{$FusedCyclePairID}{$EdgeID}) {
    2050           # Edge already processed...
    2051           next EDGE;
    2052         }
    2053         $CommonEdgeVisited{$FusedCyclePairID}{$EdgeID} = $EdgeID;
    2054
    2055         $CommonEdgesCount{$FusedCyclePairID} += 1;
    2056         push @{$FusedCyclePairs{$FusedCyclePairID}}, $EdgeID;
    2057       }
    2058       else {
    2059         @{$FusedCyclePairs{$FusedCyclePairID}} = ();
    2060         push @{$FusedCyclePairs{$FusedCyclePairID}}, $EdgeID;
    2061
    2062         %{$CommonEdgeVisited{$FusedCyclePairID}} = ();
    2063         $CommonEdgeVisited{$FusedCyclePairID}{$EdgeID} = $EdgeID;
    2064
    2065         $CommonEdgesCount{$FusedCyclePairID} = 1;
    2066       }
    2067     }
    2068   }
    2069   # Valid fused cyle in fused cycle pairs must have only one common egde...
    2070   for $FusedCyclePairID (keys %FusedCyclePairs) {
    2071     ($FusedCyclicPathIndex1, $FusedCyclicPathIndex2) = split /-/, $FusedCyclePairID;
    2072     $FusedCycles{$FusedCyclicPathIndex1} = $FusedCyclicPathIndex1;
    2073     $FusedCycles{$FusedCyclicPathIndex2} = $FusedCyclicPathIndex2;
    2074     if (@{$FusedCyclePairs{$FusedCyclePairID}} != 1) {
    2075       # Mark the cycles involved as invalid fused cycles...
    2076       $InValidFusedCycles{$FusedCyclicPathIndex1} = $FusedCyclicPathIndex1;
    2077       $InValidFusedCycles{$FusedCyclicPathIndex2} = $FusedCyclicPathIndex2;
    2078     }
    2079   }
    2080   return (\%FusedCyclePairs, \%FusedCycles, \%InValidFusedCycles);
    2081 }
    2082
    2083 # Go over fused cycles and set up a graph to collect fused cycle sets. Graph vertices
    2084 # correspond to cylce indices; edges correspond to pair of fused cylcles; fused cycle
    2085 # sets correspond to connected components. Addionally set up common edges for
    2086 # fused cycle sets.
    2087 #
    2088 sub _GetFusedCycleSetsIndices {
    2089   my($This, $FusedCyclePairsRef, $FusedCyclesRef) = @_;
    2090   my($FusedCyclesGraph, @FusedCycleIndices, @FusedCyclePairIndices, @FusedCycleSetsIndices);
    2091
    2092   @FusedCycleIndices = (); @FusedCyclePairIndices = ();
    2093   @FusedCycleSetsIndices = ();
    2094
    2095   @FusedCycleIndices = sort { $a <=> $b } keys %{$FusedCyclesRef};
    2096   @FusedCyclePairIndices = map { split /-/, $_; } keys %{$FusedCyclePairsRef};
    2097   if (!@FusedCycleIndices) {
    2098     # No fused cycles out there...
    2099     return \@FusedCycleSetsIndices;
    2100   }
    2101   $FusedCyclesGraph = new Graph(@FusedCycleIndices);
    2102   $FusedCyclesGraph->AddEdges(@FusedCyclePairIndices);
    2103
    2104   @FusedCycleSetsIndices = $FusedCyclesGraph->GetConnectedComponentsVertices();
    2105
    2106   return \@FusedCycleSetsIndices;
    2107 }
    2108
    2109 # Go over indices of fused cycle sets and map cyclic path indices to cyclic path objects.
    2110 # For fused sets containing a cycle with more than one common edge, the whole set is treated
    2111 # as non-fused set...
    2112 #
    2113 sub _GetFusedAndNonFusedCycles {
    2114   my($This, $ActiveCyclicPathsRef, $FusedCycleSetsIndicesRef, $InValidFusedCycleRef) = @_;
    2115   my($CycleSetIndicesRef, $CyclicPathIndex, $ValidFusedCycleSet, @FusedCycleSets, @UnsortedNonFusedCycles, @NonFusedCycles, %CycleIndexVisited);
    2116
    2117   @FusedCycleSets = (); @NonFusedCycles = (); @UnsortedNonFusedCycles = ();
    2118   %CycleIndexVisited = ();
    2119   for $CycleSetIndicesRef (@{$FusedCycleSetsIndicesRef}) {
    2120     # Is it a valid fused cycle set? Fused cycle set containing any cycle with more than one common
    2121     # edge is considered invalid and all its cycles are treated as non-fused cycles.
    2122     $ValidFusedCycleSet = 1;
    2123     for $CyclicPathIndex (@{$CycleSetIndicesRef}) {
    2124       $CycleIndexVisited{$CyclicPathIndex} = $CyclicPathIndex;
    2125       if (exists $InValidFusedCycleRef->{$CyclicPathIndex}) {
    2126         $ValidFusedCycleSet = 0;
    2127       }
    2128     }
    2129     if ($ValidFusedCycleSet) {
    2130       my(@FusedCycleSet);
    2131       @FusedCycleSet = ();
    2132       push @FusedCycleSet, sort { $a->GetLength() <=> $b->GetLength() } map { $ActiveCyclicPathsRef->[$_] } @{$CycleSetIndicesRef};
    2133       push @FusedCycleSets, \@FusedCycleSet;
    2134     }
    2135     else {
    2136       push @UnsortedNonFusedCycles, map { $ActiveCyclicPathsRef->[$_] } @{$CycleSetIndicesRef};
    2137     }
    2138   }
    2139
    2140   # Add any leftover cycles to non-fused cycles list...
    2141   CYCLICPATH: for $CyclicPathIndex (0 .. $#{$ActiveCyclicPathsRef}) {
    2142     if (exists $CycleIndexVisited{$CyclicPathIndex}) {
    2143       next CYCLICPATH;
    2144     }
    2145     push @UnsortedNonFusedCycles, $ActiveCyclicPathsRef->[$CyclicPathIndex];
    2146   }
    2147   @NonFusedCycles = sort { $a->GetLength() <=> $b->GetLength() } @UnsortedNonFusedCycles;
    2148
    2149   return (\@FusedCycleSets, \@NonFusedCycles);
    2150 }
    2151
    2152 # Delete cycles associated with graph...
    2153 #
    2154 sub _DeleteCyclesAssociatedWithGraph {
    2155   my($This) = @_;
    2156
    2157   if ($This->HasGraphProperty('ActiveCyclicPaths')) {
    2158     $This->DeleteGraphProperty('ActiveCyclicPaths');
    2159     $This->DeleteGraphProperty('AllCyclicPaths');
    2160     $This->DeleteGraphProperty('IndependentCyclicPaths');
    2161   }
    2162   return $This;
    2163 }
    2164
    2165 # Delete cycles associated with vertices...
    2166 #
    2167 sub _DeleteCyclesAssociatedWithVertices {
    2168   my($This) = @_;
    2169   my($VertexID, @VertexIDs);
    2170
    2171   @VertexIDs = ();
    2172   @VertexIDs = $This->GetVertices();
    2173   for $VertexID (@VertexIDs) {
    2174     if ($This->HasVertexProperty('ActiveCyclicPaths', $VertexID)) {
    2175       $This->DeleteVertexProperty('ActiveCyclicPaths', $VertexID);
    2176     }
    2177   }
    2178   return $This;
    2179 }
    2180
    2181 # Delete cycles associated with edges...
    2182 #
    2183 sub _DeleteCyclesAssociatedWithEdges {
    2184   my($This) = @_;
    2185   my($Index, $VertexID1, $VertexID2, @EdgeVertexIDs);
    2186
    2187   @EdgeVertexIDs = ();
    2188   @EdgeVertexIDs = $This->GetEdges();
    2189   for ($Index = 0; $Index < $#EdgeVertexIDs; $Index += 2) {
    2190     $VertexID1 = $EdgeVertexIDs[$Index]; $VertexID2 = $EdgeVertexIDs[$Index + 1];
    2191     if ($This->HasEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2)) {
    2192       $This->DeleteEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2);
    2193     }
    2194   }
    2195   return $This;
    2196 }
    2197
    2198 # Delete fused cycles associated with edges...
    2199 #
    2200 sub _DeleteFusedCyclesAssociatedWithGraph {
    2201   my($This) = @_;
    2202
    2203   # Delete exisiting cycles...
    2204   if ($This->HasGraphProperty('FusedActiveCyclicPaths')) {
    2205     $This->DeleteGraphProperty('FusedActiveCyclicPaths');
    2206     $This->DeleteGraphProperty('NonFusedActiveCyclicPaths');
    2207   }
    2208   return $This;
    2209 }
    2210
    2211 # Does graph contains any cycles?
    2212 #
    2213 sub IsAcyclic {
    2214   my($This) = @_;
    2215
    2216   return $This->GetNumOfCycles() ? 0 : 1;
    2217 }
    2218
    2219 # Does graph contains cycles?
    2220 #
    2221 sub IsCyclic {
    2222   my($This) = @_;
    2223
    2224   return $This->GetNumOfCycles() ? 1 : 0;
    2225 }
    2226
    2227 # Does graph contains only any cycle?
    2228 #
    2229 sub IsUnicyclic {
    2230   my($This) = @_;
    2231
    2232   return ($This->GetNumOfCycles() == 1) ? 1 : 0;
    2233 }
    2234
    2235 # Get size of smallest cycle in graph...
    2236 #
    2237 sub GetGirth {
    2238   my($This) = @_;
    2239
    2240   return $This->GetSizeOfSmallestCycle();
    2241 }
    2242
    2243 # Get size of smallest cycle in graph...
    2244 #
    2245 sub GetSizeOfSmallestCycle {
    2246   my($This) = @_;
    2247
    2248   return $This->_GetCycleSize('GraphCycle', 'SmallestCycle');
    2249 }
    2250
    2251 # Get size of largest cycle in graph...
    2252 #
    2253 sub GetCircumference {
    2254   my($This) = @_;
    2255
    2256   return $This->GetSizeOfLargestCycle();
    2257 }
    2258
    2259 # Get size of largest cycle in graph...
    2260 #
    2261 sub GetSizeOfLargestCycle {
    2262   my($This) = @_;
    2263
    2264   return $This->_GetCycleSize('GraphCycle', 'LargestCycle');
    2265 }
    2266
    2267 # Get number of cycles in graph...
    2268 #
    2269 sub GetNumOfCycles {
    2270   my($This) = @_;
    2271
    2272   return $This->_GetNumOfCyclesWithSize('GraphCycle', 'AllSizes');
    2273 }
    2274
    2275 # Get number of cycles with odd size in graph...
    2276 #
    2277 sub GetNumOfCyclesWithOddSize {
    2278   my($This) = @_;
    2279
    2280   return $This->_GetNumOfCyclesWithSize('GraphCycle', 'OddSize');
    2281 }
    2282
    2283 # Get number of cycles with even size in graph...
    2284 #
    2285 sub GetNumOfCyclesWithEvenSize {
    2286   my($This) = @_;
    2287
    2288   return $This->_GetNumOfCyclesWithSize('GraphCycle', 'EvenSize');
    2289 }
    2290
    2291 # Get number of cycles with specific size in graph...
    2292 #
    2293 sub GetNumOfCyclesWithSize {
    2294   my($This, $CycleSize) = @_;
    2295
    2296   return $This->_GetNumOfCyclesWithSize('GraphCycle', 'SpecifiedSize', $CycleSize);
    2297 }
    2298
    2299 # Get number of cycles with size less than a specific size in graph...
    2300 #
    2301 sub GetNumOfCyclesWithSizeLessThan {
    2302   my($This, $CycleSize) = @_;
    2303
    2304   return $This->_GetNumOfCyclesWithSize('GraphCycle', 'SizeLessThan', $CycleSize);
    2305 }
    2306
    2307 # Get number of cycles with size greater than a specific size in graph...
    2308 #
    2309 sub GetNumOfCyclesWithSizeGreaterThan {
    2310   my($This, $CycleSize) = @_;
    2311
    2312   return $This->_GetNumOfCyclesWithSize('GraphCycle', 'SizeGreaterThan', $CycleSize);
    2313 }
    2314
    2315 # Get largest cyclic path in graph...
    2316 #
    2317 sub GetLargestCycle {
    2318   my($This) = @_;
    2319
    2320   return $This->_GetCycle('GraphCycle', 'LargestCycle');
    2321 }
    2322
    2323 # Get smallest cyclic path in graph...
    2324 #
    2325 sub GetSmallestCycle {
    2326   my($This) = @_;
    2327
    2328   return $This->_GetCycle('GraphCycle', 'SmallestCycle');
    2329 }
    2330
    2331 # Get all cycles in graph...
    2332 #
    2333 sub GetCycles {
    2334   my($This) = @_;
    2335
    2336   return $This->_GetCyclesWithSize('GraphCycle', 'AllSizes');
    2337 }
    2338
    2339 # Get cycles with odd size in graph...
    2340 #
    2341 sub GetCyclesWithOddSize {
    2342   my($This) = @_;
    2343
    2344   return $This->_GetCyclesWithSize('GraphCycle', 'OddSize');
    2345 }
    2346
    2347 # Get cycles with even size in graph...
    2348 #
    2349 sub GetCyclesWithEvenSize {
    2350   my($This) = @_;
    2351
    2352   return $This->_GetCyclesWithSize('GraphCycle', 'EvenSize');
    2353 }
    2354
    2355 # Get cycles with specific size in graph...
    2356 #
    2357 sub GetCyclesWithSize {
    2358   my($This, $CycleSize) = @_;
    2359
    2360   return $This->_GetCyclesWithSize('GraphCycle', 'SpecifiedSize', $CycleSize);
    2361 }
    2362
    2363 # Get cycles with size less than a specific size in graph...
    2364 #
    2365 sub GetCyclesWithSizeLessThan {
    2366   my($This, $CycleSize) = @_;
    2367
    2368   return $This->_GetCyclesWithSize('GraphCycle', 'SizeLessThan', $CycleSize);
    2369 }
    2370
    2371 # Get cycles with size greater than a specific size in graph...
    2372 #
    2373 sub GetCyclesWithSizeGreaterThan {
    2374   my($This, $CycleSize) = @_;
    2375
    2376   return $This->_GetCyclesWithSize('GraphCycle', 'SizeGreaterThan', $CycleSize);
    2377 }
    2378
    2379 # Is vertex in a cycle?
    2380 #
    2381 sub IsCyclicVertex {
    2382   my($This, $VertexID) = @_;
    2383
    2384   return $This->GetNumOfVertexCycles($VertexID) ? 1 : 0;
    2385 }
    2386
    2387 # Is vertex in a only one cycle?
    2388 #
    2389 sub IsUnicyclicVertex {
    2390   my($This, $VertexID) = @_;
    2391
    2392   return ($This->GetNumOfVertexCycles($VertexID)  == 1) ? 1 : 0;
    2393 }
    2394
    2395 # Is vertex not in a cycle?
    2396 #
    2397 sub IsAcyclicVertex {
    2398   my($This, $VertexID) = @_;
    2399
    2400   return $This->GetNumOfVertexCycles($VertexID) ? 0 : 1;
    2401 }
    2402
    2403 # Get size of smallest cycle containing specified vertex...
    2404 #
    2405 sub GetSizeOfSmallestVertexCycle {
    2406   my($This, $VertexID) = @_;
    2407
    2408   return $This->_GetCycleSize('VertexCycle', 'SmallestCycle', $VertexID);
    2409 }
    2410
    2411 # Get size of largest cycle containing specified vertex...
    2412 #
    2413 sub GetSizeOfLargestVertexCycle {
    2414   my($This, $VertexID) = @_;
    2415
    2416   return $This->_GetCycleSize('VertexCycle', 'LargestCycle', $VertexID);
    2417 }
    2418
    2419 # Get number of cycles containing specified vertex...
    2420 #
    2421 sub GetNumOfVertexCycles {
    2422   my($This, $VertexID) = @_;
    2423
    2424   return $This->_GetNumOfCyclesWithSize('VertexCycle', 'AllSizes', 0, $VertexID);
    2425 }
    2426
    2427 # Get number of cycles with odd size containing specified vertex...
    2428 #
    2429 sub GetNumOfVertexCyclesWithOddSize {
    2430   my($This, $VertexID) = @_;
    2431
    2432   return $This->_GetNumOfCyclesWithSize('VertexCycle', 'OddSize', 0, $VertexID);
    2433 }
    2434
    2435 # Get number of cycles with even size containing specified vertex...
    2436 #
    2437 sub GetNumOfVertexCyclesWithEvenSize {
    2438   my($This, $VertexID) = @_;
    2439
    2440   return $This->_GetNumOfCyclesWithSize('VertexCycle', 'EvenSize', 0, $VertexID);
    2441 }
    2442
    2443 # Get number of cycles with specified size containing specified vertex...
    2444 #
    2445 sub GetNumOfVertexCyclesWithSize {
    2446   my($This, $VertexID, $CycleSize) = @_;
    2447
    2448   return $This->_GetNumOfCyclesWithSize('VertexCycle', 'SpecifiedSize', $CycleSize, $VertexID);
    2449 }
    2450
    2451 # Get number of cycles with size less than specified size containing specified vertex...
    2452 #
    2453 sub GetNumOfVertexCyclesWithSizeLessThan {
    2454   my($This, $VertexID, $CycleSize) = @_;
    2455
    2456   return $This->_GetNumOfCyclesWithSize('VertexCycle', 'SizeLessThan', $CycleSize, $VertexID);
    2457 }
    2458
    2459 # Get number of cycles with size greater than specified size containing specified vertex...
    2460 #
    2461 sub GetNumOfVertexCyclesWithSizeGreaterThan {
    2462   my($This, $VertexID, $CycleSize) = @_;
    2463
    2464   return $This->_GetNumOfCyclesWithSize('VertexCycle', 'SizeGreaterThan', $CycleSize, $VertexID);
    2465 }
    2466
    2467 # Get smallest cycle containing specified vertex...
    2468 #
    2469 sub GetSmallestVertexCycle {
    2470   my($This, $VertexID) = @_;
    2471
    2472   return $This->_GetCycle('VertexCycle', 'SmallestCycle', $VertexID);
    2473 }
    2474
    2475 # Get largest cycle containing specified vertex...
    2476 #
    2477 sub GetLargestVertexCycle {
    2478   my($This, $VertexID) = @_;
    2479
    2480   return $This->_GetCycle('VertexCycle', 'LargestCycle', $VertexID);
    2481 }
    2482
    2483 # Get cycles containing specified vertex...
    2484 #
    2485 sub GetVertexCycles {
    2486   my($This, $VertexID) = @_;
    2487
    2488   return $This->_GetCyclesWithSize('VertexCycle', 'AllSizes', 0, $VertexID);
    2489 }
    2490
    2491 # Get cycles with odd size containing specified vertex...
    2492 #
    2493 sub GetVertexCyclesWithOddSize {
    2494   my($This, $VertexID) = @_;
    2495
    2496   return $This->_GetCyclesWithSize('VertexCycle', 'OddSize', 0, $VertexID);
    2497 }
    2498
    2499 # Get cycles with even size containing specified vertex...
    2500 #
    2501 sub GetVertexCyclesWithEvenSize {
    2502   my($This, $VertexID) = @_;
    2503
    2504   return $This->_GetCyclesWithSize('VertexCycle', 'EvenSize', 0, $VertexID);
    2505 }
    2506
    2507 # Get cycles with specified size containing specified vertex...
    2508 #
    2509 sub GetVertexCyclesWithSize {
    2510   my($This, $VertexID, $CycleSize) = @_;
    2511
    2512   return $This->_GetCyclesWithSize('VertexCycle', 'SpecifiedSize', $CycleSize, $VertexID);
    2513 }
    2514
    2515 # Get cycles with size less than specified size containing specified vertex...
    2516 #
    2517 sub GetVertexCyclesWithSizeLessThan {
    2518   my($This, $VertexID, $CycleSize) = @_;
    2519
    2520   return $This->_GetCyclesWithSize('VertexCycle', 'SizeLessThan', $CycleSize, $VertexID);
    2521 }
    2522
    2523 # Get cycles with size greater than specified size containing specified vertex...
    2524 #
    2525 sub GetVertexCyclesWithSizeGreaterThan {
    2526   my($This, $VertexID, $CycleSize) = @_;
    2527
    2528   return $This->_GetCyclesWithSize('VertexCycle', 'SizeGreaterThan', $CycleSize, $VertexID);
    2529 }
    2530
    2531 # Is edge in a cycle?
    2532 #
    2533 sub IsCyclicEdge {
    2534   my($This, $VertexID1, $VertexID2) = @_;
    2535
    2536   return $This->GetNumOfEdgeCycles($VertexID1, $VertexID2) ? 1 : 0;
    2537 }
    2538
    2539 # Is edge in a only one cycle?
    2540 #
    2541 sub IsUnicyclicEdge {
    2542   my($This, $VertexID1, $VertexID2) = @_;
    2543
    2544   return ($This->GetNumOfEdgeCycles($VertexID1, $VertexID2)  == 1) ? 1 : 0;
    2545 }
    2546
    2547 # Is Edge not in a cycle?
    2548 #
    2549 sub IsAcyclicEdge {
    2550   my($This, $VertexID1, $VertexID2) = @_;
    2551
    2552   return $This->GetNumOfEdgeCycles($VertexID1, $VertexID2) ? 0 : 1;
    2553 }
    2554
    2555 # Get size of smallest cycle containing specified edge...
    2556 #
    2557 sub GetSizeOfSmallestEdgeCycle {
    2558   my($This, $VertexID1, $VertexID2) = @_;
    2559
    2560   return $This->_GetCycleSize('EdgeCycle', 'SmallestCycle', $VertexID1, $VertexID2);
    2561 }
    2562
    2563 # Get size of largest cycle containing specified edge...
    2564 #
    2565 sub GetSizeOfLargestEdgeCycle {
    2566   my($This, $VertexID1, $VertexID2) = @_;
    2567
    2568   return $This->_GetCycleSize('EdgeCycle', 'LargestCycle', $VertexID1, $VertexID2);
    2569 }
    2570
    2571 # Get number of cycles containing specified edge...
    2572 #
    2573 sub GetNumOfEdgeCycles {
    2574   my($This, $VertexID1, $VertexID2) = @_;
    2575
    2576   return $This->_GetNumOfCyclesWithSize('EdgeCycle', 'AllSizes', 0, $VertexID1, $VertexID2);
    2577 }
    2578
    2579 # Get number of cycles with odd size containing specified edge...
    2580 #
    2581 sub GetNumOfEdgeCyclesWithOddSize {
    2582   my($This, $VertexID1, $VertexID2) = @_;
    2583
    2584   return $This->_GetNumOfCyclesWithSize('EdgeCycle', 'OddSize', 0, $VertexID1, $VertexID2);
    2585 }
    2586
    2587 # Get number of cycles with even size containing specified edge...
    2588 #
    2589 sub GetNumOfEdgeCyclesWithEvenSize {
    2590   my($This, $VertexID1, $VertexID2) = @_;
    2591
    2592   return $This->_GetNumOfCyclesWithSize('EdgeCycle', 'EvenSize', 0, $VertexID1, $VertexID2);
    2593 }
    2594
    2595 # Get number of cycles with specified size containing specified edge...
    2596 #
    2597 sub GetNumOfEdgeCyclesWithSize {
    2598   my($This, $VertexID1, $VertexID2, $CycleSize) = @_;
    2599
    2600   return $This->_GetNumOfCyclesWithSize('EdgeCycle', 'SpecifiedSize', $CycleSize, $VertexID1, $VertexID2);
    2601 }
    2602
    2603 # Get number of cycles with size less than specified size containing specified edge...
    2604 #
    2605 sub GetNumOfEdgeCyclesWithSizeLessThan {
    2606   my($This, $VertexID1, $VertexID2, $CycleSize) = @_;
    2607
    2608   return $This->_GetNumOfCyclesWithSize('EdgeCycle', 'SizeLessThan', $CycleSize, $VertexID1, $VertexID2);
    2609 }
    2610
    2611 # Get number of cycles with size greater than specified size containing specified edge...
    2612 #
    2613 sub GetNumOfEdgeCyclesWithSizeGreaterThan {
    2614   my($This, $VertexID1, $VertexID2, $CycleSize) = @_;
    2615
    2616   return $This->_GetNumOfCyclesWithSize('EdgeCycle', 'SizeGreaterThan', $CycleSize, $VertexID1, $VertexID2);
    2617 }
    2618
    2619 # Get smallest cycle containing specified edge...
    2620 #
    2621 sub GetSmallestEdgeCycle {
    2622   my($This, $VertexID1, $VertexID2) = @_;
    2623
    2624   return $This->_GetCycle('EdgeCycle', 'SmallestCycle', $VertexID1, $VertexID2);
    2625 }
    2626
    2627 # Get largest cycle containing specified edge...
    2628 #
    2629 sub GetLargestEdgeCycle {
    2630   my($This, $VertexID1, $VertexID2) = @_;
    2631
    2632   return $This->_GetCycle('EdgeCycle', 'LargestCycle', $VertexID1, $VertexID2);
    2633 }
    2634
    2635 # Get cycles containing specified edge...
    2636 #
    2637 sub GetEdgeCycles {
    2638   my($This, $VertexID1, $VertexID2) = @_;
    2639
    2640   return $This->_GetCyclesWithSize('EdgeCycle', 'AllSizes', 0, $VertexID1, $VertexID2);
    2641 }
    2642
    2643 # Get cycles with odd size containing specified edge...
    2644 #
    2645 sub GetEdgeCyclesWithOddSize {
    2646   my($This, $VertexID1, $VertexID2) = @_;
    2647
    2648   return $This->_GetCyclesWithSize('EdgeCycle', 'OddSize', 0, $VertexID1, $VertexID2);
    2649 }
    2650
    2651 # Get cycles with even size containing specified edge...
    2652 #
    2653 sub GetEdgeCyclesWithEvenSize {
    2654   my($This, $VertexID1, $VertexID2) = @_;
    2655
    2656   return $This->_GetCyclesWithSize('EdgeCycle', 'EvenSize', 0, $VertexID1, $VertexID2);
    2657 }
    2658
    2659 # Get cycles with specified size containing specified edge...
    2660 #
    2661 sub GetEdgeCyclesWithSize {
    2662   my($This, $VertexID1, $VertexID2, $CycleSize) = @_;
    2663
    2664   return $This->_GetCyclesWithSize('EdgeCycle', 'SpecifiedSize', $CycleSize, $VertexID1, $VertexID2);
    2665 }
    2666
    2667 # Get cycles with size less than specified size containing specified edge...
    2668 #
    2669 sub GetEdgeCyclesWithSizeLessThan {
    2670   my($This, $VertexID1, $VertexID2, $CycleSize) = @_;
    2671
    2672   return $This->_GetCyclesWithSize('EdgeCycle', 'SizeLessThan', $CycleSize, $VertexID1, $VertexID2);
    2673 }
    2674
    2675 # Get cycles with size greater than specified size containing specified edge...
    2676 #
    2677 sub GetEdgeCyclesWithSizeGreaterThan {
    2678   my($This, $VertexID1, $VertexID2, $CycleSize) = @_;
    2679
    2680   return $This->_GetCyclesWithSize('EdgeCycle', 'SizeGreaterThan', $CycleSize, $VertexID1, $VertexID2);
    2681 }
    2682
    2683 # Get size of specified cycle type...
    2684 #
    2685 sub _GetCycleSize {
    2686   my($This, $Mode, $CycleSize, $VertexID1, $VertexID2) = @_;
    2687   my($ActiveCyclicPathsRef, $CyclicPath, $Size);
    2688
    2689   if (!$This->HasGraphProperty('ActiveCyclicPaths')) {
    2690     return 0;
    2691   }
    2692   if ($Mode =~ /^VertexCycle$/i) {
    2693     if (!$This->HasVertexProperty('ActiveCyclicPaths', $VertexID1)) {
    2694       return 0;
    2695     }
    2696   }
    2697   elsif ($Mode =~ /^EdgeCycle$/i) {
    2698     if (!$This->HasEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2)) {
    2699       return 0;
    2700     }
    2701   }
    2702
    2703   MODE: {
    2704       if ($Mode =~ /^GraphCycle$/i) { $ActiveCyclicPathsRef = $This->GetGraphProperty('ActiveCyclicPaths'); last MODE; }
    2705       if ($Mode =~ /^VertexCycle$/i) { $ActiveCyclicPathsRef = $This->GetVertexProperty('ActiveCyclicPaths', $VertexID1); last MODE; }
    2706       if ($Mode =~ /^EdgeCycle$/i) { $ActiveCyclicPathsRef = $This->GetEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2); last MODE; }
    2707       return 0;
    2708   }
    2709
    2710   if (!@{$ActiveCyclicPathsRef}) {
    2711     return 0;
    2712   }
    2713
    2714   CYCLESIZE: {
    2715       if ($CycleSize =~ /^SmallestCycle$/i) { $CyclicPath = $ActiveCyclicPathsRef->[0]; last CYCLESIZE; }
    2716       if ($CycleSize =~ /^LargestCycle$/i) { $CyclicPath = $ActiveCyclicPathsRef->[$#{$ActiveCyclicPathsRef}]; last CYCLESIZE; }
    2717       return 0;
    2718   }
    2719   $Size = $CyclicPath->GetLength() - 1;
    2720
    2721   return $Size;
    2722 }
    2723
    2724 # Get of specified cycle size...
    2725 #
    2726 sub _GetCycle {
    2727   my($This, $Mode, $CycleSize, $VertexID1, $VertexID2) = @_;
    2728   my($ActiveCyclicPathsRef, $CyclicPath, $Size);
    2729
    2730   if (!$This->HasGraphProperty('ActiveCyclicPaths')) {
    2731     return $This->_GetEmptyCycles();
    2732   }
    2733   if ($Mode =~ /^VertexCycle$/i) {
    2734     if (!$This->HasVertexProperty('ActiveCyclicPaths', $VertexID1)) {
    2735       return $This->_GetEmptyCycles();
    2736     }
    2737   }
    2738   elsif ($Mode =~ /^EdgeCycle$/i) {
    2739     if (!$This->HasEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2)) {
    2740       return $This->_GetEmptyCycles();
    2741     }
    2742   }
    2743
    2744   MODE: {
    2745       if ($Mode =~ /^GraphCycle$/i) { $ActiveCyclicPathsRef = $This->GetGraphProperty('ActiveCyclicPaths'); last MODE; }
    2746       if ($Mode =~ /^VertexCycle$/i) { $ActiveCyclicPathsRef = $This->GetVertexProperty('ActiveCyclicPaths', $VertexID1); last MODE; }
    2747       if ($Mode =~ /^EdgeCycle$/i) { $ActiveCyclicPathsRef = $This->GetEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2); last MODE; }
    2748       return $This->_GetEmptyCycles();
    2749   }
    2750
    2751   if (!@{$ActiveCyclicPathsRef}) {
    2752     return $This->_GetEmptyCycles();
    2753   }
    2754
    2755   CYCLESIZE: {
    2756       if ($CycleSize =~ /^SmallestCycle$/i) { $CyclicPath = $ActiveCyclicPathsRef->[0]; last CYCLESIZE; }
    2757       if ($CycleSize =~ /^LargestCycle$/i) { $CyclicPath = $ActiveCyclicPathsRef->[$#{$ActiveCyclicPathsRef}]; last CYCLESIZE; }
    2758       return $This->_GetEmptyCycles();
    2759   }
    2760   return $CyclicPath;
    2761 }
    2762
    2763 # Get num of cycles in graph...
    2764 #
    2765 sub _GetNumOfCyclesWithSize {
    2766   my($This, $Mode, $SizeMode, $SpecifiedSize, $VertexID1, $VertexID2) = @_;
    2767   my($ActiveCyclicPathsRef);
    2768
    2769   if (!$This->HasGraphProperty('ActiveCyclicPaths')) {
    2770     return 0;
    2771   }
    2772   if ($Mode =~ /^VertexCycle$/i) {
    2773     if (!$This->HasVertexProperty('ActiveCyclicPaths', $VertexID1)) {
    2774       return 0;
    2775     }
    2776   }
    2777   elsif ($Mode =~ /^EdgeCycle$/i) {
    2778     if (!$This->HasEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2)) {
    2779       return 0;
    2780     }
    2781   }
    2782
    2783   if ($SizeMode =~ /^(SizeLessThan|SizeGreaterThan|SpecifiedSize)$/i) {
    2784     if (!defined $SpecifiedSize) {
    2785       carp "Warning: ${ClassName}->_GetNumOfCyclesWithSize: Cycle size muse be defined...";
    2786       return 0;
    2787     }
    2788     if ($SpecifiedSize < 0) {
    2789       carp "Warning: ${ClassName}->_GetNumOfCyclesWithSize: Specified cycle size, $SpecifiedSize, must be > 0 ...";
    2790       return 0;
    2791     }
    2792   }
    2793
    2794   MODE: {
    2795       if ($Mode =~ /^GraphCycle$/i) { $ActiveCyclicPathsRef = $This->GetGraphProperty('ActiveCyclicPaths'); last MODE; }
    2796       if ($Mode =~ /^VertexCycle$/i) { $ActiveCyclicPathsRef = $This->GetVertexProperty('ActiveCyclicPaths', $VertexID1); last MODE; }
    2797       if ($Mode =~ /^EdgeCycle$/i) { $ActiveCyclicPathsRef = $This->GetEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2); last MODE; }
    2798       return 0;
    2799   }
    2800
    2801   if (!@{$ActiveCyclicPathsRef}) {
    2802     return 0;
    2803   }
    2804   my($NumOfCycles);
    2805
    2806   $NumOfCycles = $This->_GetCycles($Mode, $ActiveCyclicPathsRef, $SizeMode, $SpecifiedSize);
    2807
    2808   return $NumOfCycles;
    2809 }
    2810
    2811 # Get cycles in graph...
    2812 #
    2813 sub _GetCyclesWithSize {
    2814   my($This, $Mode, $SizeMode, $SpecifiedSize, $VertexID1, $VertexID2) = @_;
    2815   my($ActiveCyclicPathsRef);
    2816
    2817   if (!$This->HasGraphProperty('ActiveCyclicPaths')) {
    2818     return $This->_GetEmptyCycles();
    2819   }
    2820   if ($Mode =~ /^VertexCycle$/i) {
    2821     if (!$This->HasVertexProperty('ActiveCyclicPaths', $VertexID1)) {
    2822       return $This->_GetEmptyCycles();
    2823     }
    2824   }
    2825   elsif ($Mode =~ /^EdgeCycle$/i) {
    2826     if (!$This->HasEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2)) {
    2827       return $This->_GetEmptyCycles();
    2828     }
    2829   }
    2830
    2831   if ($SizeMode =~ /^(SizeLessThan|SizeGreaterThan|SpecifiedSize)$/i) {
    2832     if (!defined $SpecifiedSize) {
    2833       carp "Warning: ${ClassName}->_GetCyclesWithSize: Cycle size must be defined...";
    2834       return $This->_GetEmptyCycles();
    2835     }
    2836     if ($SpecifiedSize < 0) {
    2837       carp "Warning: ${ClassName}->_GetCyclesWithSize: Specified cycle size, $SpecifiedSize, must be > 0 ...";
    2838       return $This->_GetEmptyCycles();
    2839     }
    2840   }
    2841
    2842   MODE: {
    2843       if ($Mode =~ /^GraphCycle$/i) { $ActiveCyclicPathsRef = $This->GetGraphProperty('ActiveCyclicPaths'); last MODE; }
    2844       if ($Mode =~ /^VertexCycle$/i) { $ActiveCyclicPathsRef = $This->GetVertexProperty('ActiveCyclicPaths', $VertexID1); last MODE; }
    2845       if ($Mode =~ /^EdgeCycle$/i) { $ActiveCyclicPathsRef = $This->GetEdgeProperty('ActiveCyclicPaths', $VertexID1, $VertexID2); last MODE; }
    2846       return $This->_GetEmptyCycles();
    2847     }
    2848
    2849   if (!@{$ActiveCyclicPathsRef}) {
    2850     return $This->_GetEmptyCycles();
    2851   }
    2852   return $This->_GetCycles($Mode, $ActiveCyclicPathsRef, $SizeMode, $SpecifiedSize);
    2853 }
    2854
    2855 # Get cycles information...
    2856 #
    2857 sub _GetCycles {
    2858   my($This, $Mode, $ActiveCyclicPathsRef, $SizeMode, $SpecifiedSize) = @_;
    2859
    2860   if (!@{$ActiveCyclicPathsRef}) {
    2861     return $This->_GetEmptyCycles();
    2862   }
    2863
    2864   if ($SizeMode =~ /^AllSizes$/i) {
    2865     return wantarray ? @{$ActiveCyclicPathsRef} : scalar @{$ActiveCyclicPathsRef};
    2866   }
    2867
    2868   # Get appropriate cycles...
    2869   my($Size, $CyclicPath, @FilteredCyclicPaths);
    2870   @FilteredCyclicPaths = ();
    2871
    2872   for $CyclicPath (@{$ActiveCyclicPathsRef}) {
    2873     $Size = $CyclicPath->GetLength() - 1;
    2874     SIZEMODE: {
    2875       if ($SizeMode =~ /^OddSize$/i) { if ($Size % 2) { push @FilteredCyclicPaths, $CyclicPath; } last SIZEMODE; }
    2876       if ($SizeMode =~ /^EvenSize$/i) { if (!($Size % 2)) { push @FilteredCyclicPaths, $CyclicPath; } last SIZEMODE; }
    2877       if ($SizeMode =~ /^SizeLessThan$/i) { if ($Size < $SpecifiedSize) { push @FilteredCyclicPaths, $CyclicPath; } last SIZEMODE; }
    2878       if ($SizeMode =~ /^SizeGreaterThan$/i) { if ($Size > $SpecifiedSize) { push @FilteredCyclicPaths, $CyclicPath; } last SIZEMODE; }
    2879       if ($SizeMode =~ /^SpecifiedSize$/i) { if ($Size == $SpecifiedSize) { push @FilteredCyclicPaths, $CyclicPath; } last SIZEMODE; }
    2880       return undef;
    2881     }
    2882   }
    2883   return wantarray ? @FilteredCyclicPaths : scalar @FilteredCyclicPaths;
    2884 }
    2885
    2886 # Return empty cyles array...
    2887 #
    2888 sub _GetEmptyCycles {
    2889   my($This) = @_;
    2890   my(@CyclicPaths);
    2891
    2892   @CyclicPaths = ();
    2893
    2894   return wantarray ? @CyclicPaths : scalar @CyclicPaths;
    2895 }
    2896
    2897 # Does graph contains fused cycles?
    2898 sub HasFusedCycles {
    2899   my($This) = @_;
    2900
    2901   return ($This->HasGraphProperty('FusedActiveCyclicPaths')) ? 1 : 0;
    2902 }
    2903
    2904 # Return a reference to fused cycle sets lists containing references to lists of cyclic path objects
    2905 # in each fused cycle set and a reference to a list containing non-fused cyclic paths...
    2906 #
    2907 sub GetFusedAndNonFusedCycles {
    2908   my($This) = @_;
    2909   my($FusedCycleSetsRef, $NonFusedCyclesRef);
    2910
    2911   $FusedCycleSetsRef = $This->HasGraphProperty('FusedActiveCyclicPaths') ? $This->GetGraphProperty('FusedActiveCyclicPaths') : undef;
    2912   $NonFusedCyclesRef = $This->HasGraphProperty('NonFusedActiveCyclicPaths') ? $This->GetGraphProperty('NonFusedActiveCyclicPaths') : undef;
    2913
    2914   return ($FusedCycleSetsRef, $NonFusedCyclesRef);
    2915 }
    2916
    2917 # Get vertices of connected components as a list containing references to
    2918 # lists of vertices for each component  sorted in order of its decreasing size...
    2919 #
    2920 sub GetConnectedComponentsVertices {
    2921   my($This) = @_;
    2922   my($PathsTraversal);
    2923
    2924   $PathsTraversal = new Graph::PathsTraversal($This);
    2925   $PathsTraversal->PerformDepthFirstSearch();
    2926
    2927   return $PathsTraversal->GetConnectedComponentsVertices();
    2928 }
    2929
    2930 # Get a list of topologically sorted vertrices starting from a specified vertex or
    2931 # an arbitrary vertex in the graph...
    2932 #
    2933 sub GetTopologicallySortedVertices {
    2934   my($This, $RootVertexID) = @_;
    2935   my($PathsTraversal);
    2936
    2937   $PathsTraversal = new Graph::PathsTraversal($This);
    2938   $PathsTraversal->PerformBreadthFirstSearch($RootVertexID);
    2939
    2940   return $PathsTraversal->GetVertices();
    2941 }
    2942
    2943 # Get a list of paths starting from a specified vertex with length upto specified length
    2944 # and no sharing of edges in paths traversed. By default, cycles are included in paths.
    2945 # A path containing a cycle is terminated at a vertex completing the cycle.
    2946 #
    2947 sub GetPathsStartingAtWithLengthUpto {
    2948   my($This, $StartVertexID, $Length, $AllowCycles) = @_;
    2949   my($PathsTraversal);
    2950
    2951   $PathsTraversal = new Graph::PathsTraversal($This);
    2952   $PathsTraversal->PerformPathsSearchWithLengthUpto($StartVertexID, $Length, $AllowCycles);
    2953
    2954   return $PathsTraversal->GetPaths();
    2955 }
    2956
    2957 # Get a list of paths starting from a specified vertex with specified length
    2958 # and no sharing of edges in paths traversed. By default, cycles are included in paths.
    2959 # A path containing a cycle is terminated at a vertex completing the cycle.
    2960 #
    2961 sub GetPathsStartingAtWithLength {
    2962   my($This, $StartVertexID, $Length, $AllowCycles) = @_;
    2963   my($PathsTraversal);
    2964
    2965   $PathsTraversal = new Graph::PathsTraversal($This);
    2966   $PathsTraversal->PerformPathsSearchWithLength($StartVertexID, $Length, $AllowCycles);
    2967
    2968   return $PathsTraversal->GetPaths();
    2969 }
    2970
    2971 # Get a list of paths with all possible lengths starting from a specified vertex
    2972 # with no sharing of edges in paths traversed. By default, cycles are included in paths.
    2973 # A path containing a cycle is terminated at a vertex completing the cycle.
    2974 #
    2975 sub GetPathsStartingAt {
    2976   my($This, $StartVertexID, $AllowCycles) = @_;
    2977   my($PathsTraversal);
    2978
    2979   $PathsTraversal = new Graph::PathsTraversal($This);
    2980   $PathsTraversal->PerformPathsSearch($StartVertexID, $AllowCycles);
    2981
    2982   return $PathsTraversal->GetPaths();
    2983 }
    2984
    2985 # Get a list of all paths starting from a specified vertex with length upto a specified length
    2986 # with sharing of edges in paths traversed. By default, cycles are included in paths.
    2987 # A path containing a cycle is terminated at a vertex completing the cycle.
    2988 #
    2989 sub GetAllPathsStartingAtWithLengthUpto {
    2990   my($This, $StartVertexID, $Length, $AllowCycles) = @_;
    2991   my($PathsTraversal);
    2992
    2993   $PathsTraversal = new Graph::PathsTraversal($This);
    2994   $PathsTraversal->PerformAllPathsSearchWithLengthUpto($StartVertexID, $Length, $AllowCycles);
    2995
    2996   return $PathsTraversal->GetPaths();
    2997 }
    2998
    2999 # Get a list of all paths starting from a specified vertex with specified length
    3000 # with sharing of edges in paths traversed. By default, cycles are included in paths.
    3001 # A path containing a cycle is terminated at a vertex completing the cycle.
    3002 #
    3003 sub GetAllPathsStartingAtWithLength {
    3004   my($This, $StartVertexID, $Length, $AllowCycles) = @_;
    3005   my($PathsTraversal);
    3006
    3007   $PathsTraversal = new Graph::PathsTraversal($This);
    3008   $PathsTraversal->PerformAllPathsSearchWithLength($StartVertexID, $Length, $AllowCycles);
    3009
    3010   return $PathsTraversal->GetPaths();
    3011 }
    3012
    3013
    3014 # Get a list of all paths with all possible lengths starting from a specified vertex
    3015 # with sharing of edges in paths traversed. By default, cycles are included in paths.
    3016 # A path containing a cycle is terminated at a vertex completing the cycle.
    3017 #
    3018 sub GetAllPathsStartingAt {
    3019   my($This, $StartVertexID, $AllowCycles) = @_;
    3020   my($PathsTraversal);
    3021
    3022   $PathsTraversal = new Graph::PathsTraversal($This);
    3023   $PathsTraversal->PerformAllPathsSearch($StartVertexID, $AllowCycles);
    3024
    3025   return $PathsTraversal->GetPaths();
    3026 }
    3027
    3028 # Get a reference to list of paths starting from each vertex in graph with length upto specified
    3029 # length and no sharing of edges in paths traversed. By default, cycles are included in paths.
    3030 # A path containing a cycle is terminated at a vertex completing the cycle.
    3031 #
    3032 sub GetPathsWithLengthUpto {
    3033   my($This, $Length, $AllowCycles) = @_;
    3034
    3035   $AllowCycles = (defined $AllowCycles) ? $AllowCycles : 1;
    3036
    3037   return $This->_GetPaths('PathsWithLengthUpto', $Length, $AllowCycles);
    3038 }
    3039
    3040 # Get a reference to list of paths starting from each vertex in graph with specified
    3041 # length and no sharing of edges in paths traversed. By default, cycles are included in paths.
    3042 # A path containing a cycle is terminated at a vertex completing the cycle.
    3043 #
    3044 sub GetPathsWithLength {
    3045   my($This, $Length, $AllowCycles) = @_;
    3046
    3047   $AllowCycles = (defined $AllowCycles) ? $AllowCycles : 1;
    3048
    3049   return $This->_GetPaths('PathsWithLength', $Length, $AllowCycles);
    3050 }
    3051
    3052 # Get a reference to list of paths with all possible lengths starting from each vertex
    3053 # with no sharing of edges in paths traversed. By default, cycles are included in paths.
    3054 # A path containing a cycle is terminated at a vertex completing the cycle.
    3055 #
    3056 #
    3057 sub GetPaths {
    3058   my($This, $AllowCycles) = @_;
    3059
    3060   $AllowCycles = (defined $AllowCycles) ? $AllowCycles : 1;
    3061
    3062   return $This->_GetPaths('PathsWithAllLengths', undef, $AllowCycles);
    3063 }
    3064
    3065 # Get a reference to list of all paths starting from each vertex in graph with length upto a specified
    3066 # length with sharing of edges in paths traversed. By default, cycles are included in paths. A path
    3067 # containing a cycle is terminated at a vertex completing the cycle.
    3068 #
    3069 # Note:
    3070 #   . Duplicate paths are not removed.
    3071 #
    3072 sub GetAllPathsWithLengthUpto {
    3073   my($This, $Length, $AllowCycles) = @_;
    3074
    3075   $AllowCycles = (defined $AllowCycles) ? $AllowCycles : 1;
    3076
    3077   return $This->_GetPaths('AllPathsWithLengthUpto', $Length, $AllowCycles);
    3078 }
    3079
    3080 # Get a reference to list of all paths starting from each vertex in graph with specified
    3081 # length with sharing of edges in paths traversed. By default, cycles are included in paths. A path
    3082 # containing a cycle is terminated at a vertex completing the cycle.
    3083 #
    3084 # Note:
    3085 #   . Duplicate paths are not removed.
    3086 #
    3087 sub GetAllPathsWithLength {
    3088   my($This, $Length, $AllowCycles) = @_;
    3089
    3090   $AllowCycles = (defined $AllowCycles) ? $AllowCycles : 1;
    3091
    3092   return $This->_GetPaths('AllPathsWithLength', $Length, $AllowCycles);
    3093 }
    3094
    3095 # Get a reference to list of all paths with all possible lengths starting from each vertex in graph
    3096 # with sharing of edges in paths traversed. By default, cycles are included in paths. A path
    3097 # containing a cycle is terminated at a vertex completing the cycle.
    3098 #
    3099 # Note:
    3100 #   . Duplicate paths are not removed.
    3101 #
    3102 sub GetAllPaths {
    3103   my($This, $AllowCycles) = @_;
    3104
    3105   $AllowCycles = (defined $AllowCycles) ? $AllowCycles : 1;
    3106
    3107   return $This->_GetPaths('AllPathsWithAllLengths', undef, $AllowCycles);
    3108 }
    3109
    3110
    3111 # Retrieve appropriate paths for each vertex in graph and return a referernce to list
    3112 # containing path objects...
    3113 #
    3114 sub _GetPaths {
    3115   my($This, $Mode, $Length, $AllowCycles) = @_;
    3116   my($VertexID, @EmptyPaths, @Paths);
    3117
    3118   @Paths = (); @EmptyPaths = ();
    3119
    3120   for $VertexID ($This->GetVertices()) {
    3121     my($Status, $PathsTraversal);
    3122
    3123     $PathsTraversal = new Graph::PathsTraversal($This);
    3124     MODE: {
    3125       if ($Mode =~ /^PathsWithLengthUpto$/i) { $Status = $PathsTraversal->PerformPathsSearchWithLengthUpto($VertexID, $Length, $AllowCycles); last MODE; }
    3126       if ($Mode =~ /^PathsWithLength$/i) { $Status = $PathsTraversal->PerformPathsSearchWithLength($VertexID, $Length, $AllowCycles); last MODE; }
    3127       if ($Mode =~ /^PathsWithAllLengths$/i) { $Status = $PathsTraversal->PerformPathsSearch($VertexID, $AllowCycles); last MODE; }
    3128
    3129       if ($Mode =~ /^AllPathsWithLengthUpto$/i) { $Status = $PathsTraversal->PerformAllPathsSearchWithLengthUpto($VertexID, $Length, $AllowCycles); last MODE; }
    3130       if ($Mode =~ /^AllPathsWithLength$/i) { $Status = $PathsTraversal->PerformAllPathsSearchWithLength($VertexID, $Length, $AllowCycles); last MODE; }
    3131       if ($Mode =~ /^AllPathsWithAllLengths$/i) { $Status = $PathsTraversal->PerformAllPathsSearch($VertexID, $AllowCycles); last MODE; }
    3132
    3133       return \@EmptyPaths;
    3134     }
    3135     if (!defined $Status) {
    3136       return \@EmptyPaths;
    3137     }
    3138     push @Paths, $PathsTraversal->GetPaths();
    3139   }
    3140   return \@Paths;
    3141 }
    3142
    3143 # Get a list of paths between two vertices. For cyclic graphs, the list contains
    3144 # may contain two paths...
    3145 #
    3146 sub GetPathsBetween {
    3147   my($This, $StartVertexID, $EndVertexID) = @_;
    3148   my($Path, $ReversePath, @Paths);
    3149
    3150   @Paths = ();
    3151
    3152   $Path = $This->_GetPathBetween($StartVertexID, $EndVertexID);
    3153   if (!defined $Path) {
    3154     return \@Paths;
    3155   }
    3156
    3157   $ReversePath = $This->_GetPathBetween($EndVertexID, $StartVertexID);
    3158   if (!defined $ReversePath) {
    3159     return \@Paths;
    3160   }
    3161   if ($Path eq $ReversePath) {
    3162     push @Paths, $Path;
    3163   }
    3164   else {
    3165     # Make sure first vertex in reverse path corresponds to specified start vertex ID...
    3166     $ReversePath->Reverse();
    3167     push @Paths, ($Path->GetLength <= $ReversePath->GetLength()) ? ($Path, $ReversePath) : ($ReversePath, $Path);
    3168   }
    3169   return @Paths;
    3170 }
    3171
    3172 # Get a path beween two vertices...
    3173 #
    3174 sub _GetPathBetween {
    3175   my($This, $StartVertexID, $EndVertexID) = @_;
    3176   my($PathsTraversal,  @Paths);
    3177
    3178   $PathsTraversal = new Graph::PathsTraversal($This);
    3179   $PathsTraversal->PerformPathsSearchBetween($StartVertexID, $EndVertexID);
    3180
    3181   @Paths = $PathsTraversal->GetPaths();
    3182
    3183   return (@Paths) ? $Paths[0] : undef;
    3184 }
    3185
    3186 # Get a list containing lists of neighborhood vertices around a specified vertex with in a
    3187 # specified radius...
    3188 #
    3189 sub GetNeighborhoodVerticesWithRadiusUpto {
    3190   my($This, $StartVertexID, $Radius) = @_;
    3191   my($PathsTraversal);
    3192
    3193   $PathsTraversal = new Graph::PathsTraversal($This);
    3194   $PathsTraversal->PerformNeighborhoodVerticesSearchWithRadiusUpto($StartVertexID, $Radius);
    3195
    3196   return $PathsTraversal->GetVerticesNeighborhoods();
    3197 }
    3198
    3199 # Get a list containing lists of neighborhood vertices around a specified vertex at all
    3200 # radii levels...
    3201 #
    3202 sub GetNeighborhoodVertices {
    3203   my($This, $StartVertexID) = @_;
    3204   my($PathsTraversal);
    3205
    3206   $PathsTraversal = new Graph::PathsTraversal($This);
    3207   $PathsTraversal->PerformNeighborhoodVerticesSearch($StartVertexID);
    3208
    3209   return $PathsTraversal->GetVerticesNeighborhoods();
    3210 }
    3211
    3212 # Get neighborhood vertices around a specified vertex, along with their successor connected vertices, collected
    3213 # with in a specified radius as a list containing references to lists with first value corresponding to vertex
    3214 # ID and second value as reference to a list containing its successor connected vertices.
    3215 #
    3216 # For a neighborhood vertex at each radius level, the successor connected vertices correspond to the
    3217 # neighborhood vertices at the next radius level. Consequently, the neighborhood vertices at the last
    3218 # radius level don't contain any successor vertices which fall outside the range of specified radius.
    3219 #
    3220 sub GetNeighborhoodVerticesWithSuccessorsAndRadiusUpto {
    3221   my($This, $StartVertexID, $Radius) = @_;
    3222   my($PathsTraversal);
    3223
    3224   $PathsTraversal = new Graph::PathsTraversal($This);
    3225   $PathsTraversal->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto($StartVertexID, $Radius);
    3226
    3227   return $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
    3228 }
    3229
    3230 # Get neighborhood vertices around a specified vertex, along with their successor connected vertices, collected
    3231 # at all neighborhood radii as a list containing references to lists with first value corresponding to vertex
    3232 # ID and second value as reference to a list containing its successor connected vertices.
    3233 #
    3234 # For a neighborhood vertex at each radius level, the successor connected vertices correspond to the
    3235 # neighborhood vertices at the next radius level. Consequently, the neighborhood vertices at the last
    3236 # radius level don't contain any successor vertices which fall outside the range of specified radius.
    3237 #
    3238 sub GetNeighborhoodVerticesWithSuccessors {
    3239   my($This, $StartVertexID) = @_;
    3240   my($PathsTraversal);
    3241
    3242   $PathsTraversal = new Graph::PathsTraversal($This);
    3243   $PathsTraversal->PerformNeighborhoodVerticesSearchWithSuccessors($StartVertexID);
    3244
    3245   return $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
    3246 }
    3247
    3248 # Get adjacency matrix for the graph as a Matrix object with row and column indices
    3249 # corresponding to graph vertices returned by GetVertices method.
    3250 #
    3251 # For a simple graph G with n vertices, the adjacency matrix for G is a n x n square matrix and
    3252 # its elements Mij are:
    3253 #
    3254 #   . 0    if i == j
    3255 #   . 1    if i != j and vertex Vi is adjacent to vertex Vj
    3256 #   . 0    if i != j and vertex Vi is not adjacent to vertex Vj
    3257 #
    3258 sub GetAdjacencyMatrix {
    3259   my($This) = @_;
    3260   my($GraphMatrix);
    3261
    3262   $GraphMatrix = new Graph::GraphMatrix($This);
    3263   $GraphMatrix->GenerateAdjacencyMatrix();
    3264
    3265   return $GraphMatrix->GetMatrix();
    3266 }
    3267
    3268 # Get Siedel adjacency matrix for the graph as a Matrix object with row and column indices
    3269 # corresponding to graph vertices returned by GetVertices method.
    3270 #
    3271 # For a simple graph G with n vertices, the Siedal adjacency matrix for G is a n x n square matrix and
    3272 # its elements Mij are:
    3273 #
    3274 #   . 0    if i == j
    3275 #   . -1   if i != j and vertex Vi is adjacent to vertex Vj
    3276 #   . 1    if i != j and vertex Vi is not adjacent to vertex Vj
    3277 #
    3278 sub GetSiedelAdjacencyMatrix {
    3279   my($This) = @_;
    3280   my($GraphMatrix);
    3281
    3282   $GraphMatrix = new Graph::GraphMatrix($This);
    3283   $GraphMatrix->GenerateSiedelAdjacencyMatrix();
    3284
    3285   return $GraphMatrix->GetMatrix();
    3286 }
    3287
    3288 # Get distance matrix for the graph as a Matrix object with row and column indices
    3289 # corresponding to graph vertices returned by GetVertices method.
    3290 #
    3291 # For a simple graph G with n vertices, the distance matrix for G is a n x n square matrix and
    3292 # its elements Mij are:
    3293 #
    3294 #   . 0    if i == j
    3295 #   . d    if i != j and d is the shortest distance between vertex Vi and vertex Vj
    3296 #
    3297 # Note:
    3298 #   . In the final matrix, BigNumber values correspond to vertices with no edges.
    3299 #
    3300 sub GetDistanceMatrix {
    3301   my($This) = @_;
    3302   my($GraphMatrix);
    3303
    3304   $GraphMatrix = new Graph::GraphMatrix($This);
    3305   $GraphMatrix->GenerateDistanceMatrix();
    3306
    3307   return $GraphMatrix->GetMatrix();
    3308 }
    3309
    3310 # Get incidence matrix for the graph as a Matrix object with row and column indices
    3311 # corresponding to graph vertices and edges returned by GetVertices and GetEdges
    3312 # methods respectively.
    3313 #
    3314 # For a simple graph G with n vertices and e edges, the incidence matrix for G is a n x e matrix
    3315 # its elements Mij are:
    3316 #
    3317 #   . 1    if vertex Vi and the edge Ej are incident; in other words, Vi and Ej are related
    3318 #   . 0    otherwise
    3319 #
    3320 sub GetIncidenceMatrix {
    3321   my($This) = @_;
    3322   my($GraphMatrix);
    3323
    3324   $GraphMatrix = new Graph::GraphMatrix($This);
    3325   $GraphMatrix->GenerateIncidenceMatrix();
    3326
    3327   return $GraphMatrix->GetMatrix();
    3328 }
    3329
    3330 # Get degree matrix for the graph as a Matrix object with row and column indices
    3331 # corresponding to graph vertices returned by GetVertices method.
    3332 #
    3333 # For a simple graph G with n vertices, the degree matrix for G is a n x n square matrix and
    3334 # its elements Mij are:
    3335 #
    3336 #   . deg(Vi)   if i == j and deg(Vi) is the degree of vertex Vi
    3337 #   . 0         otherwise
    3338 #
    3339 sub GetDegreeMatrix {
    3340   my($This) = @_;
    3341   my($GraphMatrix);
    3342
    3343   $GraphMatrix = new Graph::GraphMatrix($This);
    3344   $GraphMatrix->GenerateDegreeMatrix();
    3345
    3346   return $GraphMatrix->GetMatrix();
    3347 }
    3348
    3349 # Get Laplacian matrix for the graph as a Matrix object with row and column indices
    3350 # corresponding to graph vertices returned by GetVertices method.
    3351 #
    3352 # For a simple graph G with n vertices, the Laplacian matrix for G is a n x n square matrix and
    3353 # its elements Mij are:
    3354 #
    3355 #   . deg(Vi)   if i == j and deg(Vi) is the degree of vertex Vi
    3356 #   . -1        if i != j and vertex Vi is adjacent to vertex Vj
    3357 #   . 0         otherwise
    3358 #
    3359 # Note: The Laplacian matrix is the difference between the degree matrix and adjacency matrix.
    3360 #
    3361 sub GetLaplacianMatrix {
    3362   my($This) = @_;
    3363   my($GraphMatrix);
    3364
    3365   $GraphMatrix = new Graph::GraphMatrix($This);
    3366   $GraphMatrix->GenerateLaplacianMatrix();
    3367
    3368   return $GraphMatrix->GetMatrix();
    3369 }
    3370
    3371 # Get normalized Laplacian matrix for the graph as a Matrix object with row and column indices
    3372 # corresponding to graph vertices returned by GetVertices method.
    3373 #
    3374 # For a simple graph G with n vertices, the normalized Laplacian matrix L for G is a n x n square matrix and
    3375 # its elements Lij are:
    3376 #
    3377 #   . 1                           if i == j and deg(Vi) != 0
    3378 #   . -1/SQRT(deg(Vi) * deg(Vj))  if i != j and vertex Vi is adjacent to vertex Vj
    3379 #   . 0                           otherwise
    3380 #
    3381 #
    3382 sub GetNormalizedLaplacianMatrix {
    3383   my($This) = @_;
    3384   my($GraphMatrix);
    3385
    3386   $GraphMatrix = new Graph::GraphMatrix($This);
    3387   $GraphMatrix->GenerateNormalizedLaplacianMatrix();
    3388
    3389   return $GraphMatrix->GetMatrix();
    3390 }
    3391
    3392 # Get admittance matrix for the graph as a Matrix object with row and column indices
    3393 # corresponding to graph vertices returned by GetVertices method.
    3394 #
    3395 sub GetAdmittanceMatrix {
    3396   my($This) = @_;
    3397
    3398   return $This->GetLaplacianMatrix();
    3399 }
    3400
    3401 # Get Kirchhoff matrix for the graph as a Matrix object with row and column indices
    3402 # corresponding to graph vertices returned by GetVertices method.
    3403 #
    3404 sub GetKirchhoffMatrix {
    3405   my($This) = @_;
    3406
    3407   return $This->GetLaplacianMatrix();
    3408 }
    3409