|
1
|
1 package Graph::PathsTraversal;
|
|
|
2 #
|
|
|
3 # $RCSfile: PathsTraversal.pm,v $
|
|
|
4 # $Date: 2015/02/28 20:49:06 $
|
|
|
5 # $Revision: 1.29 $
|
|
|
6 #
|
|
|
7 # Author: Manish Sud <msud@san.rr.com>
|
|
|
8 #
|
|
|
9 # Copyright (C) 2015 Manish Sud. All rights reserved.
|
|
|
10 #
|
|
|
11 # This file is part of MayaChemTools.
|
|
|
12 #
|
|
|
13 # MayaChemTools is free software; you can redistribute it and/or modify it under
|
|
|
14 # the terms of the GNU Lesser General Public License as published by the Free
|
|
|
15 # Software Foundation; either version 3 of the License, or (at your option) any
|
|
|
16 # later version.
|
|
|
17 #
|
|
|
18 # MayaChemTools is distributed in the hope that it will be useful, but without
|
|
|
19 # any warranty; without even the implied warranty of merchantability of fitness
|
|
|
20 # for a particular purpose. See the GNU Lesser General Public License for more
|
|
|
21 # details.
|
|
|
22 #
|
|
|
23 # You should have received a copy of the GNU Lesser General Public License
|
|
|
24 # along with MayaChemTools; if not, see <http://www.gnu.org/licenses/> or
|
|
|
25 # write to the Free Software Foundation Inc., 59 Temple Place, Suite 330,
|
|
|
26 # Boston, MA, 02111-1307, USA.
|
|
|
27 #
|
|
|
28
|
|
|
29 use strict;
|
|
|
30 use Carp;
|
|
|
31 use Exporter;
|
|
|
32 use Graph;
|
|
|
33 use Graph::Path;
|
|
|
34
|
|
|
35 use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
|
|
|
36
|
|
|
37 @ISA = qw(Exporter);
|
|
|
38 @EXPORT = qw();
|
|
|
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 '""' => 'StringifyPathsTraversal';
|
|
|
49
|
|
|
50 # Class constructor...
|
|
|
51 sub new {
|
|
|
52 my($Class, $Graph) = @_;
|
|
|
53
|
|
|
54 # Initialize object...
|
|
|
55 my $This = {};
|
|
|
56 bless $This, ref($Class) || $Class;
|
|
|
57 $This->_InitializePathsTraversal($Graph);
|
|
|
58
|
|
|
59 return $This;
|
|
|
60 }
|
|
|
61
|
|
|
62 # Initialize object data...
|
|
|
63 sub _InitializePathsTraversal {
|
|
|
64 my($This, $Graph) = @_;
|
|
|
65
|
|
|
66 # Graph object...
|
|
|
67 $This->{Graph} = $Graph;
|
|
|
68
|
|
|
69 # Traversal mode: Vertex or Path
|
|
|
70 $This->{TraversalMode} = '';
|
|
|
71
|
|
|
72 # Traversal type: DFS, DFSWithLimit, BFS, BFSWithLimit...
|
|
|
73 $This->{TraversalType} = '';
|
|
|
74
|
|
|
75 # For finding root vertex and controlling search...
|
|
|
76 my(@VertexIDs);
|
|
|
77 @VertexIDs = $This->{Graph}->GetVertices();
|
|
|
78 %{$This->{VerticesToVisit}} = ();
|
|
|
79 @{$This->{VerticesToVisit}}{ @VertexIDs } = @VertexIDs;
|
|
|
80
|
|
|
81 # Root vertex of all visited vertices...
|
|
|
82 %{$This->{VerticesRoots}} = ();
|
|
|
83
|
|
|
84 # Visited vertices...
|
|
|
85 %{$This->{VisitedVertices}} = ();
|
|
|
86
|
|
|
87 # Finished vertices...
|
|
|
88 %{$This->{FinishedVertices}} = ();
|
|
|
89
|
|
|
90 # List of active vertices during DFS/BFS search...
|
|
|
91 @{$This->{ActiveVertices}} = ();
|
|
|
92
|
|
|
93 # List of ordered vertices traversed during DFS/BFS search...
|
|
|
94 @{$This->{Vertices}} = ();
|
|
|
95
|
|
|
96 # Vertex neighbors during traversal...
|
|
|
97 %{$This->{VerticesNeighbors}} = ();
|
|
|
98
|
|
|
99 # Vertices depth from root...
|
|
|
100 %{$This->{VerticesDepth}} = ();
|
|
|
101
|
|
|
102 # Predecessor of each vertex during vertex traversal. For root vertex, it's root itself...
|
|
|
103 %{$This->{VerticesPredecessors}} = ();
|
|
|
104
|
|
|
105 # Successors of each vertex during vertex traversal...
|
|
|
106 %{$This->{VerticesSuccessors}} = ();
|
|
|
107
|
|
|
108 # Vertices at different neighborhood levels during vertex traversal...
|
|
|
109 @{$This->{VerticesNeighborhoods}} = ();
|
|
|
110
|
|
|
111 # Vertices, along with their successors, at different neighborhood levels during vertex traversal...
|
|
|
112 @{$This->{VerticesNeighborhoodsWithSuccessors}} = ();
|
|
|
113
|
|
|
114 # Visited edges during Path TraversalMode...
|
|
|
115 %{$This->{VisitedEdges}} = ();
|
|
|
116 %{$This->{VisitedEdges}->{From}} = ();
|
|
|
117 %{$This->{VisitedEdges}->{To}} = ();
|
|
|
118
|
|
|
119 # Vertex path during Path TraversalMode...
|
|
|
120 %{$This->{VerticesPaths}} = ();
|
|
|
121
|
|
|
122 # Allow cycles in paths during VertexNeighborhood TraversalMode. By default, cycles are not allowed
|
|
|
123 # during vertex traversal: a vertex is only visited once during BFS search for neighborhoods. For
|
|
|
124 # neighborhood vertices search during successors identification, vertex cycles are explicity allowed
|
|
|
125 # to indentify all successors.
|
|
|
126 $This->{AllowVertexCycles} = 0;
|
|
|
127
|
|
|
128 # Allow cycles in paths during Path TraversalMode...
|
|
|
129 $This->{AllowPathCycles} = 1;
|
|
|
130
|
|
|
131 # Cycle closure vertices during Path TraversalMode...
|
|
|
132 %{$This->{CycleClosureVertices}} = ();
|
|
|
133
|
|
|
134 # Paths traversed during search...
|
|
|
135 @{$This->{Paths}} = ();
|
|
|
136
|
|
|
137 return $This;
|
|
|
138 }
|
|
|
139
|
|
|
140 # Initialize class ...
|
|
|
141 sub _InitializeClass {
|
|
|
142 #Class name...
|
|
|
143 $ClassName = __PACKAGE__;
|
|
|
144 }
|
|
|
145
|
|
|
146 # Perform a depth first search (DFS)...
|
|
|
147 #
|
|
|
148 sub PerformDepthFirstSearch {
|
|
|
149 my($This, $RootVertexID) = @_;
|
|
|
150
|
|
|
151 if (defined $RootVertexID) {
|
|
|
152 if (!$This->{Graph}->HasVertex($RootVertexID)) {
|
|
|
153 carp "Warning: ${ClassName}->PerformDepthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist...";
|
|
|
154 return undef;
|
|
|
155 }
|
|
|
156 }
|
|
|
157 return $This->_PerformVertexSearch("DFS", $RootVertexID);
|
|
|
158 }
|
|
|
159
|
|
|
160 # Perform a depth first search (DFS) with limit on depth...
|
|
|
161 #
|
|
|
162 sub PerformDepthFirstSearchWithLimit {
|
|
|
163 my($This, $DepthLimit, $RootVertexID) = @_;
|
|
|
164
|
|
|
165 if (!defined $DepthLimit) {
|
|
|
166 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Depth limit must be specified...";
|
|
|
167 return undef;
|
|
|
168 }
|
|
|
169 if ($DepthLimit < 0) {
|
|
|
170 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer...";
|
|
|
171 return undef;
|
|
|
172 }
|
|
|
173 if (defined $RootVertexID) {
|
|
|
174 if (!$This->{Graph}->HasVertex($RootVertexID)) {
|
|
|
175 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist...";
|
|
|
176 return undef;
|
|
|
177 }
|
|
|
178 }
|
|
|
179 return $This->_PerformVertexSearch("DFSWithLimit", $RootVertexID, $DepthLimit);
|
|
|
180 }
|
|
|
181
|
|
|
182 # Perform a breadth first search (BFS)...
|
|
|
183 #
|
|
|
184 sub PerformBreadthFirstSearch {
|
|
|
185 my($This, $RootVertexID) = @_;
|
|
|
186
|
|
|
187 if (defined $RootVertexID) {
|
|
|
188 if (!$This->{Graph}->HasVertex($RootVertexID)) {
|
|
|
189 carp "Warning: ${ClassName}->PerformBreadthFirstSearch: No search performed: Vertex $RootVertexID doesn't exist...";
|
|
|
190 return undef;
|
|
|
191 }
|
|
|
192 }
|
|
|
193 return $This->_PerformVertexSearch("BFS", $RootVertexID);
|
|
|
194 }
|
|
|
195
|
|
|
196 # Perform a breadth first search (BFS) with limit...
|
|
|
197 #
|
|
|
198 sub PerformBreadthFirstSearchWithLimit {
|
|
|
199 my($This, $DepthLimit, $RootVertexID) = @_;
|
|
|
200
|
|
|
201 if (!defined $DepthLimit) {
|
|
|
202 carp "Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Depth limit must be specified...";
|
|
|
203 return undef;
|
|
|
204 }
|
|
|
205 if ($DepthLimit < 0) {
|
|
|
206 carp "Warning: ${ClassName}->PerformBreadthFirstSearchWithLimit: No search performed: Specified depth limit, $DepthLimit, must be a positive integer...";
|
|
|
207 return undef;
|
|
|
208 }
|
|
|
209 if (defined $RootVertexID) {
|
|
|
210 if (!$This->{Graph}->HasVertex($RootVertexID)) {
|
|
|
211 carp "Warning: ${ClassName}->PerformDepthFirstSearchWithLimit: No search performed: Vertex $RootVertexID doesn't exist...";
|
|
|
212 return undef;
|
|
|
213 }
|
|
|
214 }
|
|
|
215 return $This->_PerformVertexSearch("BFSWithLimit", $RootVertexID, $DepthLimit);
|
|
|
216 }
|
|
|
217
|
|
|
218 # Perform appropriate vertex search...
|
|
|
219 #
|
|
|
220 sub _PerformVertexSearch {
|
|
|
221 my($This, $SearchType, $RootVertexID, $DepthLimit, $TargetVertexID) = @_;
|
|
|
222
|
|
|
223 # Setup search...
|
|
|
224 $This->{TraversalMode} = 'Vertex';
|
|
|
225 $This->{TraversalType} = $SearchType;
|
|
|
226
|
|
|
227 if (defined $RootVertexID) {
|
|
|
228 $This->{RootVertex} = $RootVertexID;
|
|
|
229 }
|
|
|
230 if (defined $DepthLimit) {
|
|
|
231 $This->{DepthLimit} = $DepthLimit;
|
|
|
232 }
|
|
|
233 if (defined $TargetVertexID) {
|
|
|
234 $This->{TargetVertex} = $TargetVertexID;
|
|
|
235 }
|
|
|
236
|
|
|
237 # Perform search...
|
|
|
238 return $This->_TraverseGraph();
|
|
|
239 }
|
|
|
240
|
|
|
241 # Perform DFS or BFS traversal with or without any limits...
|
|
|
242 #
|
|
|
243 sub _TraverseGraph {
|
|
|
244 my($This) = @_;
|
|
|
245 my($ProcessingVertices, $CurrentVertexID, $NeighborVertexID, $VertexID);
|
|
|
246
|
|
|
247 if ($This->{TraversalMode} !~ /^(Vertex|Path|VertexNeighborhood)$/i) {
|
|
|
248 return $This;
|
|
|
249 }
|
|
|
250
|
|
|
251 $ProcessingVertices = 1;
|
|
|
252
|
|
|
253 VERTICES: while ($ProcessingVertices) {
|
|
|
254 # Set root vertex...
|
|
|
255 if (!@{$This->{ActiveVertices}}) {
|
|
|
256 my($RootVertexID);
|
|
|
257
|
|
|
258 $RootVertexID = $This->_GetRootVertex();
|
|
|
259 if (!defined $RootVertexID) {
|
|
|
260 $ProcessingVertices = 0; next VERTICES;
|
|
|
261 }
|
|
|
262 $This->_ProcessVisitedVertex($RootVertexID, $RootVertexID);
|
|
|
263 }
|
|
|
264
|
|
|
265 # Get current active vertex...
|
|
|
266 $CurrentVertexID = $This->_GetActiveVertex();
|
|
|
267 if (!defined $CurrentVertexID) {
|
|
|
268 $ProcessingVertices = 0; next VERTICES;
|
|
|
269 }
|
|
|
270
|
|
|
271 # Get next available neighbor of current vertex...
|
|
|
272 #
|
|
|
273 $NeighborVertexID = $This->_GetNeighborVertex($CurrentVertexID);
|
|
|
274
|
|
|
275 # Process neighbor or current vertex...
|
|
|
276 if (defined $NeighborVertexID) {
|
|
|
277 $This->_ProcessVisitedVertex($NeighborVertexID, $CurrentVertexID);
|
|
|
278 }
|
|
|
279 else {
|
|
|
280 # Finished with all neighbors for current vertex...
|
|
|
281 $This->_ProcessFinishedVertex($CurrentVertexID);
|
|
|
282 }
|
|
|
283 }
|
|
|
284 return $This;
|
|
|
285 }
|
|
|
286
|
|
|
287 # Get root vertex to start the search...
|
|
|
288 #
|
|
|
289 # Notes:
|
|
|
290 # . User specification of root vertex forces traversal in a specific connected component
|
|
|
291 # of graph; To traverse find all connected components, perform traversal without specification of
|
|
|
292 # a root vertex.
|
|
|
293 #
|
|
|
294 sub _GetRootVertex {
|
|
|
295 my($This) = @_;
|
|
|
296 my($RootVertexID);
|
|
|
297
|
|
|
298 # Check for specified root vertex and constrain traversal to specific connected
|
|
|
299 # component by setting root limit...
|
|
|
300 if (exists $This->{RootVertex}) {
|
|
|
301 $RootVertexID = $This->{RootVertex};
|
|
|
302 delete $This->{RootVertex};
|
|
|
303 $This->{RootVertexSpecified} = 1;
|
|
|
304
|
|
|
305 return $RootVertexID;
|
|
|
306 }
|
|
|
307 # Traversal limited to connected component containing specified root vertex...
|
|
|
308 if (exists $This->{RootVertexSpecified}) {
|
|
|
309 return undef;
|
|
|
310 }
|
|
|
311
|
|
|
312 # Use first vertex in sorted available vertices list to get root vertex. Vertex
|
|
|
313 # with largest degree could also be used as root vertex. However, for all
|
|
|
314 # practical purposes, any arbitrary vertex can be used as root vertex to
|
|
|
315 # start search for another disconnected component of the graph.
|
|
|
316 #
|
|
|
317 my(@VerticesToVisit);
|
|
|
318
|
|
|
319 $RootVertexID = undef; @VerticesToVisit = ();
|
|
|
320 @VerticesToVisit = sort { $a <=> $b } keys %{$This->{VerticesToVisit}};
|
|
|
321 if (@VerticesToVisit) {
|
|
|
322 $RootVertexID = $VerticesToVisit[0];
|
|
|
323 }
|
|
|
324 return $RootVertexID;
|
|
|
325 }
|
|
|
326
|
|
|
327 # Get current or new active vertex for DFS/BFS traversals...
|
|
|
328 #
|
|
|
329 sub _GetActiveVertex {
|
|
|
330 my($This) = @_;
|
|
|
331 my($ActiveVertexID);
|
|
|
332
|
|
|
333 $ActiveVertexID = undef;
|
|
|
334 if ($This->{TraversalType} =~ /^(DFS|DFSWithLimit)$/i) {
|
|
|
335 # For DFS, it's last vertex in LIFO queue...
|
|
|
336 $ActiveVertexID = $This->{ActiveVertices}[-1];
|
|
|
337 }
|
|
|
338 elsif ($This->{TraversalType} =~ /^(BFS|BFSWithLimit)$/i) {
|
|
|
339 # For BFS, it's first vertex in FIFO queue...
|
|
|
340 $ActiveVertexID = $This->{ActiveVertices}[0];
|
|
|
341 }
|
|
|
342 return $ActiveVertexID;
|
|
|
343 }
|
|
|
344
|
|
|
345 # Get available neigbor of specified vertex...
|
|
|
346 #
|
|
|
347 sub _GetNeighborVertex {
|
|
|
348 my($This, $VertexID) = @_;
|
|
|
349
|
|
|
350 # Retrieve neighbors for vertex...
|
|
|
351 if (!exists $This->{VerticesNeighbors}{$VertexID}) {
|
|
|
352 @{$This->{VerticesNeighbors}{$VertexID}} = ();
|
|
|
353
|
|
|
354 if (exists $This->{DepthLimit}) {
|
|
|
355 # Only collect neighbors to visit below specified depth limit...
|
|
|
356 if ($This->{VerticesDepth}{$VertexID} < $This->{DepthLimit}) {
|
|
|
357 push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
|
|
|
358 }
|
|
|
359 else {
|
|
|
360 if (!exists $This->{RootVertexSpecified}) {
|
|
|
361 # Mark all other downstream neighbor vertices to be ignored from any further
|
|
|
362 # processing and avoid selection of a new root...
|
|
|
363 $This->_IgnoreDownstreamNeighbors($VertexID);
|
|
|
364 }
|
|
|
365 }
|
|
|
366 }
|
|
|
367 elsif (exists $This->{TargetVertex}) {
|
|
|
368 if ($VertexID != $This->{TargetVertex}) {
|
|
|
369 push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
|
|
|
370 }
|
|
|
371 }
|
|
|
372 else {
|
|
|
373 push @{$This->{VerticesNeighbors}{$VertexID}}, $This->{Graph}->GetNeighbors($VertexID);
|
|
|
374 }
|
|
|
375 }
|
|
|
376
|
|
|
377 if ($This->{TraversalMode} =~ /^Path$/i) {
|
|
|
378 # Get available neighbor for path search...
|
|
|
379 return $This->_GetNeighborVertexDuringPathTraversal($VertexID);
|
|
|
380 }
|
|
|
381 elsif ($This->{TraversalMode} =~ /^Vertex$/i) {
|
|
|
382 # Get unvisited neighbor for vertex search...
|
|
|
383 return $This->_GetNeighborVertexDuringVertexTraversal($VertexID);
|
|
|
384 }
|
|
|
385 elsif ($This->{TraversalMode} =~ /^VertexNeighborhood$/i) {
|
|
|
386 # Get available neighbor during vertex neighborhood search...
|
|
|
387 return $This->_GetNeighborVertexDuringVertexNeighborhoodTraversal($VertexID);
|
|
|
388 }
|
|
|
389 return undef;
|
|
|
390 }
|
|
|
391
|
|
|
392 # Get unvisited neighbor of specified vertex during vertex traversal...
|
|
|
393 #
|
|
|
394 sub _GetNeighborVertexDuringVertexTraversal {
|
|
|
395 my($This, $VertexID) = @_;
|
|
|
396 my($NeighborVertexID, $UnvisitedNeighborVertexID);
|
|
|
397
|
|
|
398 # Get unvisited neighbor...
|
|
|
399 $UnvisitedNeighborVertexID = undef;
|
|
|
400 NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
|
|
|
401 if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
|
|
|
402 $UnvisitedNeighborVertexID = $NeighborVertexID;
|
|
|
403 last NEIGHBOR;
|
|
|
404 }
|
|
|
405 }
|
|
|
406 return $UnvisitedNeighborVertexID;
|
|
|
407 }
|
|
|
408
|
|
|
409 # Get available neighbor of specified vertex during vertex neighborhood traversal...
|
|
|
410 #
|
|
|
411 sub _GetNeighborVertexDuringVertexNeighborhoodTraversal {
|
|
|
412 my($This, $VertexID) = @_;
|
|
|
413 my($NeighborVertexID, $UnvisitedNeighborVertexID);
|
|
|
414
|
|
|
415 # Get available neighbor...
|
|
|
416 $UnvisitedNeighborVertexID = undef;
|
|
|
417 NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
|
|
|
418 if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
|
|
|
419 $UnvisitedNeighborVertexID = $NeighborVertexID;
|
|
|
420 last NEIGHBOR;
|
|
|
421 }
|
|
|
422 # Look for any unvisited edge back to visited vertex...
|
|
|
423 if ($This->_IsVisitedEdge($VertexID, $NeighborVertexID) || $This->_IsVisitedEdge($NeighborVertexID, $VertexID)) {
|
|
|
424 next NEIGHBOR;
|
|
|
425 }
|
|
|
426 # Check its depth...
|
|
|
427 if (exists $This->{DepthLimit}) {
|
|
|
428 if (($This->{VerticesDepth}{$VertexID} + 1) > $This->{DepthLimit}) {
|
|
|
429 next NEIGHBOR;
|
|
|
430 }
|
|
|
431 }
|
|
|
432 # Its an edge that makes a cycle during BFS search...
|
|
|
433 if ($This->{AllowVertexCycles}) {
|
|
|
434 $This->{CycleClosureVertices}{$NeighborVertexID} = 1;
|
|
|
435 $UnvisitedNeighborVertexID = $NeighborVertexID;
|
|
|
436 last NEIGHBOR;
|
|
|
437 }
|
|
|
438 }
|
|
|
439 return $UnvisitedNeighborVertexID;
|
|
|
440 }
|
|
|
441
|
|
|
442 # Get available neighbor of specified vertex during path traversal...
|
|
|
443 #
|
|
|
444 sub _GetNeighborVertexDuringPathTraversal {
|
|
|
445 my($This, $VertexID) = @_;
|
|
|
446 my($NeighborVertexID, $UnvisitedNeighborVertexID);
|
|
|
447
|
|
|
448 # Get unvisited neighbor...
|
|
|
449 $UnvisitedNeighborVertexID = undef;
|
|
|
450 NEIGHBOR: for $NeighborVertexID (@{$This->{VerticesNeighbors}{$VertexID}}) {
|
|
|
451 if (!exists $This->{VisitedVertices}{$NeighborVertexID}) {
|
|
|
452 # An unvisited vertex...
|
|
|
453 $UnvisitedNeighborVertexID = $NeighborVertexID;
|
|
|
454 last NEIGHBOR;
|
|
|
455 }
|
|
|
456 # Look for any unvisited edge back to visited vertex...
|
|
|
457 if ($This->_IsVisitedEdge($VertexID, $NeighborVertexID) || $This->_IsVisitedEdge($NeighborVertexID, $VertexID)) {
|
|
|
458 next NEIGHBOR;
|
|
|
459 }
|
|
|
460 # Check its depth...
|
|
|
461 if (exists $This->{DepthLimit}) {
|
|
|
462 if (($This->{VerticesDepth}{$VertexID} + 1) >= $This->{DepthLimit}) {
|
|
|
463 next NEIGHBOR;
|
|
|
464 }
|
|
|
465 }
|
|
|
466
|
|
|
467 # It's the edge final edge of a cycle in case $NeighborVertexID is already in the path; otherwise, it's
|
|
|
468 # part of the path from a different direction in a cycle or a left over vertex during Limit search.
|
|
|
469 #
|
|
|
470 if ($This->_IsCycleClosureEdge($VertexID, $NeighborVertexID)) {
|
|
|
471 if ($This->{AllowPathCycles}) {
|
|
|
472 $This->{CycleClosureVertices}{$NeighborVertexID} = 1;
|
|
|
473 $UnvisitedNeighborVertexID = $NeighborVertexID;
|
|
|
474 last NEIGHBOR;
|
|
|
475 }
|
|
|
476 }
|
|
|
477 else {
|
|
|
478 $UnvisitedNeighborVertexID = $NeighborVertexID;
|
|
|
479 last NEIGHBOR;
|
|
|
480 }
|
|
|
481 }
|
|
|
482 return $UnvisitedNeighborVertexID;
|
|
|
483 }
|
|
|
484
|
|
|
485 # Process visited vertex...
|
|
|
486 #
|
|
|
487 sub _ProcessVisitedVertex {
|
|
|
488 my($This, $VertexID, $PredecessorVertexID) = @_;
|
|
|
489
|
|
|
490 if (!exists $This->{VisitedVertices}{$VertexID}) {
|
|
|
491 # Add it to active vertices list...
|
|
|
492 push @{$This->{ActiveVertices}}, $VertexID;
|
|
|
493
|
|
|
494 # Mark vertex as visited vertex and take it out from the list of vertices to visit...
|
|
|
495 $This->{VisitedVertices}{$VertexID} = 1;
|
|
|
496 delete $This->{VerticesToVisit}{$VertexID};
|
|
|
497 }
|
|
|
498
|
|
|
499 # Set up root vertex, predecessor vertex and distance from root...
|
|
|
500 if ($VertexID == $PredecessorVertexID) {
|
|
|
501 $This->{VerticesRoots}{$VertexID} = $VertexID;
|
|
|
502
|
|
|
503 $This->{VerticesPredecessors}{$VertexID} = $VertexID;
|
|
|
504 if (!exists $This->{VerticesSuccessors}{$VertexID}) {
|
|
|
505 @{$This->{VerticesSuccessors}{$VertexID}} = ();
|
|
|
506 }
|
|
|
507
|
|
|
508 $This->{VerticesDepth}{$VertexID} = 0;
|
|
|
509
|
|
|
510 if ($This->{TraversalMode} =~ /^Path$/i) {
|
|
|
511 $This->_ProcessVisitedPath($VertexID, $PredecessorVertexID);
|
|
|
512 }
|
|
|
513 }
|
|
|
514 else {
|
|
|
515 $This->{VerticesRoots}{$VertexID} = $This->{VerticesRoots}{$PredecessorVertexID};
|
|
|
516
|
|
|
517 $This->{VerticesPredecessors}{$VertexID} = $PredecessorVertexID;
|
|
|
518 if (!exists $This->{VerticesSuccessors}{$PredecessorVertexID}) {
|
|
|
519 @{$This->{VerticesSuccessors}{$PredecessorVertexID}} = ();
|
|
|
520 }
|
|
|
521 push @{$This->{VerticesSuccessors}{$PredecessorVertexID}}, $VertexID;
|
|
|
522
|
|
|
523 if (!exists $This->{VerticesDepth}{$VertexID}) {
|
|
|
524 $This->{VerticesDepth}{$VertexID} = $This->{VerticesDepth}{$PredecessorVertexID} + 1;
|
|
|
525 }
|
|
|
526
|
|
|
527 if ($This->{TraversalMode} =~ /^Path$/i) {
|
|
|
528 $This->_ProcessVisitedPath($VertexID, $PredecessorVertexID);
|
|
|
529 $This->_ProcessVisitedEdge($PredecessorVertexID, $VertexID);
|
|
|
530 }
|
|
|
531 elsif ($This->{TraversalMode} =~ /^VertexNeighborhood$/i) {
|
|
|
532 $This->_ProcessVisitedEdge($PredecessorVertexID, $VertexID);
|
|
|
533 }
|
|
|
534 }
|
|
|
535 return $This;
|
|
|
536 }
|
|
|
537
|
|
|
538 # Process visited path...
|
|
|
539 #
|
|
|
540 sub _ProcessVisitedPath {
|
|
|
541 my($This, $VertexID, $PredecessorVertexID) = @_;
|
|
|
542
|
|
|
543 # Initialize VerticesPath...
|
|
|
544 if (!exists $This->{VerticesPaths}{$VertexID}) {
|
|
|
545 @{$This->{VerticesPaths}{$VertexID}} = ();
|
|
|
546 }
|
|
|
547
|
|
|
548 if ($VertexID == $PredecessorVertexID) {
|
|
|
549 # Starting of a path from root...
|
|
|
550 push @{$This->{VerticesPaths}{$VertexID}}, $VertexID;
|
|
|
551 }
|
|
|
552 else {
|
|
|
553 # Setup path for a vertex using path information from predecessor vertex...
|
|
|
554 if (exists $This->{CycleClosureVertices}{$PredecessorVertexID}) {
|
|
|
555 # Start of a new path from predecessor vertex...
|
|
|
556 push @{$This->{VerticesPaths}{$VertexID}}, "${PredecessorVertexID}-${VertexID}";
|
|
|
557 }
|
|
|
558 else {
|
|
|
559 my($PredecessorVertexPath);
|
|
|
560 for $PredecessorVertexPath (@{$This->{VerticesPaths}{$PredecessorVertexID}}) {
|
|
|
561 push @{$This->{VerticesPaths}{$VertexID}}, "${PredecessorVertexPath}-${VertexID}";
|
|
|
562 }
|
|
|
563 }
|
|
|
564 }
|
|
|
565 return $This;
|
|
|
566 }
|
|
|
567
|
|
|
568 # Process visited edge...
|
|
|
569 #
|
|
|
570 sub _ProcessVisitedEdge {
|
|
|
571 my($This, $VertexID1, $VertexID2) = @_;
|
|
|
572
|
|
|
573 if (!exists $This->{VisitedEdges}->{From}->{$VertexID1}) {
|
|
|
574 %{$This->{VisitedEdges}->{From}->{$VertexID1}} = ();
|
|
|
575 }
|
|
|
576 $This->{VisitedEdges}->{From}->{$VertexID1}->{$VertexID2} = $VertexID2;
|
|
|
577
|
|
|
578 if (!exists $This->{VisitedEdges}->{To}->{$VertexID2}) {
|
|
|
579 %{$This->{VisitedEdges}->{To}->{$VertexID2}} = ();
|
|
|
580 }
|
|
|
581 $This->{VisitedEdges}->{To}->{$VertexID2}->{$VertexID1} = $VertexID1;
|
|
|
582
|
|
|
583 return $This;
|
|
|
584 }
|
|
|
585
|
|
|
586 # Finished processing active vertex...
|
|
|
587 #
|
|
|
588 sub _ProcessFinishedVertex {
|
|
|
589 my($This, $VertexID) = @_;
|
|
|
590
|
|
|
591 if (!exists $This->{FinishedVertices}{$VertexID}) {
|
|
|
592 $This->{FinishedVertices}{$VertexID} = $VertexID;
|
|
|
593 # Add vertex to list of vertices found by traversal...
|
|
|
594 push @{$This->{Vertices}}, $VertexID;
|
|
|
595 }
|
|
|
596
|
|
|
597 # Any active vertices left...
|
|
|
598 if (!@{$This->{ActiveVertices}}) {
|
|
|
599 return $This;
|
|
|
600 }
|
|
|
601
|
|
|
602 # Take it off active vertices list...
|
|
|
603 if ($This->{TraversalType} =~ /^(DFS|DFSWithLimit)$/i) {
|
|
|
604 # For DFS, it's last vertex in LIFO queue...
|
|
|
605 pop @{$This->{ActiveVertices}};
|
|
|
606 }
|
|
|
607 elsif ($This->{TraversalType} =~ /^(BFS|BFSWithLimit)$/i) {
|
|
|
608 # For BFS, it's first vertex in FIFO queue...
|
|
|
609 shift @{$This->{ActiveVertices}};
|
|
|
610 }
|
|
|
611 return $This;
|
|
|
612 }
|
|
|
613
|
|
|
614 # Mark all other downstream neighbor vertices to be ignored from any further
|
|
|
615 # processing...
|
|
|
616 #
|
|
|
617 sub _IgnoreDownstreamNeighbors {
|
|
|
618 my($This, $VertexID, $PredecessorVertexID) = @_;
|
|
|
619
|
|
|
620 if (exists $This->{VerticesToVisit}{$VertexID}) {
|
|
|
621 # Mark vertex as visited vertex and take it out from the list of vertices to visit...
|
|
|
622 $This->{VisitedVertices}{$VertexID} = 1;
|
|
|
623 delete $This->{VerticesToVisit}{$VertexID};
|
|
|
624
|
|
|
625 if (defined($PredecessorVertexID) && $This->{TraversalMode} =~ /^(Path|VertexNeighborhood)$/i) {
|
|
|
626 $This->_ProcessVisitedEdge($VertexID, $PredecessorVertexID);
|
|
|
627 }
|
|
|
628 }
|
|
|
629 my($NeighborVertexID, @NeighborsVertexIDs);
|
|
|
630
|
|
|
631 @NeighborsVertexIDs = ();
|
|
|
632 @NeighborsVertexIDs = $This->{Graph}->GetNeighbors($VertexID);
|
|
|
633 NEIGHBOR: for $NeighborVertexID (@NeighborsVertexIDs) {
|
|
|
634 if (!exists $This->{VerticesToVisit}{$NeighborVertexID}) {
|
|
|
635 # Avoid going back to predecessor vertex which has already been ignored...
|
|
|
636 next NEIGHBOR;
|
|
|
637 }
|
|
|
638 $This->_IgnoreDownstreamNeighbors($NeighborVertexID, $VertexID);
|
|
|
639 }
|
|
|
640 return $This;
|
|
|
641 }
|
|
|
642
|
|
|
643 # Is it a visited edge?
|
|
|
644 #
|
|
|
645 sub _IsVisitedEdge {
|
|
|
646 my($This, $VertexID1, $VertexID2) = @_;
|
|
|
647
|
|
|
648 if (exists $This->{VisitedEdges}->{From}->{$VertexID1}) {
|
|
|
649 if (exists $This->{VisitedEdges}->{From}->{$VertexID1}->{$VertexID2}) {
|
|
|
650 return 1;
|
|
|
651 }
|
|
|
652 }
|
|
|
653 elsif (exists $This->{VisitedEdges}->{To}->{$VertexID2}) {
|
|
|
654 if (exists $This->{VisitedEdges}->{To}->{$VertexID2}->{$VertexID1}) {
|
|
|
655 return 1;
|
|
|
656 }
|
|
|
657 }
|
|
|
658 return 0;
|
|
|
659 }
|
|
|
660
|
|
|
661 # Is it a cycle closure edge?
|
|
|
662 #
|
|
|
663 # Notes:
|
|
|
664 # . Presence of VertexID2 in DFS path traversed for VertexID1 make it a cycle
|
|
|
665 # closure edge...
|
|
|
666 #
|
|
|
667 sub _IsCycleClosureEdge {
|
|
|
668 my($This, $VertexID1, $VertexID2) = @_;
|
|
|
669
|
|
|
670 if (!exists $This->{VerticesPaths}{$VertexID1}) {
|
|
|
671 return 0;
|
|
|
672 }
|
|
|
673 my($Path);
|
|
|
674 for $Path (@{$This->{VerticesPaths}{$VertexID1}}) {
|
|
|
675 if (($Path =~ /-$VertexID2-/ || $Path =~ /^$VertexID2-/ || $Path =~ /-$VertexID2$/)) {
|
|
|
676 return 1;
|
|
|
677 }
|
|
|
678 }
|
|
|
679 return 0;
|
|
|
680 }
|
|
|
681
|
|
|
682 # Search paths starting from a specified vertex with no sharing of edges in paths traversed.
|
|
|
683 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
684 # completing the cycle.
|
|
|
685 #
|
|
|
686 sub PerformPathsSearch {
|
|
|
687 my($This, $StartVertexID, $AllowCycles) = @_;
|
|
|
688
|
|
|
689 # Make sure start vertex is defined...
|
|
|
690 if (!defined $StartVertexID) {
|
|
|
691 carp "Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Start vertex must be specified...";
|
|
|
692 return undef;
|
|
|
693 }
|
|
|
694
|
|
|
695 # Make sure start vertex is valid...
|
|
|
696 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
697 carp "Warning: ${ClassName}->PerformPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
698 return undef;
|
|
|
699 }
|
|
|
700
|
|
|
701 if (!defined $AllowCycles) {
|
|
|
702 $AllowCycles = 1;
|
|
|
703 }
|
|
|
704
|
|
|
705 # Perform paths search...
|
|
|
706 return $This->_PerformPathsSearch("AllLengths", $StartVertexID, $AllowCycles);
|
|
|
707 }
|
|
|
708
|
|
|
709 # Search paths starting from a specified vertex with length upto a specified length
|
|
|
710 # with no sharing of edges in paths traversed...
|
|
|
711 #
|
|
|
712 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
713 # completing the cycle.
|
|
|
714 #
|
|
|
715 sub PerformPathsSearchWithLengthUpto {
|
|
|
716 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
|
|
|
717
|
|
|
718 return $This->_PerformPathsSearchWithLength("LengthUpto", $StartVertexID, $Length, $AllowCycles);
|
|
|
719 }
|
|
|
720
|
|
|
721 # Search paths starting from a specified vertex with specified length
|
|
|
722 # with no sharing of edges in paths traversed...
|
|
|
723 #
|
|
|
724 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
725 # completing the cycle.
|
|
|
726 #
|
|
|
727 sub PerformPathsSearchWithLength {
|
|
|
728 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
|
|
|
729
|
|
|
730 return $This->_PerformPathsSearchWithLength("Length", $StartVertexID, $Length, $AllowCycles);
|
|
|
731 }
|
|
|
732
|
|
|
733
|
|
|
734 # Search paths starting from a specified vertex with length upto a specified length
|
|
|
735 # with no sharing of edges in paths traversed...
|
|
|
736 #
|
|
|
737 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
738 # completing the cycle.
|
|
|
739 #
|
|
|
740 sub _PerformPathsSearchWithLength {
|
|
|
741 my($This, $Mode, $StartVertexID, $Length, $AllowCycles) = @_;
|
|
|
742
|
|
|
743 # Make sure both start vertex and length are defined...
|
|
|
744 if (!defined $StartVertexID) {
|
|
|
745 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Start vertex must be specified...";
|
|
|
746 return undef;
|
|
|
747 }
|
|
|
748 if (!defined $Length) {
|
|
|
749 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Length must be specified...";
|
|
|
750 return undef;
|
|
|
751 }
|
|
|
752
|
|
|
753 if (!defined $AllowCycles) {
|
|
|
754 $AllowCycles = 1;
|
|
|
755 }
|
|
|
756
|
|
|
757 # Make sure both start vertex and length are valid...
|
|
|
758 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
759 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
760 return undef;
|
|
|
761 }
|
|
|
762
|
|
|
763 if ($Length < 1) {
|
|
|
764 carp "Warning: ${ClassName}->_PerformPathsSearchWithLength: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1...";
|
|
|
765 return undef;
|
|
|
766 }
|
|
|
767
|
|
|
768 # Perform paths search...
|
|
|
769 return $This->_PerformPathsSearch($Mode, $StartVertexID, $AllowCycles, $Length);
|
|
|
770 }
|
|
|
771
|
|
|
772 # Search all paths starting from a specified vertex with sharing of edges in paths traversed...
|
|
|
773 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
774 # completing the cycle.
|
|
|
775 #
|
|
|
776 sub PerformAllPathsSearch {
|
|
|
777 my($This, $StartVertexID, $AllowCycles) = @_;
|
|
|
778
|
|
|
779 # Make sure start vertex is defined...
|
|
|
780 if (!defined $StartVertexID) {
|
|
|
781 carp "Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Start vertex must be specified...";
|
|
|
782 return undef;
|
|
|
783 }
|
|
|
784
|
|
|
785 # Make sure start vertex is valid...
|
|
|
786 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
787 carp "Warning: ${ClassName}->PerformAllPathsSearch: No paths search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
788 return undef;
|
|
|
789 }
|
|
|
790
|
|
|
791 if (!defined $AllowCycles) {
|
|
|
792 $AllowCycles = 1;
|
|
|
793 }
|
|
|
794
|
|
|
795 # Perform paths search...
|
|
|
796 return $This->_PerformAllPathsSearch("AllLengths", $StartVertexID, $AllowCycles);
|
|
|
797 }
|
|
|
798
|
|
|
799 # Search all paths starting from a specified vertex with length upto a specified length with sharing of
|
|
|
800 # edges in paths traversed.
|
|
|
801 #
|
|
|
802 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
803 # completing the cycle.
|
|
|
804 #
|
|
|
805 sub PerformAllPathsSearchWithLengthUpto {
|
|
|
806 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
|
|
|
807
|
|
|
808 return $This->_PerformAllPathsSearchWithLength("LengthUpto", $StartVertexID, $Length, $AllowCycles);
|
|
|
809 }
|
|
|
810
|
|
|
811 # Search all paths starting from a specified vertex with specified length with sharing of
|
|
|
812 # edges in paths traversed.
|
|
|
813 #
|
|
|
814 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
815 # completing the cycle.
|
|
|
816 #
|
|
|
817 sub PerformAllPathsSearchWithLength {
|
|
|
818 my($This, $StartVertexID, $Length, $AllowCycles) = @_;
|
|
|
819
|
|
|
820 return $This->_PerformAllPathsSearchWithLength("Length", $StartVertexID, $Length, $AllowCycles);
|
|
|
821 }
|
|
|
822
|
|
|
823 # Search all paths starting from a specified vertex with length upto a specified length with sharing of
|
|
|
824 # edges in paths traversed.
|
|
|
825 #
|
|
|
826 # By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
827 # completing the cycle.
|
|
|
828 #
|
|
|
829 sub _PerformAllPathsSearchWithLength {
|
|
|
830 my($This, $Mode, $StartVertexID, $Length, $AllowCycles) = @_;
|
|
|
831
|
|
|
832 # Make sure both start vertex and length are defined...
|
|
|
833 if (!defined $StartVertexID) {
|
|
|
834 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Start vertex must be specified...";
|
|
|
835 return undef;
|
|
|
836 }
|
|
|
837 if (!defined $Length) {
|
|
|
838 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Length must be specified...";
|
|
|
839 return undef;
|
|
|
840 }
|
|
|
841
|
|
|
842 if (!defined $AllowCycles) {
|
|
|
843 $AllowCycles = 1;
|
|
|
844 }
|
|
|
845
|
|
|
846 # Make sure both start vertex and length are valid...
|
|
|
847 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
848 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
849 return undef;
|
|
|
850 }
|
|
|
851
|
|
|
852 if ($Length < 1) {
|
|
|
853 carp "Warning: ${ClassName}->_PerformAllPathsSearchWithLength: No paths search performed: Specified length, $Length, must be a positive integer with value greater than 1...";
|
|
|
854 return undef;
|
|
|
855 }
|
|
|
856
|
|
|
857 # Perform paths search...
|
|
|
858 return $This->_PerformAllPathsSearch($Mode, $StartVertexID, $AllowCycles, $Length);
|
|
|
859 }
|
|
|
860
|
|
|
861 # Search paths between two vertices...
|
|
|
862 #
|
|
|
863 sub PerformPathsSearchBetween {
|
|
|
864 my($This, $StartVertexID, $EndVertexID) = @_;
|
|
|
865
|
|
|
866 # Make sure start and end vertices are defined...
|
|
|
867 if (!defined $StartVertexID) {
|
|
|
868 carp "Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: Start vertex must be specified...";
|
|
|
869 return undef;
|
|
|
870 }
|
|
|
871 if (!defined $EndVertexID) {
|
|
|
872 carp "Warning: ${ClassName}->PerformPathsSearchBetweeb: No paths search performed: EndVertex vertex must be specified...";
|
|
|
873 return undef;
|
|
|
874 }
|
|
|
875 # Make sure start and end vertices are valid...
|
|
|
876 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
877 carp "Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
878 return undef;
|
|
|
879 }
|
|
|
880 if (!$This->{Graph}->HasVertex($EndVertexID)) {
|
|
|
881 carp "Warning: ${ClassName}->PerformPathsSearchBetween: No paths search performed: Vertex $EndVertexID doesn't exist...";
|
|
|
882 return undef;
|
|
|
883 }
|
|
|
884
|
|
|
885 # Perform paths search...
|
|
|
886 return $This->_PerformPathsSearchBetween($StartVertexID, $EndVertexID);
|
|
|
887 }
|
|
|
888
|
|
|
889 # Search paths starting from root vertex with no sharing of edges...
|
|
|
890 #
|
|
|
891 # Notes:
|
|
|
892 # . Possible paths searche modes are: DFSPathsWithLimit, DFSPaths. And each
|
|
|
893 # of these modes supports any combination of two options: CommonEdges, Cycles.
|
|
|
894 # Default for CommonEdges - No; Cycles - No.
|
|
|
895 #
|
|
|
896 sub _PerformPathsSearch {
|
|
|
897 my($This, $Mode, $RootVertexID, $AllowCycles, $Length) = @_;
|
|
|
898
|
|
|
899 # Perform DFS path search...
|
|
|
900
|
|
|
901 $This->{TraversalMode} = 'Path';
|
|
|
902
|
|
|
903 if ($Mode =~ /^(LengthUpto|Length)$/i) {
|
|
|
904 my($DepthLimit);
|
|
|
905
|
|
|
906 $DepthLimit = $Length - 1;
|
|
|
907 $This->{TraversalType} = 'DFSWithLimit';
|
|
|
908 $This->{DepthLimit} = $DepthLimit;
|
|
|
909 }
|
|
|
910 else {
|
|
|
911 $This->{TraversalType} = 'DFS';
|
|
|
912 }
|
|
|
913 if (defined $RootVertexID) {
|
|
|
914 $This->{RootVertex} = $RootVertexID;
|
|
|
915 }
|
|
|
916
|
|
|
917 $This->{AllowPathCycles} = $AllowCycles;
|
|
|
918
|
|
|
919 # Perform search...
|
|
|
920 $This->_TraverseGraph();
|
|
|
921
|
|
|
922 # Make sure traversal did get the root vertex...
|
|
|
923 if (!exists $This->{VerticesDepth}{$RootVertexID}) {
|
|
|
924 return $This;
|
|
|
925 }
|
|
|
926 if ($Mode =~ /^Length$/i) {
|
|
|
927 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearchWithLength($Length);
|
|
|
928 }
|
|
|
929 else {
|
|
|
930 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearch();
|
|
|
931 }
|
|
|
932
|
|
|
933 return $This;
|
|
|
934 }
|
|
|
935
|
|
|
936 # Search all paths starting from root vertex with sharing of edges...
|
|
|
937 #
|
|
|
938 sub _PerformAllPathsSearch {
|
|
|
939 my($This, $Mode, $RootVertexID, $AllowCycles, $Length) = @_;
|
|
|
940
|
|
|
941 # Perform DFS path search...
|
|
|
942
|
|
|
943 $This->{TraversalMode} = 'AllPaths';
|
|
|
944
|
|
|
945 if ($Mode =~ /^(LengthUpto|Length)$/i) {
|
|
|
946 my($DepthLimit);
|
|
|
947
|
|
|
948 $DepthLimit = $Length - 1;
|
|
|
949 $This->{TraversalType} = 'DFSWithLimit';
|
|
|
950 $This->{DepthLimit} = $DepthLimit;
|
|
|
951 }
|
|
|
952 else {
|
|
|
953 $This->{TraversalType} = 'DFS';
|
|
|
954 }
|
|
|
955 $This->{RootVertex} = $RootVertexID;
|
|
|
956 $This->{AllowPathCycles} = $AllowCycles;
|
|
|
957
|
|
|
958 # Traverse all paths search using DFS search...
|
|
|
959 $This->_TraverseAllPathsInGraph($Mode, $Length);
|
|
|
960
|
|
|
961 return $This;
|
|
|
962 }
|
|
|
963
|
|
|
964 # Travese all paths in graph starting from a specified root vertex...
|
|
|
965 #
|
|
|
966 sub _TraverseAllPathsInGraph {
|
|
|
967 my($This, $Mode, $Length) = @_;
|
|
|
968
|
|
|
969 if ($This->{TraversalMode} !~ /^AllPaths$/i) {
|
|
|
970 return $This;
|
|
|
971 }
|
|
|
972 my($CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath);
|
|
|
973
|
|
|
974 $CurrentVertexID = $This->{RootVertex};
|
|
|
975 $PredecessorVertexID = $CurrentVertexID;
|
|
|
976 $CurrentDepth = 0;
|
|
|
977 $CurrentPath = "$CurrentVertexID";
|
|
|
978
|
|
|
979 $This->_TraverseAllPaths($CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath);
|
|
|
980
|
|
|
981 if ($Mode =~ /^Length$/i) {
|
|
|
982 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearchWithLength($Length);
|
|
|
983 }
|
|
|
984 else {
|
|
|
985 push @{$This->{Paths}}, $This->_CollectPathsTraversedDuringPathsSearch();
|
|
|
986 }
|
|
|
987
|
|
|
988 return $This;
|
|
|
989 }
|
|
|
990
|
|
|
991 # Traverse and collect all paths recuresively..
|
|
|
992 #
|
|
|
993 sub _TraverseAllPaths {
|
|
|
994 my($This, $CurrentVertexID, $PredecessorVertexID, $CurrentDepth, $CurrentPath) = @_;
|
|
|
995
|
|
|
996 # Save path traversed for current vertex..
|
|
|
997 if (!exists $This->{VerticesPaths}{$CurrentVertexID}) {
|
|
|
998 @{$This->{VerticesPaths}{$CurrentVertexID}} = ();
|
|
|
999 $This->{VerticesDepth}{$CurrentVertexID} = 0;
|
|
|
1000 }
|
|
|
1001 push @{$This->{VerticesPaths}{$CurrentVertexID}}, $CurrentPath;
|
|
|
1002 $This->{VerticesDepth}{$CurrentVertexID} = $CurrentDepth;
|
|
|
1003
|
|
|
1004 $CurrentDepth++;
|
|
|
1005 if (exists $This->{DepthLimit}) {
|
|
|
1006 if ($CurrentDepth > $This->{DepthLimit}) {
|
|
|
1007 # Nothing more to do...
|
|
|
1008 return $This;
|
|
|
1009 }
|
|
|
1010 }
|
|
|
1011 my($NeighborVertexID, $NewPath);
|
|
|
1012
|
|
|
1013 NEIGHBOR: for $NeighborVertexID ($This->{Graph}->GetNeighbors($CurrentVertexID)) {
|
|
|
1014 if ($NeighborVertexID == $PredecessorVertexID) {
|
|
|
1015 next NEIGHBOR;
|
|
|
1016 }
|
|
|
1017 if ($This->_IsVertexInTraversedPath($NeighborVertexID, $CurrentPath)) {
|
|
|
1018 # It's a cycle...
|
|
|
1019 if ($This->{AllowPathCycles}) {
|
|
|
1020 $NewPath = "${CurrentPath}-${NeighborVertexID}";
|
|
|
1021 if (!exists $This->{VerticesPaths}{$NeighborVertexID}) {
|
|
|
1022 @{$This->{VerticesPaths}{$NeighborVertexID}} = ();
|
|
|
1023 }
|
|
|
1024 push @{$This->{VerticesPaths}{$NeighborVertexID}}, $NewPath;
|
|
|
1025 }
|
|
|
1026 next NEIGHBOR;
|
|
|
1027 }
|
|
|
1028 $NewPath = "${CurrentPath}-${NeighborVertexID}";
|
|
|
1029 $This->_TraverseAllPaths($NeighborVertexID, $CurrentVertexID, $CurrentDepth, $NewPath);
|
|
|
1030 }
|
|
|
1031 return $This;
|
|
|
1032 }
|
|
|
1033
|
|
|
1034 # Is vertex already in traversed path?
|
|
|
1035 #
|
|
|
1036 sub _IsVertexInTraversedPath {
|
|
|
1037 my($This, $VertexID, $Path) = @_;
|
|
|
1038
|
|
|
1039 return ($Path =~ /-$VertexID-/ || $Path =~ /^$VertexID-/ || $Path =~ /-$VertexID$/) ? 1 : 0;
|
|
|
1040 }
|
|
|
1041
|
|
|
1042 # Collect all paths traversed during Path TraversalMode and sort 'em in
|
|
|
1043 # ascending order of lengths
|
|
|
1044 #
|
|
|
1045 sub _CollectPathsTraversedDuringPathsSearch {
|
|
|
1046 my($This) = @_;
|
|
|
1047 my($VertexID, @Paths, @SortedPaths);
|
|
|
1048
|
|
|
1049 @Paths = (); @SortedPaths = ();
|
|
|
1050
|
|
|
1051 # Create path objects from path vertex strings...
|
|
|
1052 for $VertexID (keys %{$This->{VerticesPaths}}) {
|
|
|
1053 push @Paths, map { new Graph::Path(split /-/, $_) } @{$This->{VerticesPaths}{$VertexID}};
|
|
|
1054 }
|
|
|
1055
|
|
|
1056 # Sort paths in ascending order of lengths...
|
|
|
1057 push @SortedPaths, sort { $a->GetLength() <=> $b->GetLength() } @Paths;
|
|
|
1058
|
|
|
1059 return @SortedPaths;
|
|
|
1060 }
|
|
|
1061
|
|
|
1062 # Collect paths traversed during Path TraversalMode with specific length...
|
|
|
1063 #
|
|
|
1064 sub _CollectPathsTraversedDuringPathsSearchWithLength {
|
|
|
1065 my($This, $Length) = @_;
|
|
|
1066 my($VertexID, $Depth, $PathString, @VertexIDs, @Paths);
|
|
|
1067
|
|
|
1068 @Paths = ();
|
|
|
1069 $Depth = $Length - 1;
|
|
|
1070
|
|
|
1071 # Create path objects from path vertex strings...
|
|
|
1072 VERTEXID: for $VertexID (keys %{$This->{VerticesPaths}}) {
|
|
|
1073 if ($This->{VerticesDepth}{$VertexID} != $Depth) {
|
|
|
1074 next VERTEXID;
|
|
|
1075 }
|
|
|
1076 # For vertices involved in cycles, the path might also contain some shorter paths. So check
|
|
|
1077 # the lengths before its collection...
|
|
|
1078 PATHSTRING: for $PathString (@{$This->{VerticesPaths}{$VertexID}}) {
|
|
|
1079 @VertexIDs = split /-/, $PathString;
|
|
|
1080 if ($Length != @VertexIDs) {
|
|
|
1081 next PATHSTRING;
|
|
|
1082 }
|
|
|
1083 push @Paths, new Graph::Path(@VertexIDs);
|
|
|
1084 }
|
|
|
1085 }
|
|
|
1086 return @Paths;
|
|
|
1087 }
|
|
|
1088
|
|
|
1089 # Collect paths traversed during Vertex TraversalMode...
|
|
|
1090 #
|
|
|
1091 sub _CollectPathsTraversedDuringVertexSearch {
|
|
|
1092 my($This, $RootVertexID) = @_;
|
|
|
1093 my($Depth, @Paths, @VerticesAtDepth);
|
|
|
1094 @Paths = ();
|
|
|
1095
|
|
|
1096 # Get vertices at specific depths...
|
|
|
1097 @VerticesAtDepth = ();
|
|
|
1098 @VerticesAtDepth = $This->_CollectVerticesAtSpecificDepths();
|
|
|
1099 if (!@VerticesAtDepth) {
|
|
|
1100 return @Paths;
|
|
|
1101 }
|
|
|
1102
|
|
|
1103 # Make sure search found only one root vertex and it corresponds to
|
|
|
1104 # what was specified...
|
|
|
1105 $Depth = 0;
|
|
|
1106 if ((@{$VerticesAtDepth[$Depth]} > 1) || ($VerticesAtDepth[$Depth][0] != $RootVertexID)) {
|
|
|
1107 carp "Warning: ${ClassName}->_PerformPathsSearch: No paths found: Root vertex, $VerticesAtDepth[$Depth][0], identified by paths traversal doen't match specified root vertex $RootVertexID...";
|
|
|
1108 return @Paths;
|
|
|
1109 }
|
|
|
1110
|
|
|
1111 # Setup root vertex at depth 0. And set its path...
|
|
|
1112 my($Path, $VertexID, $SuccessorVertexID, @VertexIDs, %PathAtVertex);
|
|
|
1113 %PathAtVertex = ();
|
|
|
1114 $PathAtVertex{$RootVertexID} = new Graph::Path($RootVertexID);
|
|
|
1115
|
|
|
1116 for $Depth (0 .. $#VerticesAtDepth) {
|
|
|
1117 # Go over all vertices at current depth...
|
|
|
1118 VERTEX: for $VertexID (@{$VerticesAtDepth[$Depth]}) {
|
|
|
1119 if (!exists $This->{VerticesSuccessors}{$VertexID}) {
|
|
|
1120 next VERTEX;
|
|
|
1121 }
|
|
|
1122 # Get vertices for current path...
|
|
|
1123 @VertexIDs = ();
|
|
|
1124 push @VertexIDs, $PathAtVertex{$VertexID}->GetVertices;
|
|
|
1125
|
|
|
1126 # Expand path to successor vertex found during traversal...
|
|
|
1127 for $SuccessorVertexID (@{$This->{VerticesSuccessors}{$VertexID}}) {
|
|
|
1128 $Path = new Graph::Path(@VertexIDs);
|
|
|
1129 $Path->AddVertex($SuccessorVertexID);
|
|
|
1130 $PathAtVertex{$SuccessorVertexID} = $Path;
|
|
|
1131 }
|
|
|
1132 }
|
|
|
1133 }
|
|
|
1134 # Sort paths in ascending order of lengths...
|
|
|
1135 push @Paths, sort { $a->GetLength() <=> $b->GetLength() } values %PathAtVertex;
|
|
|
1136
|
|
|
1137 return @Paths;
|
|
|
1138 }
|
|
|
1139
|
|
|
1140 # Collect vertices at specific depths. Depth values start from 0...
|
|
|
1141 #
|
|
|
1142 sub _CollectVerticesAtSpecificDepths {
|
|
|
1143 my($This) = @_;
|
|
|
1144 my($VertexID, $Depth, @VerticesAtDepth);
|
|
|
1145
|
|
|
1146 @VerticesAtDepth = ();
|
|
|
1147 while (($VertexID, $Depth) = each %{$This->{VerticesDepth}}) {
|
|
|
1148 push @{$VerticesAtDepth[$Depth]}, $VertexID;
|
|
|
1149 }
|
|
|
1150 return @VerticesAtDepth;
|
|
|
1151 }
|
|
|
1152
|
|
|
1153 # Collect vertices, along with their successors, at specific depths and return a list containing references to
|
|
|
1154 # lists with first value corresponding to vertex ID and second value a reference to a list containing
|
|
|
1155 # its successors.
|
|
|
1156 #
|
|
|
1157 # Depth values start from 0...
|
|
|
1158 #
|
|
|
1159 sub _CollectVerticesWithSuccessorsAtSpecificDepths {
|
|
|
1160 my($This) = @_;
|
|
|
1161 my($VertexID, $Depth, @VerticesWithSuccessorsAtDepth);
|
|
|
1162
|
|
|
1163 @VerticesWithSuccessorsAtDepth = ();
|
|
|
1164 while (($VertexID, $Depth) = each %{$This->{VerticesDepth}}) {
|
|
|
1165 my(@VertexWithSuccessors, @VertexSuccessors);
|
|
|
1166
|
|
|
1167 @VertexWithSuccessors = (); @VertexSuccessors = ();
|
|
|
1168 if (exists $This->{VerticesSuccessors}{$VertexID}) {
|
|
|
1169 push @VertexSuccessors, @{$This->{VerticesSuccessors}{$VertexID}};
|
|
|
1170 }
|
|
|
1171 push @VertexWithSuccessors, ($VertexID, \@VertexSuccessors);
|
|
|
1172 # Multiple entries for a vertex and its successors could be present at a specific depth...
|
|
|
1173 push @{$VerticesWithSuccessorsAtDepth[$Depth]}, \@VertexWithSuccessors;
|
|
|
1174 }
|
|
|
1175 return @VerticesWithSuccessorsAtDepth;
|
|
|
1176 }
|
|
|
1177
|
|
|
1178 # Search paths between two vertices...
|
|
|
1179 #
|
|
|
1180 sub _PerformPathsSearchBetween {
|
|
|
1181 my($This, $RootVertexID, $TargetVertexID) = @_;
|
|
|
1182 my($DepthLimit);
|
|
|
1183
|
|
|
1184 # Perform a targeted DFS search...
|
|
|
1185 $DepthLimit = undef;
|
|
|
1186 $This->_PerformVertexSearch("DFS", $RootVertexID, $DepthLimit, $TargetVertexID);
|
|
|
1187
|
|
|
1188 my($Path);
|
|
|
1189 $Path = $This->_CollectPathBetween($RootVertexID, $TargetVertexID);
|
|
|
1190
|
|
|
1191 if (defined $Path) {
|
|
|
1192 push @{$This->{Paths}}, $Path;
|
|
|
1193 }
|
|
|
1194 return $This;
|
|
|
1195 }
|
|
|
1196
|
|
|
1197 # Collect path between root and target vertex after the search...
|
|
|
1198 #
|
|
|
1199 sub _CollectPathBetween {
|
|
|
1200 my($This, $RootVertexID, $TargetVertexID) = @_;
|
|
|
1201
|
|
|
1202 # Does a path from root to target vertex exist?
|
|
|
1203 if (!(exists($This->{VerticesRoots}{$TargetVertexID}) && ($This->{VerticesRoots}{$TargetVertexID} == $RootVertexID))) {
|
|
|
1204 return undef;
|
|
|
1205 }
|
|
|
1206
|
|
|
1207 # Add target vertex ID path vertices...
|
|
|
1208 my($VertexID, $Path, @VertexIDs);
|
|
|
1209 @VertexIDs = ();
|
|
|
1210 $VertexID = $TargetVertexID;
|
|
|
1211 push @VertexIDs, $VertexID;
|
|
|
1212
|
|
|
1213 # Backtrack to root vertex ID...
|
|
|
1214 while ($This->{VerticesPredecessors}{$VertexID} != $VertexID) {
|
|
|
1215 $VertexID = $This->{VerticesPredecessors}{$VertexID};
|
|
|
1216 push @VertexIDs, $VertexID;
|
|
|
1217 }
|
|
|
1218
|
|
|
1219 # Create path from target to root and reverse it...
|
|
|
1220 $Path = new Graph::Path(@VertexIDs);
|
|
|
1221 $Path->Reverse();
|
|
|
1222
|
|
|
1223 return $Path;
|
|
|
1224 }
|
|
|
1225
|
|
|
1226 # Search vertices around specified root vertex with in specific neighborhood radius...
|
|
|
1227 #
|
|
|
1228 sub PerformNeighborhoodVerticesSearchWithRadiusUpto {
|
|
|
1229 my($This, $StartVertexID, $Radius) = @_;
|
|
|
1230
|
|
|
1231 # Make sure both start vertex and radius are defined...
|
|
|
1232 if (!defined $StartVertexID) {
|
|
|
1233 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Start vertex must be specified...";
|
|
|
1234 return undef;
|
|
|
1235 }
|
|
|
1236 if (!defined $Radius) {
|
|
|
1237 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Radius must be specified...";
|
|
|
1238 return undef;
|
|
|
1239 }
|
|
|
1240
|
|
|
1241 # Make sure both start vertex and length are valid...
|
|
|
1242 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
1243 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
1244 return undef;
|
|
|
1245 }
|
|
|
1246 if ($Radius < 0) {
|
|
|
1247 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithRadiusUpto: No vertices search performed: Specified radius, $Radius, must be a positive integer...";
|
|
|
1248 return undef;
|
|
|
1249 }
|
|
|
1250
|
|
|
1251 # Perform vertices search...
|
|
|
1252 return $This->_PerformNeighborhoodVerticesSearch("RadiusUpto", $StartVertexID, $Radius);
|
|
|
1253 }
|
|
|
1254
|
|
|
1255 # Search vertices around specified root vertex...
|
|
|
1256 #
|
|
|
1257 sub PerformNeighborhoodVerticesSearch {
|
|
|
1258 my($This, $StartVertexID) = @_;
|
|
|
1259
|
|
|
1260 # Make sure start vertex is defined...
|
|
|
1261 if (!defined $StartVertexID) {
|
|
|
1262 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Start vertex must be specified...";
|
|
|
1263 return undef;
|
|
|
1264 }
|
|
|
1265
|
|
|
1266 # Make sure start vertex is valid...
|
|
|
1267 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
1268 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearch: No vertices search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
1269 return undef;
|
|
|
1270 }
|
|
|
1271 # Perform vertices search...
|
|
|
1272 return $This->_PerformNeighborhoodVerticesSearch("AllRadii", $StartVertexID);
|
|
|
1273 }
|
|
|
1274
|
|
|
1275 # Search vertices around specified root vertex with in specific neighborhood radius along with
|
|
|
1276 # identification of successors of each vertex found during the search...
|
|
|
1277 #
|
|
|
1278 sub PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto {
|
|
|
1279 my($This, $StartVertexID, $Radius) = @_;
|
|
|
1280
|
|
|
1281 # Make sure both start vertex and radius are defined...
|
|
|
1282 if (!defined $StartVertexID) {
|
|
|
1283 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Start vertex must be specified...";
|
|
|
1284 return undef;
|
|
|
1285 }
|
|
|
1286 if (!defined $Radius) {
|
|
|
1287 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Radius must be specified...";
|
|
|
1288 return undef;
|
|
|
1289 }
|
|
|
1290
|
|
|
1291 # Make sure both start vertex and length are valid...
|
|
|
1292 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
1293 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
1294 return undef;
|
|
|
1295 }
|
|
|
1296 if ($Radius < 0) {
|
|
|
1297 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto: No vertices search performed: Specified radius, $Radius, must be a positive integer...";
|
|
|
1298 return undef;
|
|
|
1299 }
|
|
|
1300
|
|
|
1301 # Perform vertices search...
|
|
|
1302 return $This->_PerformNeighborhoodVerticesSearch("WithSuccessorsAndRadiusUpto", $StartVertexID, $Radius);
|
|
|
1303 }
|
|
|
1304
|
|
|
1305 # Search vertices around specified root vertex along with identification of
|
|
|
1306 # successors of each vertex found during the search...
|
|
|
1307 #
|
|
|
1308 sub PerformNeighborhoodVerticesSearchWithSuccessors {
|
|
|
1309 my($This, $StartVertexID) = @_;
|
|
|
1310
|
|
|
1311 # Make sure start vertex is defined...
|
|
|
1312 if (!defined $StartVertexID) {
|
|
|
1313 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessors: No vertices search performed: Start vertex must be specified...";
|
|
|
1314 return undef;
|
|
|
1315 }
|
|
|
1316
|
|
|
1317 # Make sure start vertex is valid...
|
|
|
1318 if (!$This->{Graph}->HasVertex($StartVertexID)) {
|
|
|
1319 carp "Warning: ${ClassName}->PerformNeighborhoodVerticesSearchWithSuccessors: No vertices search performed: Vertex $StartVertexID doesn't exist...";
|
|
|
1320 return undef;
|
|
|
1321 }
|
|
|
1322 # Perform vertices search...
|
|
|
1323 return $This->_PerformNeighborhoodVerticesSearch("WithSuccessorsAndAllRadii", $StartVertexID);
|
|
|
1324 }
|
|
|
1325
|
|
|
1326 # Search vertices at successive neighborhood radii levels...
|
|
|
1327 #
|
|
|
1328 sub _PerformNeighborhoodVerticesSearch {
|
|
|
1329 my($This, $Mode, $RootVertexID, $Radius) = @_;
|
|
|
1330 my($DepthLimit, $AllowCycles);
|
|
|
1331
|
|
|
1332 $DepthLimit = defined $Radius ? $Radius : undef;
|
|
|
1333 $AllowCycles = undef;
|
|
|
1334
|
|
|
1335 # Perform BFS search...
|
|
|
1336 if ($Mode =~ /^RadiusUpto$/i) {
|
|
|
1337 $This->_PerformVertexNeighborhoodSearch("BFSWithLimit", $RootVertexID, $DepthLimit);
|
|
|
1338 }
|
|
|
1339 elsif ($Mode =~ /^(AllRadii)$/i) {
|
|
|
1340 $This->_PerformVertexNeighborhoodSearch("BFS", $RootVertexID);
|
|
|
1341 }
|
|
|
1342 elsif ($Mode =~ /^WithSuccessorsAndRadiusUpto$/i) {
|
|
|
1343 $AllowCycles = 1;
|
|
|
1344 $This->_PerformVertexNeighborhoodSearch("BFSWithLimit", $RootVertexID, $DepthLimit, $AllowCycles);
|
|
|
1345 }
|
|
|
1346 elsif ($Mode =~ /^WithSuccessorsAndAllRadii$/i) {
|
|
|
1347 $AllowCycles = 1;
|
|
|
1348 $This->_PerformVertexNeighborhoodSearch("BFSWithLimit", $RootVertexID, $DepthLimit, $AllowCycles);
|
|
|
1349 }
|
|
|
1350
|
|
|
1351 # Make sure traversal did get the root vertex...
|
|
|
1352 if (!exists $This->{VerticesDepth}{$RootVertexID}) {
|
|
|
1353 return $This;
|
|
|
1354 }
|
|
|
1355
|
|
|
1356 if ($Mode =~ /^(RadiusUpto|AllRadii)$/i) {
|
|
|
1357 push @{$This->{VerticesNeighborhoods}}, $This->_CollectVerticesAtSpecificDepths();
|
|
|
1358 }
|
|
|
1359 elsif ($Mode =~ /^(WithSuccessorsAndRadiusUpto|WithSuccessorsAndAllRadii)$/i) {
|
|
|
1360 push @{$This->{VerticesNeighborhoodsWithSuccessors}}, $This->_CollectVerticesWithSuccessorsAtSpecificDepths();
|
|
|
1361 }
|
|
|
1362
|
|
|
1363 return $This;
|
|
|
1364 }
|
|
|
1365
|
|
|
1366 # Perform appropriate vertex search...
|
|
|
1367 #
|
|
|
1368 sub _PerformVertexNeighborhoodSearch {
|
|
|
1369 my($This, $SearchType, $RootVertexID, $DepthLimit, $AllowCycles) = @_;
|
|
|
1370
|
|
|
1371 # Setup search...
|
|
|
1372 $This->{TraversalMode} = 'VertexNeighborhood';
|
|
|
1373 $This->{TraversalType} = $SearchType;
|
|
|
1374
|
|
|
1375 if (defined $RootVertexID) {
|
|
|
1376 $This->{RootVertex} = $RootVertexID;
|
|
|
1377 }
|
|
|
1378 if (defined $DepthLimit) {
|
|
|
1379 $This->{DepthLimit} = $DepthLimit;
|
|
|
1380 }
|
|
|
1381 if (defined $AllowCycles) {
|
|
|
1382 $This->{AllowVertexCycles} = $AllowCycles;
|
|
|
1383 }
|
|
|
1384
|
|
|
1385 # Perform search...
|
|
|
1386 return $This->_TraverseGraph();
|
|
|
1387 }
|
|
|
1388
|
|
|
1389 # Get orderded list of vertices after DFS/BFS search...
|
|
|
1390 #
|
|
|
1391 sub GetVertices {
|
|
|
1392 my($This) = @_;
|
|
|
1393
|
|
|
1394 return wantarray ? @{$This->{Vertices}} : scalar @{$This->{Vertices}};
|
|
|
1395 }
|
|
|
1396
|
|
|
1397 # Get a hash list containing vertex and root vertex as key/value pair for all vertices
|
|
|
1398 # ordered using DFS/BFS search available via GetVertices method...
|
|
|
1399 #
|
|
|
1400 sub GetVerticesRoots {
|
|
|
1401 my($This) = @_;
|
|
|
1402
|
|
|
1403 return %{$This->{VerticesRoots}};
|
|
|
1404 }
|
|
|
1405
|
|
|
1406 # Get a list containing lists of vertices in connected components of graph after DFS/BFS
|
|
|
1407 # search...
|
|
|
1408 #
|
|
|
1409 # Note:
|
|
|
1410 # . List is sorted in descending order of number of vertices in each connected component.
|
|
|
1411 #
|
|
|
1412 sub GetConnectedComponentsVertices {
|
|
|
1413 my($This) = @_;
|
|
|
1414 my($VertexID, $VertexRoot, @ConnectedVertices, %VerticesAtRoot);
|
|
|
1415
|
|
|
1416 @ConnectedVertices = ();
|
|
|
1417 %VerticesAtRoot = ();
|
|
|
1418 for $VertexID (@{$This->{Vertices}}) {
|
|
|
1419 $VertexRoot = $This->{VerticesRoots}{$VertexID};
|
|
|
1420 if (!exists $VerticesAtRoot{$VertexRoot}) {
|
|
|
1421 @{$VerticesAtRoot{$VertexRoot}} = ();
|
|
|
1422 }
|
|
|
1423 push @{$VerticesAtRoot{$VertexRoot}}, $VertexID;
|
|
|
1424 }
|
|
|
1425 push @ConnectedVertices, sort { @{$b} <=> @{$a} } values %VerticesAtRoot;
|
|
|
1426
|
|
|
1427 return wantarray ? @ConnectedVertices : scalar @ConnectedVertices;
|
|
|
1428 }
|
|
|
1429
|
|
|
1430 # Get predecessor vertices...
|
|
|
1431 #
|
|
|
1432 sub GetVerticesPredecessors {
|
|
|
1433 my($This) = @_;
|
|
|
1434
|
|
|
1435 return %{$This->{VerticesPredecessors}};
|
|
|
1436 }
|
|
|
1437
|
|
|
1438 # Get a hash list containing vertex and depth from root vertex as key/value pair for all vertices
|
|
|
1439 # ordered using DFS/BFS search available via GetVertices method...
|
|
|
1440 #
|
|
|
1441 sub GetVerticesDepth {
|
|
|
1442 my($This) = @_;
|
|
|
1443
|
|
|
1444 return %{$This->{VerticesDepth}};
|
|
|
1445 }
|
|
|
1446
|
|
|
1447 # Get paths found during paths search...
|
|
|
1448 #
|
|
|
1449 sub GetPaths {
|
|
|
1450 my($This) = @_;
|
|
|
1451
|
|
|
1452 return wantarray ? @{$This->{Paths}} : scalar @{$This->{Paths}};
|
|
|
1453 }
|
|
|
1454
|
|
|
1455 # Get vertices collected at various neighborhood radii...
|
|
|
1456 #
|
|
|
1457 sub GetVerticesNeighborhoods {
|
|
|
1458 my($This) = @_;
|
|
|
1459
|
|
|
1460 return wantarray ? @{$This->{VerticesNeighborhoods}} : scalar @{$This->{VerticesNeighborhoods}};
|
|
|
1461 }
|
|
|
1462
|
|
|
1463 # Get vertices, along with their successor vertices, collected at various neighborhood radii as
|
|
|
1464 # a list containing references to lists with first value corresponding to vertex ID and second value
|
|
|
1465 # a reference to a list containing its successors.
|
|
|
1466 #
|
|
|
1467 sub GetVerticesNeighborhoodsWithSuccessors {
|
|
|
1468 my($This) = @_;
|
|
|
1469
|
|
|
1470 return wantarray ? @{$This->{VerticesNeighborhoodsWithSuccessors}} : scalar @{$This->{VerticesNeighborhoodsWithSuccessors}};
|
|
|
1471 }
|
|
|
1472
|
|
|
1473 # Return a string containg data for PathsTraversal object...
|
|
|
1474 sub StringifyPathsTraversal {
|
|
|
1475 my($This) = @_;
|
|
|
1476 my($PathsTraversalString);
|
|
|
1477
|
|
|
1478 $PathsTraversalString = "PathsTraversalMode: " . $This->{TraversalMode};
|
|
|
1479 $PathsTraversalString .= "; PathsTraversalType: " . $This->{TraversalType};
|
|
|
1480
|
|
|
1481 # Vertices ordered by traversal...
|
|
|
1482 $PathsTraversalString .= "; Vertices: " . join(' ', @{$This->{Vertices}});
|
|
|
1483
|
|
|
1484 # Stringify depths of vertices...
|
|
|
1485 $PathsTraversalString .= "; " . $This->StringifyVerticesDepth();
|
|
|
1486
|
|
|
1487 # Stringify roots of vertices...
|
|
|
1488 $PathsTraversalString .= "; " . $This->StringifyVerticesRoots();
|
|
|
1489
|
|
|
1490 # Stringify predecessor of vertices...
|
|
|
1491 $PathsTraversalString .= "; " . $This->StringifyVerticesPredecessors();
|
|
|
1492
|
|
|
1493 # Stringify successor vertices...
|
|
|
1494 $PathsTraversalString .= "; " . $This->StringifyVerticesSuccessors();
|
|
|
1495
|
|
|
1496 # Stringify paths...
|
|
|
1497 $PathsTraversalString .= "; " . $This->StringifyPaths();
|
|
|
1498
|
|
|
1499 # Stringify vertices neighborhoods...
|
|
|
1500 $PathsTraversalString .= "; " . $This->StringifyVerticesNeighborhoods();
|
|
|
1501
|
|
|
1502 # Stringify vertices neighborhoods with successors...
|
|
|
1503 $PathsTraversalString .= "; " . $This->StringifyVerticesNeighborhoodsWithSuccessors();
|
|
|
1504
|
|
|
1505 return $PathsTraversalString;
|
|
|
1506 }
|
|
|
1507
|
|
|
1508 # Stringify vertices depth...
|
|
|
1509 #
|
|
|
1510 sub StringifyVerticesDepth {
|
|
|
1511 my($This) = @_;
|
|
|
1512 my($VertexID, $VertexDepth, $DepthString);
|
|
|
1513
|
|
|
1514 if (!@{$This->{Vertices}}) {
|
|
|
1515 $DepthString = "<Vertex-Depth>: None";
|
|
|
1516 return $DepthString;
|
|
|
1517 }
|
|
|
1518
|
|
|
1519 $DepthString = "<Vertex-Depth>: ";
|
|
|
1520 for $VertexID (@{$This->{Vertices}}) {
|
|
|
1521 $VertexDepth = $This->{VerticesDepth}{$VertexID};
|
|
|
1522 $DepthString .= " <$VertexID-$VertexDepth>";
|
|
|
1523 }
|
|
|
1524 return $DepthString;
|
|
|
1525 }
|
|
|
1526
|
|
|
1527 # Stringify roots of vertices...
|
|
|
1528 #
|
|
|
1529 sub StringifyVerticesRoots {
|
|
|
1530 my($This) = @_;
|
|
|
1531 my($VertexID, $RootVertexID, $RootsString);
|
|
|
1532
|
|
|
1533 if (!@{$This->{Vertices}}) {
|
|
|
1534 $RootsString = "<Vertex-RootVertex>: None";
|
|
|
1535 return $RootsString;
|
|
|
1536 }
|
|
|
1537
|
|
|
1538 $RootsString = "<Vertex-RootVertex>: ";
|
|
|
1539 for $VertexID (@{$This->{Vertices}}) {
|
|
|
1540 $RootVertexID = $This->{VerticesRoots}{$VertexID};
|
|
|
1541 $RootsString .= " <$VertexID-$RootVertexID>";
|
|
|
1542 }
|
|
|
1543 return $RootsString;
|
|
|
1544 }
|
|
|
1545
|
|
|
1546 # Stringify predecessor of vertices...
|
|
|
1547 #
|
|
|
1548 sub StringifyVerticesPredecessors {
|
|
|
1549 my($This) = @_;
|
|
|
1550 my($VertexID, $PredecessorVertexID, $PredecessorString);
|
|
|
1551
|
|
|
1552 if (!@{$This->{Vertices}}) {
|
|
|
1553 $PredecessorString = "<Vertex-PredecessorVertex>: None";
|
|
|
1554 return $PredecessorString;
|
|
|
1555 }
|
|
|
1556
|
|
|
1557 $PredecessorString = "<Vertex-PredecessorVertex>: ";
|
|
|
1558 for $VertexID (@{$This->{Vertices}}) {
|
|
|
1559 $PredecessorVertexID = $This->{VerticesPredecessors}{$VertexID};
|
|
|
1560 $PredecessorString .= " <$VertexID-$PredecessorVertexID>";
|
|
|
1561 }
|
|
|
1562 return $PredecessorString;
|
|
|
1563 }
|
|
|
1564
|
|
|
1565 # Stringify successor vertices...
|
|
|
1566 #
|
|
|
1567 sub StringifyVerticesSuccessors {
|
|
|
1568 my($This) = @_;
|
|
|
1569 my($VertexID, $SuccessorString, $VerticesSuccessorsString);
|
|
|
1570
|
|
|
1571 if (!@{$This->{Vertices}}) {
|
|
|
1572 $SuccessorString = "<Vertex-VerticesSuccessorsList>: None";
|
|
|
1573 return $SuccessorString;
|
|
|
1574 }
|
|
|
1575
|
|
|
1576 $SuccessorString = "<Vertex-VerticesSuccessorsList>: ";
|
|
|
1577 for $VertexID (@{$This->{Vertices}}) {
|
|
|
1578 if (exists($This->{VerticesSuccessors}{$VertexID}) && @{$This->{VerticesSuccessors}{$VertexID}}) {
|
|
|
1579 $VerticesSuccessorsString = join(',', @{$This->{VerticesSuccessors}{$VertexID}});
|
|
|
1580 }
|
|
|
1581 else {
|
|
|
1582 $VerticesSuccessorsString = "None";
|
|
|
1583 }
|
|
|
1584 $SuccessorString .= " <$VertexID-$VerticesSuccessorsString>";
|
|
|
1585 }
|
|
|
1586 return $SuccessorString;
|
|
|
1587 }
|
|
|
1588
|
|
|
1589 # Strinigify paths...
|
|
|
1590 #
|
|
|
1591 sub StringifyPaths {
|
|
|
1592 my($This) = @_;
|
|
|
1593 my($PathsString, $Path);
|
|
|
1594
|
|
|
1595 if (!@{$This->{Paths}}) {
|
|
|
1596 $PathsString = "Paths: None";
|
|
|
1597 return $PathsString;
|
|
|
1598 }
|
|
|
1599
|
|
|
1600 my($FirstPath);
|
|
|
1601 $PathsString = "Paths: ";
|
|
|
1602 $FirstPath = 1;
|
|
|
1603 for $Path (@{$This->{Paths}}) {
|
|
|
1604 if ($FirstPath) {
|
|
|
1605 $FirstPath = 0;
|
|
|
1606 }
|
|
|
1607 else {
|
|
|
1608 $PathsString .= " ";
|
|
|
1609 }
|
|
|
1610 $PathsString .= "<" . join('-', $Path->GetVertices()) . ">";
|
|
|
1611 }
|
|
|
1612 return $PathsString;
|
|
|
1613 }
|
|
|
1614
|
|
|
1615 # Strinigify vertices neighborhoods...
|
|
|
1616 #
|
|
|
1617 sub StringifyVerticesNeighborhoods {
|
|
|
1618 my($This) = @_;
|
|
|
1619 my($NeighborhoodsString, $NeighborhoodVerticesString, $Radius);
|
|
|
1620
|
|
|
1621 if (!@{$This->{VerticesNeighborhoods}}) {
|
|
|
1622 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVerticesList>: None";
|
|
|
1623 return $NeighborhoodsString;
|
|
|
1624 }
|
|
|
1625 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVerticesList>:";
|
|
|
1626 for $Radius (0 .. $#{$This->{VerticesNeighborhoods}}) {
|
|
|
1627 $NeighborhoodVerticesString = join(',', @{$This->{VerticesNeighborhoods}[$Radius]});
|
|
|
1628 $NeighborhoodsString .= " <$Radius-$NeighborhoodVerticesString>";
|
|
|
1629 }
|
|
|
1630
|
|
|
1631 return $NeighborhoodsString;
|
|
|
1632 }
|
|
|
1633
|
|
|
1634 # Strinigify vertices neighborhoods...
|
|
|
1635 #
|
|
|
1636 sub StringifyVerticesNeighborhoodsWithSuccessors {
|
|
|
1637 my($This) = @_;
|
|
|
1638 my($NeighborhoodsString, $NeighborhoodVertexSuccessorsString, $Radius, $NeighborhoodVertericesWithSuccessorsRef, $NeighborhoodVertexWithSuccessorsRef, $VertexID, $NeighborhoodVertexSuccessorsRef);
|
|
|
1639
|
|
|
1640 if (!@{$This->{VerticesNeighborhoodsWithSuccessors}}) {
|
|
|
1641 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None";
|
|
|
1642 return $NeighborhoodsString;
|
|
|
1643 }
|
|
|
1644 $NeighborhoodsString = "<NeighborhoodRadius-NeighborhoodVertex-NeighborhoodVerticeSuccessorsList>: None";
|
|
|
1645
|
|
|
1646 $Radius = 0;
|
|
|
1647 for $NeighborhoodVertericesWithSuccessorsRef (@{$This->{VerticesNeighborhoodsWithSuccessors}}) {
|
|
|
1648 for $NeighborhoodVertexWithSuccessorsRef (@{$NeighborhoodVertericesWithSuccessorsRef}) {
|
|
|
1649 ($VertexID, $NeighborhoodVertexSuccessorsRef) = @{$NeighborhoodVertexWithSuccessorsRef};
|
|
|
1650 $NeighborhoodVertexSuccessorsString = 'None';
|
|
|
1651 if (@{$NeighborhoodVertexSuccessorsRef}) {
|
|
|
1652 $NeighborhoodVertexSuccessorsString = join(',', @{$NeighborhoodVertexSuccessorsRef});
|
|
|
1653 }
|
|
|
1654 $NeighborhoodsString .= " <$Radius-$VertexID-$NeighborhoodVertexSuccessorsString>";
|
|
|
1655 }
|
|
|
1656 $Radius++;
|
|
|
1657 }
|
|
|
1658 return $NeighborhoodsString;
|
|
|
1659 }
|
|
|
1660
|
|
|
1661 # Return a reference to new paths traversal object...
|
|
|
1662 sub Copy {
|
|
|
1663 my($This) = @_;
|
|
|
1664 my($NewPathsTraversal);
|
|
|
1665
|
|
|
1666 $NewPathsTraversal = Storable::dclone($This);
|
|
|
1667
|
|
|
1668 return $NewPathsTraversal;
|
|
|
1669 }
|
|
|
1670
|
|
|
1671 1;
|
|
|
1672
|
|
|
1673 __END__
|
|
|
1674
|
|
|
1675 =head1 NAME
|
|
|
1676
|
|
|
1677 PathsTraversal
|
|
|
1678
|
|
|
1679 =head1 SYNOPSIS
|
|
|
1680
|
|
|
1681 use Graph::PathsTraversal;
|
|
|
1682
|
|
|
1683 use Graph::PathsTraversal qw(:all);
|
|
|
1684
|
|
|
1685 =head1 DESCRIPTION
|
|
|
1686
|
|
|
1687 B<PathsTraversal> class provides the following methods:
|
|
|
1688
|
|
|
1689 new, Copy, GetConnectedComponentsVertices, GetPaths, GetVertices,
|
|
|
1690 GetVerticesDepth, GetVerticesNeighborhoods,
|
|
|
1691 GetVerticesNeighborhoodsWithSuccessors, GetVerticesPredecessors, GetVerticesRoots,
|
|
|
1692 PerformAllPathsSearch, PerformAllPathsSearchWithLength,
|
|
|
1693 PerformAllPathsSearchWithLengthUpto, PerformBreadthFirstSearch,
|
|
|
1694 PerformBreadthFirstSearchWithLimit, PerformDepthFirstSearch,
|
|
|
1695 PerformDepthFirstSearchWithLimit, PerformNeighborhoodVerticesSearch,
|
|
|
1696 PerformNeighborhoodVerticesSearchWithRadiusUpto,
|
|
|
1697 PerformNeighborhoodVerticesSearchWithSuccessors,
|
|
|
1698 PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto, PerformPathsSearch,
|
|
|
1699 PerformPathsSearchBetween, PerformPathsSearchWithLength,
|
|
|
1700 PerformPathsSearchWithLengthUpto, StringifyPaths, StringifyPathsTraversal,
|
|
|
1701 StringifyVerticesDepth, StringifyVerticesNeighborhoods,
|
|
|
1702 StringifyVerticesNeighborhoodsWithSuccessors, StringifyVerticesPredecessors,
|
|
|
1703 StringifyVerticesRoots, StringifyVerticesSuccessors
|
|
|
1704
|
|
|
1705 =head2 METHODS
|
|
|
1706
|
|
|
1707 =over 4
|
|
|
1708
|
|
|
1709 =item B<new>
|
|
|
1710
|
|
|
1711 $PathsTraversal = new Graph::PathsTraversal($Graph);
|
|
|
1712
|
|
|
1713 Using specified I<Graph>, B<new> method creates a new B<PathsTraversal> object and returns
|
|
|
1714 newly created B<PathsTraversal> object.
|
|
|
1715
|
|
|
1716 =item B<Copy>
|
|
|
1717
|
|
|
1718 $PathsTraversal = $PathsTraversal->Copy();
|
|
|
1719
|
|
|
1720 Copies I<PathsTraversal> and its associated data using B<Storable::dclone> and returns a new
|
|
|
1721 B<PathsTraversal> object.
|
|
|
1722
|
|
|
1723 =item B<GetConnectedComponentsVertices>
|
|
|
1724
|
|
|
1725 @Components = $PathsTraversal->GetConnectedComponentsVertices();
|
|
|
1726 $NumOfComponents = $PathsTraversal->GetConnectedComponentsVertices();
|
|
|
1727
|
|
|
1728 Returns an array of B<Components> containing references to arrays of vertex IDs corresponding
|
|
|
1729 to connected components of graph after a search. In scalar context, the number of connected
|
|
|
1730 components is returned.
|
|
|
1731
|
|
|
1732 Connected B<Components> is sorted in descending order of number of vertices in each
|
|
|
1733 connected component.
|
|
|
1734
|
|
|
1735 =item B<GetPaths>
|
|
|
1736
|
|
|
1737 @Paths = $PathsTraversal->GetPaths();
|
|
|
1738 $NumOfPaths = $PathsTraversal->GetPaths();
|
|
|
1739
|
|
|
1740 Returns an array of B<Paths> containing references to arrays of vertex IDs corresponding to
|
|
|
1741 to paths traversed in a graph after a search. In scalar context, number of paths is returned.
|
|
|
1742
|
|
|
1743 B<Paths> array is sorted in ascending order of path lengths.
|
|
|
1744
|
|
|
1745 =item B<GetVertices>
|
|
|
1746
|
|
|
1747 @Vertices = $PathsTraversal->GetVertices();
|
|
|
1748 $NumOfVertices = $PathsTraversal->GetVertices();
|
|
|
1749
|
|
|
1750 Returns an array containing an ordered list of vertex IDs traversed during a search. In
|
|
|
1751 scalar context, the number of vertices is returned.
|
|
|
1752
|
|
|
1753 =item B<GetVerticesDepth>
|
|
|
1754
|
|
|
1755 %VerticesDepth = $PathsTraversal->GetVerticesDepth();
|
|
|
1756
|
|
|
1757 Returns a hash I<VerticesDepth> containing vertex ID and depth from root vertex as a key and
|
|
|
1758 value pair for all vertices traversed during a search.
|
|
|
1759
|
|
|
1760 =item B<GetVerticesNeighborhoods>
|
|
|
1761
|
|
|
1762 @VerticesNeighborhoods =
|
|
|
1763 $PathsTraversal->GetVerticesNeighborhoods();
|
|
|
1764 $NumOfVerticesNeighborhoods =
|
|
|
1765 $PathsTraversal->GetVerticesNeighborhoods();
|
|
|
1766
|
|
|
1767 Returns an array I<VerticesNeighborhoods> containing references to arrays corresponding
|
|
|
1768 to vertices collected at various neighborhood radii around a specified vertex during a vertex
|
|
|
1769 neighborhood search. In scalar context, the number of neighborhoods is returned.
|
|
|
1770
|
|
|
1771 =item B<GetVerticesNeighborhoodsWithSuccessors>
|
|
|
1772
|
|
|
1773 @VerticesNeighborhoodsWithSucceessors =
|
|
|
1774 $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
|
|
|
1775 $NumOfVerticesNeighborhoodsWithSucceessors =
|
|
|
1776 $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
|
|
|
1777
|
|
|
1778 Returns an array I<VerticesNeighborhoodsWithSucceessors> containing references to arrays
|
|
|
1779 with first value corresponding to vertex IDs corresponding to a vertex at a specific neighborhood
|
|
|
1780 radius level and second value a reference to an arraty containing its successors.
|
|
|
1781
|
|
|
1782 =item B<GetVerticesPredecessors>
|
|
|
1783
|
|
|
1784 %VerticesPredecessors = $PathsTraversal->GetVerticesPredecessors();
|
|
|
1785
|
|
|
1786 Returns a hash I<VerticesPredecessors> containing vertex ID and predecessor vertex ID as key
|
|
|
1787 and value pair for all vertices traversed during a search.
|
|
|
1788
|
|
|
1789 =item B<GetVerticesRoots>
|
|
|
1790
|
|
|
1791 %VerticesRoots = $PathsTraversal->GetVerticesRoots();
|
|
|
1792
|
|
|
1793 Returns a hash I<VerticesPredecessors> containing vertex ID and root vertex ID as a key
|
|
|
1794 and value pair for all vertices traversed during a search.
|
|
|
1795
|
|
|
1796 =item B<PerformAllPathsSearch>
|
|
|
1797
|
|
|
1798 $PathsTraversal->PerformAllPathsSearch($StartVertexID, [$AllowCycles]);
|
|
|
1799
|
|
|
1800 Searches all paths starting from a I<StartVertexID> with sharing of edges in paths traversed and
|
|
|
1801 returns I<PathsTraversal>.
|
|
|
1802
|
|
|
1803 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
1804 completing the cycle.
|
|
|
1805
|
|
|
1806 =item B<PerformAllPathsSearchWithLength>
|
|
|
1807
|
|
|
1808 $PathsTraversal->PerformAllPathsSearchWithLength($StartVertexID,
|
|
|
1809 $Length, [$AllowCycles]);
|
|
|
1810
|
|
|
1811 Searches all paths starting from I<StartVertexID> of specific I<Length> with sharing of
|
|
|
1812 edges in paths traversed and returns I<PathsTraversal>.
|
|
|
1813
|
|
|
1814 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
1815 completing the cycle.
|
|
|
1816
|
|
|
1817 =item B<PerformAllPathsSearchWithLengthUpto>
|
|
|
1818
|
|
|
1819 $PathsTraversal->PerformAllPathsSearchWithLengthUpto($StartVertexID,
|
|
|
1820 $Length, [$AllowCycles]);
|
|
|
1821
|
|
|
1822 Searches all paths starting from I<StartVertexID> of length upto a I<Length> with sharing of
|
|
|
1823 edges in paths traversed and returns I<PathsTraversal>.
|
|
|
1824
|
|
|
1825 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
1826 completing the cycle.
|
|
|
1827
|
|
|
1828 =item B<PerformBreadthFirstSearch>
|
|
|
1829
|
|
|
1830 $PathsTraversal->PerformBreadthFirstSearch();
|
|
|
1831
|
|
|
1832 Performs Breadth First Search (BFS) and returns I<PathsTraversal>.
|
|
|
1833
|
|
|
1834 =item B<PerformBreadthFirstSearchWithLimit>
|
|
|
1835
|
|
|
1836 $PathsTraversal->PerformBreadthFirstSearchWithLimit($DepthLimit,
|
|
|
1837 [$RootVertexID]);
|
|
|
1838
|
|
|
1839 Performs BFS with depth up to I<DepthLimit> starting at I<RootVertexID> and returns
|
|
|
1840 I<PathsTraversal>. By default, root vertex ID corresponds to an arbitrary vertex.
|
|
|
1841
|
|
|
1842 =item B<PerformDepthFirstSearch>
|
|
|
1843
|
|
|
1844 $Return = $PathsTraversal->PerformDepthFirstSearch();
|
|
|
1845
|
|
|
1846 Performs Depth First Search (DFS) and returns I<PathsTraversal>.
|
|
|
1847
|
|
|
1848 =item B<PerformDepthFirstSearchWithLimit>
|
|
|
1849
|
|
|
1850 $PathsTraversal->PerformDepthFirstSearchWithLimit($DepthLimit,
|
|
|
1851 [$RootVertexID]);
|
|
|
1852
|
|
|
1853 Performs DFS with depth up to I<DepthLimit> starting at I<RootVertexID> and returns
|
|
|
1854 I<PathsTraversal>. By default, root vertex ID corresponds to an arbitrary vertex.
|
|
|
1855
|
|
|
1856 =item B<PerformNeighborhoodVerticesSearch>
|
|
|
1857
|
|
|
1858 $PathsTraversal->PerformNeighborhoodVerticesSearch($StartVertexID);
|
|
|
1859
|
|
|
1860 Searches vertices around I<StartVertexID> at all neighborhood radii and returns
|
|
|
1861 I<PathsTraversal> object.
|
|
|
1862
|
|
|
1863 =item B<PerformNeighborhoodVerticesSearchWithRadiusUpto>
|
|
|
1864
|
|
|
1865 $PathsTraversal->PerformNeighborhoodVerticesSearchWithRadiusUpto(
|
|
|
1866 $StartVertexID, $Radius);
|
|
|
1867
|
|
|
1868 Searches vertices around I<StartVertexID> with neighborhood radius up to I<Radius> and returns
|
|
|
1869 I<PathsTraversal> object.
|
|
|
1870
|
|
|
1871 =item B<PerformNeighborhoodVerticesSearchWithSuccessors>
|
|
|
1872
|
|
|
1873 $PathsTraversal->PerformNeighborhoodVerticesSearchWithSuccessors(
|
|
|
1874 $StartVertexID);
|
|
|
1875
|
|
|
1876 Searches vertices around I<StartVertexID> at all neighborhood radii along with identification of
|
|
|
1877 successor vertices for each vertex found during the traversal and returns I<PathsTraversal>.
|
|
|
1878
|
|
|
1879 =item B<PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto>
|
|
|
1880
|
|
|
1881 $PathsTraversal->
|
|
|
1882 PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto(
|
|
|
1883 $StartVertexID, $Radius);
|
|
|
1884
|
|
|
1885 Searches vertices around I<StartVertexID> with neighborhood radius upto I<Radius> along with
|
|
|
1886 identification of successor vertices for each vertex found during the traversal and returns
|
|
|
1887 I<PathsTraversal>.
|
|
|
1888
|
|
|
1889 =item B<PerformPathsSearch>
|
|
|
1890
|
|
|
1891 $PathsTraversal->PerformPathsSearch($StartVertexID, [$AllowCycles]);
|
|
|
1892
|
|
|
1893 Searches paths starting from I<StartVertexID> with no sharing of edges in paths traversed and
|
|
|
1894 returns I<PathsTraversal>.
|
|
|
1895
|
|
|
1896 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
1897 completing the cycle.
|
|
|
1898
|
|
|
1899 =item B<PerformPathsSearchBetween>
|
|
|
1900
|
|
|
1901 $PathsTraversal->PerformPathsSearchBetween($StartVertexID, $EndVertexID);
|
|
|
1902
|
|
|
1903 Searches paths between I<StartVertexID> and I<EndVertexID> and returns I<PathsTraversal>
|
|
|
1904
|
|
|
1905 =item B<PerformPathsSearchWithLength>
|
|
|
1906
|
|
|
1907 $PathsTraversal->PerformPathsSearchWithLength($StartVertexID, $Length,
|
|
|
1908 [$AllowCycles]);
|
|
|
1909
|
|
|
1910 Searches paths starting from I<StartVertexID> with length I<Length> with no sharing of
|
|
|
1911 edges in paths traversed and returns I<PathsTraversal>.
|
|
|
1912
|
|
|
1913 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
1914 completing the cycle.
|
|
|
1915
|
|
|
1916 =item B<PerformPathsSearchWithLengthUpto>
|
|
|
1917
|
|
|
1918 $PathsTraversal->PerformPathsSearchWithLengthUpto($StartVertexID, $Length,
|
|
|
1919 [$AllowCycles]);
|
|
|
1920
|
|
|
1921 Searches paths starting from I<StartVertexID> with length upto I<Length> with no sharing of
|
|
|
1922 edges in paths traversed and returns I<PathsTraversal>.
|
|
|
1923
|
|
|
1924 By default, cycles are included in paths. A path containing a cycle is terminated at a vertex
|
|
|
1925 completing the cycle.
|
|
|
1926
|
|
|
1927 =item B<StringifyPaths>
|
|
|
1928
|
|
|
1929 $String = $PathsTraversal->StringifyPaths();
|
|
|
1930
|
|
|
1931 Returns a string containing information about traversed paths in I<PathsTraversal> object
|
|
|
1932
|
|
|
1933 =item B<StringifyPathsTraversal>
|
|
|
1934
|
|
|
1935 $String = $PathsTraversal->StringifyPathsTraversal();
|
|
|
1936
|
|
|
1937 Returns a string containing information about I<PathsTraversal> object.
|
|
|
1938
|
|
|
1939 =item B<StringifyVerticesDepth>
|
|
|
1940
|
|
|
1941 $String = $PathsTraversal->StringifyVerticesDepth();
|
|
|
1942
|
|
|
1943 Returns a string containing information about depth of vertices found during search by
|
|
|
1944 I<PathsTraversal> object.
|
|
|
1945
|
|
|
1946 =item B<StringifyVerticesNeighborhoods>
|
|
|
1947
|
|
|
1948 $String = $PathsTraversal->StringifyVerticesNeighborhoods();
|
|
|
1949
|
|
|
1950 Returns a string containing information about neighborhoods of vertices found during search by
|
|
|
1951 I<PathsTraversal> object.
|
|
|
1952
|
|
|
1953 =item B<StringifyVerticesNeighborhoodsWithSuccessors>
|
|
|
1954
|
|
|
1955 $String = $PathsTraversal->StringifyVerticesNeighborhoodsWithSuccessors();
|
|
|
1956
|
|
|
1957 Returns a string containing information about neighborhoods of vertices along with their successors
|
|
|
1958 found during search by I<PathsTraversal> object.
|
|
|
1959
|
|
|
1960 =item B<StringifyVerticesPredecessors>
|
|
|
1961
|
|
|
1962 $String = $PathsTraversal->StringifyVerticesPredecessors();
|
|
|
1963
|
|
|
1964 Returns a string containing information about predecessors of vertices found during search by
|
|
|
1965 I<PathsTraversal> object.
|
|
|
1966
|
|
|
1967 =item B<StringifyVerticesRoots>
|
|
|
1968
|
|
|
1969 $String = $PathsTraversal->StringifyVerticesRoots();
|
|
|
1970
|
|
|
1971 Returns a string containing information about roots of vertices found during search by
|
|
|
1972 I<PathsTraversal> object.
|
|
|
1973
|
|
|
1974 =item B<StringifyVerticesSuccessors>
|
|
|
1975
|
|
|
1976 $String = $PathsTraversal->StringifyVerticesSuccessors();
|
|
|
1977
|
|
|
1978 Returns a string containing information about successors of vertices found during search by
|
|
|
1979 I<PathsTraversal> object.
|
|
|
1980
|
|
|
1981 =back
|
|
|
1982
|
|
|
1983 =head1 AUTHOR
|
|
|
1984
|
|
|
1985 Manish Sud <msud@san.rr.com>
|
|
|
1986
|
|
|
1987 =head1 SEE ALSO
|
|
|
1988
|
|
|
1989 Graph.pm, Path.pm
|
|
|
1990
|
|
|
1991 =head1 COPYRIGHT
|
|
|
1992
|
|
|
1993 Copyright (C) 2015 Manish Sud. All rights reserved.
|
|
|
1994
|
|
|
1995 This file is part of MayaChemTools.
|
|
|
1996
|
|
|
1997 MayaChemTools is free software; you can redistribute it and/or modify it under
|
|
|
1998 the terms of the GNU Lesser General Public License as published by the Free
|
|
|
1999 Software Foundation; either version 3 of the License, or (at your option)
|
|
|
2000 any later version.
|
|
|
2001
|
|
|
2002 =cut
|
