1 package PathGraph; 2 # 3 # $RCSfile: PathGraph.pm,v $ 4 # $Date: 2008/04/19 16:11:49 $ 5 # $Revision: 1.8 $ 6 # 7 # Author: Manish Sud <msud@san.rr.com> 8 # 9 # Copyright (C) 2004-2008 Manish Sud. All rights reserved. 10 # 11 # This file is part of MayaChemTools. 12 # 13 # MayaChemTools is free software; you can redistribute it and/or modify it under 14 # the terms of the GNU Lesser General Public License as published by the Free 15 # Software Foundation; either version 3 of the License, or (at your option) any 16 # later version. 17 # 18 # MayaChemTools is distributed in the hope that it will be useful, but without 19 # any warranty; without even the implied warranty of merchantability of fitness 20 # for a particular purpose. See the GNU Lesser General Public License for more 21 # details. 22 # 23 # You should have received a copy of the GNU Lesser General Public License 24 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or 25 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330, 26 # Boston, MA, 02111-1307, USA. 27 # 28 use 5.006; 29 use strict; 30 use Carp; 31 use Exporter; 32 use Scalar::Util; 33 use Storable (); 34 use Graph; 35 use Graph::Path; 36 37 use vars qw($VERSION @ISA @EXPORT @EXPORT_OK %EXPORT_TAGS); 38 39 $VERSION = '1.00'; 40 @ISA = qw(Graph Exporter); 41 @EXPORT = qw(IsPathGraph); 42 @EXPORT_OK = qw(); 43 44 %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]); 45 46 # Setup class variables... 47 my($ClassName, $PathsPropertyName, $CyclicPathsPropertyName); 48 _InitializeClass(); 49 50 # Overload Perl functions... 51 use overload '""' => 'StringifyPathGraph'; 52 53 # Class constructor... 54 sub new { 55 my($Class, $Graph) = @_; 56 57 # Initialize object... 58 my $This = $Class->SUPER::new(); 59 bless $This, ref($Class) || $Class; 60 $This->_InitializePathGraph($Graph); 61 62 $This->_ConvertGraphIntoPathGraph($Graph); 63 64 return $This; 65 } 66 67 # Initialize object data... 68 sub _InitializePathGraph { 69 my($This, $Graph) = @_; 70 71 if (!(defined($Graph) && Graph::IsGraph($Graph))) { 72 croak "Error: ${ClassName}->new: PathGraph object can't be instantiated without a Graph object..."; 73 } 74 75 $This->{Graph} = $Graph; 76 77 return $This; 78 } 79 80 # Initialize class ... 81 sub _InitializeClass { 82 #Class name... 83 $ClassName = __PACKAGE__; 84 85 # Path edge property name... 86 $PathsPropertyName = 'Paths'; 87 88 # Cyclic path vertex property name... 89 $CyclicPathsPropertyName = 'CyclicPaths'; 90 } 91 92 # Convert graph into a path graph... 93 # 94 sub _ConvertGraphIntoPathGraph { 95 my($This, $Graph) = @_; 96 97 # Copy graph vertices and edges without any associated properties data 98 # from Graph to This: Graph properties data is available using Graph object reference 99 # store in This object... 100 # 101 $Graph->CopyVerticesAndEdges($This); 102 103 # . Attach Path property to each edge... 104 # 105 my($Index, $VertexID1, $VertexID2, $Path, @EdgesVertexIDs); 106 107 @EdgesVertexIDs = (); 108 @EdgesVertexIDs = $This->GetEdges(); 109 for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) { 110 $VertexID1 = $EdgesVertexIDs[$Index]; $VertexID2 = $EdgesVertexIDs[$Index + 1]; 111 $Path = new Path($VertexID1, $VertexID2); 112 my(@Paths) = (); 113 push @Paths, $Path; 114 $This->SetEdgeProperty($PathsPropertyName, \@Paths, $VertexID1, $VertexID2); 115 } 116 return $This; 117 } 118 119 # Collapse paths around a specified vertex by updating paths around the vertex 120 # and adding any resulting cyclic paths to vertices attached to specified vertex. 121 # 122 # Notes: 123 # . Path object references are stored as a list attached to Paths property on edges. 124 # Usage of list allows multiple paths attached to the egde between a pair of vertices; 125 # Graph doesn't support multiple egdes between a pair of vertices. 126 # . Cyclic path object references are stored as list on vertices as CyclicPaths graph property. 127 # List allows multiple Loop properties attached to a vertex. 128 # 129 # 130 sub CollapseVertexAndCollectCyclicPaths { 131 my($This, $VertexID) = @_; 132 133 if (!$This->HasVertex($VertexID)) { 134 carp "Warning: ${ClassName}->CollapseVertexAndCollectCyclicPaths: Didn't collapse vertex $VertexID: Vertex $VertexID doesn't exist..."; 135 return undef; 136 } 137 # Collect all paths around specified VertexID by going over paths associated with its edges... 138 my($Index, $EdgePathsRef, $EdgeVertexID1, $EdgeVertexID2, @Paths, @EdgesVertexIDs); 139 140 @EdgesVertexIDs = (); 141 @EdgesVertexIDs = $This->GetEdges($VertexID); 142 143 @Paths = (); 144 for ($Index = 0; $Index < $#EdgesVertexIDs; $Index += 2) { 145 ($EdgeVertexID1, $EdgeVertexID2) = ($EdgesVertexIDs[$Index], $EdgesVertexIDs[$Index + 1]); 146 $EdgePathsRef = $This->GetEdgeProperty($PathsPropertyName, $EdgeVertexID1, $EdgeVertexID2); 147 push @Paths, @{$EdgePathsRef}; 148 } 149 150 # Go over each pair of paths around the specified vertex, join paths and associate 151 # joined path to appropriate edge... 152 my($Index1, $Index2, $Path1, $Path2, $JoinedPath, $JoinedPathStartVertexID, $JoinedPathEndVertexID, $Path1StartVertexID, $Path1EndVertexID, $Path2StartVertexID, $Path2EndVertexID, $CommonVertices); 153 154 for ($Index1 = 0; $Index1 < $#Paths; $Index1 +=1 ) { 155 $Path1 = $Paths[$Index1]; 156 ($Path1StartVertexID, $Path1EndVertexID) = $Path1->GetTerminalVertices(); 157 158 PATH2: for ($Index2 = $Index1 + 1; $Index2 <= $#Paths; $Index2 +=1 ) { 159 $Path2 = $Paths[$Index2]; 160 ($Path2StartVertexID, $Path2EndVertexID) = $Path2->GetTerminalVertices(); 161 162 $CommonVertices = $Path1->GetCommonVertices($Path2); 163 164 # For JoinedPath to be valid cycle, Path1 and Path2 must have exactly two vertices in common. 165 # Otherwise, joined path contains duplicate vertices besides the terminal vertices and 166 # indicates a path from a different direction. 167 # 168 # For paths leading to cycles, it only makes sense to join paths with only one common vertex; 169 # otherwise, it wouldn't lead to a cycle and can be ignored. 170 # 171 if ($CommonVertices > 2) { 172 next PATH2; 173 } 174 175 $JoinedPath = $Path1->JoinAtVertex($Path2, $VertexID); 176 ($JoinedPathStartVertexID, $JoinedPathEndVertexID) = $JoinedPath->GetTerminalVertices(); 177 178 if ($JoinedPathStartVertexID == $JoinedPathEndVertexID) { 179 if (!$JoinedPath->IsIndependentCyclicPath()) { 180 next PATH2; 181 } 182 183 # It's a cycle. Attach it to the graph as CylicPaths property... 184 if ($This->HasGraphProperty($CyclicPathsPropertyName)) { 185 my($ExistingCyclicPathsRef); 186 $ExistingCyclicPathsRef = $This->GetGraphProperty($CyclicPathsPropertyName); 187 push @{$ExistingCyclicPathsRef}, $JoinedPath; 188 } 189 else { 190 my(@NewCyclicPaths) = (); 191 push @NewCyclicPaths, $JoinedPath; 192 $This->SetGraphProperty($CyclicPathsPropertyName, \@NewCyclicPaths, $JoinedPathStartVertexID); 193 } 194 } 195 else { 196 if ($This->HasEdge($JoinedPathStartVertexID, $JoinedPathEndVertexID)) { 197 # Append to the list of exisiting paths property of the edge... 198 my($ExistingPathsRef); 199 $ExistingPathsRef = $This->GetEdgeProperty($PathsPropertyName, $JoinedPathStartVertexID, $JoinedPathEndVertexID); 200 push @{$ExistingPathsRef}, $JoinedPath; 201 } 202 else { 203 # Create a new edge and associate path property... 204 my(@NewPaths) = (); 205 push @NewPaths, $JoinedPath; 206 $This->AddEdge($JoinedPathStartVertexID, $JoinedPathEndVertexID); 207 $This->SetEdgeProperty($PathsPropertyName, \@NewPaths, $JoinedPathStartVertexID, $JoinedPathEndVertexID); 208 } 209 } 210 } 211 } 212 $This->DeleteVertex($VertexID); 213 214 return $This; 215 } 216 217 # Delete vertices with degree less than a specifed degree... 218 # 219 sub DeleteVerticesWithDegreeLessThan { 220 my($This, $Degree) = @_; 221 my($VertexID, @VertexIDs); 222 223 while (@VertexIDs = $This->GetVerticesWithDegreeLessThan($Degree)) { 224 for $VertexID (@VertexIDs) { 225 $This->DeleteVertex($VertexID); 226 } 227 } 228 return $This; 229 } 230 231 # Get paths associated with edges... 232 # 233 sub GetPaths { 234 my($This) = @_; 235 my($PathsRef, @Paths, @PathsList); 236 237 @Paths = (); @PathsList = (); 238 @PathsList = $This->GetEdgesProperty($PathsPropertyName); 239 for $PathsRef (@PathsList) { 240 push @Paths, @{$PathsRef}; 241 } 242 return wantarray ? @Paths : scalar @Paths; 243 } 244 245 # Get paths associated with edges which make a cylce... 246 # 247 sub GetCyclicPaths { 248 my($This) = @_; 249 my($PathsRef, @Paths, @PathsList); 250 251 @Paths = (); @PathsList = (); 252 @PathsList = $This->GetGraphProperty($CyclicPathsPropertyName); 253 PATHS: for $PathsRef (@PathsList) { 254 if (!(defined($PathsRef) && @{$PathsRef})) { 255 next PATHS; 256 } 257 push @Paths, @{$PathsRef}; 258 } 259 return wantarray ? @Paths : scalar @Paths; 260 } 261 262 # Is it a path graph object? 263 sub IsPathGraph ($) { 264 my($Object) = @_; 265 266 return _IsPathGraph($Object); 267 } 268 269 # Return a string containg data for PathGraph object... 270 sub StringifyPathGraph { 271 my($This) = @_; 272 my($PathGraphString); 273 274 $PathGraphString = 'PathGraph:' . $This->StringifyVerticesAndEdges() . '; ' . $This->StringifyProperties(); 275 276 return $PathGraphString; 277 } 278 279 # Is it a PathGraph object? 280 sub _IsPathGraph { 281 my($Object) = @_; 282 283 return (Scalar::Util::blessed($Object) && $Object->isa($ClassName)) ? 1 : 0; 284 } 285
