1 package Graph;
   2 #
   3 # File: Graph.pm
   4 # Author: Manish Sud <msud@san.rr.com>
   5 #
   6 # Copyright (C) 2024 Manish Sud. All rights reserved.
   7 #
   8 # This file is part of MayaChemTools.
   9 #
  10 # MayaChemTools is free software; you can redistribute it and/or modify it under
  11 # the terms of the GNU Lesser General Public License as published by the Free
  12 # Software Foundation; either version 3 of the License, or (at your option) any
  13 # later version.
  14 #
  15 # MayaChemTools is distributed in the hope that it will be useful, but without
  16 # any warranty; without even the implied warranty of merchantability of fitness
  17 # for a particular purpose.  See the GNU Lesser General Public License for more
  18 # details.
  19 #
  20 # You should have received a copy of the GNU Lesser General Public License
  21 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
  22 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
  23 # Boston, MA, 02111-1307, USA.
  24 #
  25 
  26 use strict;
  27 use Carp;
  28 use Exporter;
  29 use 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