annotate mayachemtools/lib/Graph/PathGraph.pm @ 9:ab29fa5c8c1f draft default tip

Uploaded
author deepakjadmin
date Thu, 15 Dec 2016 14:18:03 -0500
parents 73ae111cf86f
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
1 package Graph::PathGraph;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
2 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
3 # $RCSfile: PathGraph.pm,v $
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
4 # $Date: 2015/02/28 20:49:06 $
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
5 # $Revision: 1.24 $
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
6 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
7 # Author: Manish Sud <msud@san.rr.com>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
8 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
9 # Copyright (C) 2015 Manish Sud. All rights reserved.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
10 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
11 # This file is part of MayaChemTools.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
12 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
13 # MayaChemTools is free software; you can redistribute it and/or modify it under
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
14 # the terms of the GNU Lesser General Public License as published by the Free
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
15 # Software Foundation; either version 3 of the License, or (at your option) any
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
16 # later version.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
17 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
18 # MayaChemTools is distributed in the hope that it will be useful, but without
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
19 # any warranty; without even the implied warranty of merchantability of fitness
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
20 # for a particular purpose. See the GNU Lesser General Public License for more
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
21 # details.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
22 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
23 # You should have received a copy of the GNU Lesser General Public License
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
24 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
25 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
26 # Boston, MA, 02111-1307, USA.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
27 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
28
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
29 use strict;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
30 use Carp;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
31 use Exporter;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
32 use Storable ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
33 use Scalar::Util ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
34 use Graph;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
35 use Graph::Path;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
36
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
37 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
38
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
39 @ISA = qw(Graph Exporter);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
40 @EXPORT = qw(IsPathGraph);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
41 @EXPORT_OK = qw();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
42
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
43 %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
44
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
45 # Setup class variables...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
46 my($ClassName, $PathsPropertyName, $CyclicPathsPropertyName);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
47 _InitializeClass();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
48
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
49 # Overload Perl functions...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
50 use overload '""' => 'StringifyPathGraph';
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
51
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
52 # Class constructor...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
53 sub new {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
54 my($Class, $Graph) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
55
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
56 # Initialize object...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
57 my $This = $Class->SUPER::new();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
58 bless $This, ref($Class) || $Class;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
59 $This->_InitializePathGraph($Graph);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
60
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
61 $This->_ConvertGraphIntoPathGraph($Graph);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
62
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
63 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
64 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
65
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
66 # Initialize object data...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
67 sub _InitializePathGraph {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
68 my($This, $Graph) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
69
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
70 if (!(defined($Graph) && Graph::IsGraph($Graph))) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
71 croak "Error: ${ClassName}->new: PathGraph object can't be instantiated without a Graph object...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
72 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
73
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
74 $This->{Graph} = $Graph;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
75
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
76 # Maximum time allowed for cycles detection during collapse vertex cycles detection
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
77 # methodology in seconds...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
78 $This->{MaxAllowedTime} = 30;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
79
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
80 # Starting time for cycles detection during collapse vertex cycles detection
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
81 # methodology...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
82 $This->{StartTime} = time;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
83
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
84 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
85 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
86
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
87 # Initialize class ...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
88 sub _InitializeClass {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
89 #Class name...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
90 $ClassName = __PACKAGE__;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
91
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
92 # Path edge property name...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
93 $PathsPropertyName = 'Paths';
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
94
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
95 # Cyclic path vertex property name...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
96 $CyclicPathsPropertyName = 'CyclicPaths';
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
97 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
98
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
99 # Convert graph into a path graph...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
100 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
101 sub _ConvertGraphIntoPathGraph {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
102 my($This, $Graph) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
103
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
104 # Copy graph vertices and edges without any associated properties data
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
105 # from Graph to This: Graph properties data is available using Graph object reference
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
106 # store in This object...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
107 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
108 $Graph->CopyVerticesAndEdges($This);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
109
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
110 # . Attach Path property to each edge...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
111 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
112 my($Index, $VertexID1, $VertexID2, $Path, @EdgesVertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
113
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
114 @EdgesVertexIDs = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
115 @EdgesVertexIDs = $This->GetEdges();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
116 for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
117 $VertexID1 = $EdgesVertexIDs[$Index]; $VertexID2 = $EdgesVertexIDs[$Index + 1];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
118 $Path = new Graph::Path($VertexID1, $VertexID2);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
119 my(@Paths) = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
120 push @Paths, $Path;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
121 $This->SetEdgeProperty($PathsPropertyName, \@Paths, $VertexID1, $VertexID2);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
122 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
123 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
124 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
125
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
126 # Collapse paths around a specified vertex by updating paths around the vertex
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
127 # and adding any resulting cyclic paths to vertices attached to specified vertex.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
128 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
129 # Notes:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
130 # . Path object references are stored as a list attached to Paths property on edges.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
131 # Usage of list allows multiple paths attached to the egde between a pair of vertices;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
132 # Graph doesn't support multiple egdes between a pair of vertices.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
133 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
134 # . Cyclic path object references are stored as list on vertices as CyclicPaths graph property.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
135 # List allows multiple Loop properties attached to a vertex.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
136 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
137 # . For topologically complex graphs containing large number of cycles, cycles detection algorithm
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
138 # [ Ref 31 ] as implemented implemented in CollapseVertexAndCollectCyclicPathsDetectCycles
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
139 # might not be able to find all the cycles in a reasonable amount of time and is designed to
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
140 # abandon cycles detection after MaxAllowedTime. Consequently, no cycles are detected
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
141 # or assigned.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
142 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
143 sub CollapseVertexAndCollectCyclicPaths {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
144 my($This, $VertexID) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
145
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
146 if (!$This->HasVertex($VertexID)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
147 carp "Warning: ${ClassName}->CollapseVertexAndCollectCyclicPaths: Didn't collapse vertex $VertexID: Vertex $VertexID doesn't exist...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
148 return undef;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
149 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
150 # Collect all paths around specified VertexID by going over paths associated with its edges...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
151 my($Index, $EdgePathsRef, $EdgeVertexID1, $EdgeVertexID2, @Paths, @EdgesVertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
152
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
153 @EdgesVertexIDs = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
154 @EdgesVertexIDs = $This->GetEdges($VertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
155
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
156 @Paths = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
157 for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
158 ($EdgeVertexID1, $EdgeVertexID2) = ($EdgesVertexIDs[$Index], $EdgesVertexIDs[$Index + 1]);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
159 $EdgePathsRef = $This->GetEdgeProperty($PathsPropertyName, $EdgeVertexID1, $EdgeVertexID2);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
160 push @Paths, @{$EdgePathsRef};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
161 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
162
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
163 # Go over each pair of paths around the specified vertex, join paths and associate
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
164 # joined path to appropriate edge...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
165 my($Index1, $Index2, $Path1, $Path2, $JoinedPath, $JoinedPathStartVertexID, $JoinedPathEndVertexID, @CommonVertices);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
166
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
167 for ($Index1 = 0; $Index1 < $#Paths; $Index1 +=1 ) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
168 $Path1 = $Paths[$Index1];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
169
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
170 PATH2: for ($Index2 = $Index1 + 1; $Index2 <= $#Paths; $Index2 +=1 ) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
171 $Path2 = $Paths[$Index2];
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
172
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
173 # For JoinedPath to be valid cycle, Path1 and Path2 must have exactly two vertices in common.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
174 # Otherwise, joined path contains duplicate vertices besides the terminal vertices and
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
175 # indicates a path from a different direction.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
176 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
177 # For paths leading to cycles, it only makes sense to join paths with only one common vertex;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
178 # otherwise, it wouldn't lead to a cycle and can be ignored.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
179 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
180 @CommonVertices = $Path1->GetCommonVertices($Path2);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
181 if (!(@CommonVertices <= 2 && ($CommonVertices[0] == $VertexID || $CommonVertices[1] == $VertexID))) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
182 next PATH2;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
183 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
184
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
185 $JoinedPath = $Path1->JoinAtVertex($Path2, $VertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
186 ($JoinedPathStartVertexID, $JoinedPathEndVertexID) = $JoinedPath->GetTerminalVertices();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
187
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
188 if (!$JoinedPath->IsIndependentPath()) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
189 next PATH2;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
190 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
191
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
192 # Decide whether to give up or keep going...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
193 if ($This->_IsTimeToGiveUpCyclesDetection()) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
194 warn "Warning: ${ClassName}->CollapseVertexAndCollectCyclicPaths: Cycles detection algorithm [ Ref 31 ] as implemented in the current release of MayaChemTools didn't finish with in the maximum allowed time of $This->{MaxAllowedTime} seconds; Cycles detection has been abandoned...";
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
195 return undef;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
196 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
197
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
198 if ($JoinedPathStartVertexID == $JoinedPathEndVertexID) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
199 # It's a cycle. Attach it to the graph as CylicPaths property...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
200 if ($This->HasGraphProperty($CyclicPathsPropertyName)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
201 my($ExistingCyclicPathsRef);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
202 $ExistingCyclicPathsRef = $This->GetGraphProperty($CyclicPathsPropertyName);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
203 push @{$ExistingCyclicPathsRef}, $JoinedPath;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
204 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
205 else {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
206 my(@NewCyclicPaths) = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
207 push @NewCyclicPaths, $JoinedPath;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
208 $This->SetGraphProperty($CyclicPathsPropertyName, \@NewCyclicPaths, $JoinedPathStartVertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
209 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
210 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
211 else {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
212 if ($This->HasEdge($JoinedPathStartVertexID, $JoinedPathEndVertexID)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
213 # Append to the list of exisiting paths property of the edge...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
214 my($ExistingPathsRef);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
215 $ExistingPathsRef = $This->GetEdgeProperty($PathsPropertyName, $JoinedPathStartVertexID, $JoinedPathEndVertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
216 push @{$ExistingPathsRef}, $JoinedPath;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
217 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
218 else {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
219 # Create a new edge and associate path property...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
220 my(@NewPaths) = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
221 push @NewPaths, $JoinedPath;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
222 $This->AddEdge($JoinedPathStartVertexID, $JoinedPathEndVertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
223 $This->SetEdgeProperty($PathsPropertyName, \@NewPaths, $JoinedPathStartVertexID, $JoinedPathEndVertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
224 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
225 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
226 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
227 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
228 $This->DeleteVertex($VertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
229
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
230 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
231 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
232
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
233 # Decide whether to give up cycles detection using collapse vertex methodology...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
234 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
235 sub _IsTimeToGiveUpCyclesDetection {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
236 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
237
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
238 return ((time - $This->{StartTime}) > $This->{MaxAllowedTime}) ? 1 : 0;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
239 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
240
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
241 # Delete vertices with degree less than a specifed degree...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
242 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
243 sub DeleteVerticesWithDegreeLessThan {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
244 my($This, $Degree) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
245 my($VertexID, @VertexIDs);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
246
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
247 while (@VertexIDs = $This->GetVerticesWithDegreeLessThan($Degree)) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
248 for $VertexID (@VertexIDs) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
249 $This->DeleteVertex($VertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
250 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
251 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
252 return $This;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
253 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
254
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
255 # Get paths associated with edges...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
256 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
257 sub GetPaths {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
258 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
259 my($PathsRef, @Paths, @PathsList);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
260
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
261 @Paths = (); @PathsList = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
262 @PathsList = $This->GetEdgesProperty($PathsPropertyName);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
263 for $PathsRef (@PathsList) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
264 push @Paths, @{$PathsRef};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
265 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
266 return wantarray ? @Paths : scalar @Paths;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
267 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
268
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
269 # Get paths associated with edges which make a cylce...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
270 #
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
271 sub GetCyclicPaths {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
272 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
273 my($PathsRef, @Paths, @PathsList);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
274
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
275 @Paths = (); @PathsList = ();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
276 @PathsList = $This->GetGraphProperty($CyclicPathsPropertyName);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
277 PATHS: for $PathsRef (@PathsList) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
278 if (!(defined($PathsRef) && @{$PathsRef})) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
279 next PATHS;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
280 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
281 push @Paths, @{$PathsRef};
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
282 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
283 return wantarray ? @Paths : scalar @Paths;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
284 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
285
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
286 # Is it a path graph object?
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
287 sub IsPathGraph ($) {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
288 my($Object) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
289
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
290 return _IsPathGraph($Object);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
291 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
292
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
293 # Return a string containg data for PathGraph object...
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
294 sub StringifyPathGraph {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
295 my($This) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
296 my($PathGraphString);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
297
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
298 $PathGraphString = 'PathGraph:' . $This->StringifyVerticesAndEdges() . '; ' . $This->StringifyProperties();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
299
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
300 return $PathGraphString;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
301 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
302
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
303 # Is it a PathGraph object?
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
304 sub _IsPathGraph {
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
305 my($Object) = @_;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
306
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
307 return (Scalar::Util::blessed($Object) && $Object->isa($ClassName)) ? 1 : 0;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
308 }
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
309
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
310 1;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
311
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
312 __END__
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
313
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
314 =head1 NAME
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
315
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
316 PathGraph
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
317
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
318 =head1 SYNOPSIS
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
319
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
320 use Graph::PathGraph;
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
321
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
322 use Graph::PathGraph qw(:all);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
323
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
324 =head1 DESCRIPTION
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
325
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
326 B<PathGraph> class provides the following methods:
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
327
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
328 new, CollapseVertexAndCollectCyclicPaths, DeleteVerticesWithDegreeLessThan,
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
329 GetCyclicPaths, GetPaths, IsPathGraph, StringifyPathGraph
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
330
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
331 B<PathGraph> class is derived from I<Graph> class.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
332
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
333 =head2 METHODS
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
334
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
335 =over 4
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
336
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
337 =item B<new>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
338
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
339 $NewPathGraph = new Graph::PathGraph($Graph);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
340
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
341 Using specified I<Graph>, B<new> method creates a new B<PathGraph> object and returns
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
342 newly created B<PathGraph> object.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
343
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
344 I<Graph> is converted into a B<PathGraph> by copying all its vertices and edges without any
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
345 associated properties data and associating a I<Path> object to each edge containing edge
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
346 vertex IDs as intial path.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
347
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
348 =item B<CollapseVertexAndCollectCyclicPaths>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
349
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
350 $PathGraph->CollapseVertexAndCollectCyclicPaths($VertexID);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
351
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
352 Collapses paths around a I<VertexID> by updating paths around the vertex [Ref 31] and associating any
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
353 resulting cyclic paths to graph as B<CyclicPaths> property name. And returns I<PathGraph>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
354
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
355 =item B<DeleteVerticesWithDegreeLessThan>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
356
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
357 $Return = $PathGraph->DeleteVerticesWithDegreeLessThan($Degree);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
358
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
359 Deletes vertices with degree less than I<Degree> from I<PathGraph> and returns I<PathGraph>.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
360
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
361 =item B<GetCyclicPaths>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
362
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
363 @CyclicPaths = $PathGraph->GetCyclicPaths();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
364 $NumOfPaths = $PathGraph->GetCyclicPaths();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
365
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
366 Returns an array of cyclic I<Paths> associated with edges in I<PathGraph>. In scalar context, number
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
367 of cyclic paths is returned.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
368
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
369 =item B<GetPaths>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
370
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
371 @Paths = $PathGraph->GetPaths();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
372 $NumOfPaths = $PathGraph->GetPaths();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
373
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
374 Returns an array of I<Paths> associated with edges in I<PathGraph>. In scalar context, number
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
375 of paths is returned.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
376
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
377 =item B<IsPathGraph>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
378
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
379 $Status = Graph::PathGraph::IsPathGraph($Object);
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
380
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
381 Returns 1 or 0 based on whether I<Object> is a B<PathGraph> object.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
382
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
383 =item B<StringifyPathGraph>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
384
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
385 $String = $PathGraph->StringifyPathGraph();
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
386
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
387 Returns a string containing information about traversed paths in I<PathGraph> object.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
388
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
389 =back
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
390
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
391 =head1 AUTHOR
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
392
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
393 Manish Sud <msud@san.rr.com>
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
394
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
395 =head1 SEE ALSO
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
396
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
397 Graph.pm, Path.pm
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
398
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
399 =head1 COPYRIGHT
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
400
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
401 Copyright (C) 2015 Manish Sud. All rights reserved.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
402
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
403 This file is part of MayaChemTools.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
404
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
405 MayaChemTools is free software; you can redistribute it and/or modify it under
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
406 the terms of the GNU Lesser General Public License as published by the Free
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
407 Software Foundation; either version 3 of the License, or (at your option)
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
408 any later version.
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
409
73ae111cf86f Uploaded
deepakjadmin
parents:
diff changeset
410 =cut