|
1
|
1 NAME
|
|
|
2 PathsTraversal
|
|
|
3
|
|
|
4 SYNOPSIS
|
|
|
5 use Graph::PathsTraversal;
|
|
|
6
|
|
|
7 use Graph::PathsTraversal qw(:all);
|
|
|
8
|
|
|
9 DESCRIPTION
|
|
|
10 PathsTraversal class provides the following methods:
|
|
|
11
|
|
|
12 new, Copy, GetConnectedComponentsVertices, GetPaths, GetVertices,
|
|
|
13 GetVerticesDepth, GetVerticesNeighborhoods,
|
|
|
14 GetVerticesNeighborhoodsWithSuccessors, GetVerticesPredecessors,
|
|
|
15 GetVerticesRoots, PerformAllPathsSearch,
|
|
|
16 PerformAllPathsSearchWithLength, PerformAllPathsSearchWithLengthUpto,
|
|
|
17 PerformBreadthFirstSearch, PerformBreadthFirstSearchWithLimit,
|
|
|
18 PerformDepthFirstSearch, PerformDepthFirstSearchWithLimit,
|
|
|
19 PerformNeighborhoodVerticesSearch,
|
|
|
20 PerformNeighborhoodVerticesSearchWithRadiusUpto,
|
|
|
21 PerformNeighborhoodVerticesSearchWithSuccessors,
|
|
|
22 PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto,
|
|
|
23 PerformPathsSearch, PerformPathsSearchBetween,
|
|
|
24 PerformPathsSearchWithLength, PerformPathsSearchWithLengthUpto,
|
|
|
25 StringifyPaths, StringifyPathsTraversal, StringifyVerticesDepth,
|
|
|
26 StringifyVerticesNeighborhoods,
|
|
|
27 StringifyVerticesNeighborhoodsWithSuccessors,
|
|
|
28 StringifyVerticesPredecessors, StringifyVerticesRoots,
|
|
|
29 StringifyVerticesSuccessors
|
|
|
30
|
|
|
31 METHODS
|
|
|
32 new
|
|
|
33 $PathsTraversal = new Graph::PathsTraversal($Graph);
|
|
|
34
|
|
|
35 Using specified *Graph*, new method creates a new PathsTraversal
|
|
|
36 object and returns newly created PathsTraversal object.
|
|
|
37
|
|
|
38 Copy
|
|
|
39 $PathsTraversal = $PathsTraversal->Copy();
|
|
|
40
|
|
|
41 Copies *PathsTraversal* and its associated data using
|
|
|
42 Storable::dclone and returns a new PathsTraversal object.
|
|
|
43
|
|
|
44 GetConnectedComponentsVertices
|
|
|
45 @Components = $PathsTraversal->GetConnectedComponentsVertices();
|
|
|
46 $NumOfComponents = $PathsTraversal->GetConnectedComponentsVertices();
|
|
|
47
|
|
|
48 Returns an array of Components containing references to arrays of
|
|
|
49 vertex IDs corresponding to connected components of graph after a
|
|
|
50 search. In scalar context, the number of connected components is
|
|
|
51 returned.
|
|
|
52
|
|
|
53 Connected Components is sorted in descending order of number of
|
|
|
54 vertices in each connected component.
|
|
|
55
|
|
|
56 GetPaths
|
|
|
57 @Paths = $PathsTraversal->GetPaths();
|
|
|
58 $NumOfPaths = $PathsTraversal->GetPaths();
|
|
|
59
|
|
|
60 Returns an array of Paths containing references to arrays of vertex
|
|
|
61 IDs corresponding to to paths traversed in a graph after a search.
|
|
|
62 In scalar context, number of paths is returned.
|
|
|
63
|
|
|
64 Paths array is sorted in ascending order of path lengths.
|
|
|
65
|
|
|
66 GetVertices
|
|
|
67 @Vertices = $PathsTraversal->GetVertices();
|
|
|
68 $NumOfVertices = $PathsTraversal->GetVertices();
|
|
|
69
|
|
|
70 Returns an array containing an ordered list of vertex IDs traversed
|
|
|
71 during a search. In scalar context, the number of vertices is
|
|
|
72 returned.
|
|
|
73
|
|
|
74 GetVerticesDepth
|
|
|
75 %VerticesDepth = $PathsTraversal->GetVerticesDepth();
|
|
|
76
|
|
|
77 Returns a hash *VerticesDepth* containing vertex ID and depth from
|
|
|
78 root vertex as a key and value pair for all vertices traversed
|
|
|
79 during a search.
|
|
|
80
|
|
|
81 GetVerticesNeighborhoods
|
|
|
82 @VerticesNeighborhoods =
|
|
|
83 $PathsTraversal->GetVerticesNeighborhoods();
|
|
|
84 $NumOfVerticesNeighborhoods =
|
|
|
85 $PathsTraversal->GetVerticesNeighborhoods();
|
|
|
86
|
|
|
87 Returns an array *VerticesNeighborhoods* containing references to
|
|
|
88 arrays corresponding to vertices collected at various neighborhood
|
|
|
89 radii around a specified vertex during a vertex neighborhood search.
|
|
|
90 In scalar context, the number of neighborhoods is returned.
|
|
|
91
|
|
|
92 GetVerticesNeighborhoodsWithSuccessors
|
|
|
93 @VerticesNeighborhoodsWithSucceessors =
|
|
|
94 $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
|
|
|
95 $NumOfVerticesNeighborhoodsWithSucceessors =
|
|
|
96 $PathsTraversal->GetVerticesNeighborhoodsWithSuccessors();
|
|
|
97
|
|
|
98 Returns an array *VerticesNeighborhoodsWithSucceessors* containing
|
|
|
99 references to arrays with first value corresponding to vertex IDs
|
|
|
100 corresponding to a vertex at a specific neighborhood radius level
|
|
|
101 and second value a reference to an arraty containing its successors.
|
|
|
102
|
|
|
103 GetVerticesPredecessors
|
|
|
104 %VerticesPredecessors = $PathsTraversal->GetVerticesPredecessors();
|
|
|
105
|
|
|
106 Returns a hash *VerticesPredecessors* containing vertex ID and
|
|
|
107 predecessor vertex ID as key and value pair for all vertices
|
|
|
108 traversed during a search.
|
|
|
109
|
|
|
110 GetVerticesRoots
|
|
|
111 %VerticesRoots = $PathsTraversal->GetVerticesRoots();
|
|
|
112
|
|
|
113 Returns a hash *VerticesPredecessors* containing vertex ID and root
|
|
|
114 vertex ID as a key and value pair for all vertices traversed during
|
|
|
115 a search.
|
|
|
116
|
|
|
117 PerformAllPathsSearch
|
|
|
118 $PathsTraversal->PerformAllPathsSearch($StartVertexID, [$AllowCycles]);
|
|
|
119
|
|
|
120 Searches all paths starting from a *StartVertexID* with sharing of
|
|
|
121 edges in paths traversed and returns *PathsTraversal*.
|
|
|
122
|
|
|
123 By default, cycles are included in paths. A path containing a cycle
|
|
|
124 is terminated at a vertex completing the cycle.
|
|
|
125
|
|
|
126 PerformAllPathsSearchWithLength
|
|
|
127 $PathsTraversal->PerformAllPathsSearchWithLength($StartVertexID,
|
|
|
128 $Length, [$AllowCycles]);
|
|
|
129
|
|
|
130 Searches all paths starting from *StartVertexID* of specific
|
|
|
131 *Length* with sharing of edges in paths traversed and returns
|
|
|
132 *PathsTraversal*.
|
|
|
133
|
|
|
134 By default, cycles are included in paths. A path containing a cycle
|
|
|
135 is terminated at a vertex completing the cycle.
|
|
|
136
|
|
|
137 PerformAllPathsSearchWithLengthUpto
|
|
|
138 $PathsTraversal->PerformAllPathsSearchWithLengthUpto($StartVertexID,
|
|
|
139 $Length, [$AllowCycles]);
|
|
|
140
|
|
|
141 Searches all paths starting from *StartVertexID* of length upto a
|
|
|
142 *Length* with sharing of edges in paths traversed and returns
|
|
|
143 *PathsTraversal*.
|
|
|
144
|
|
|
145 By default, cycles are included in paths. A path containing a cycle
|
|
|
146 is terminated at a vertex completing the cycle.
|
|
|
147
|
|
|
148 PerformBreadthFirstSearch
|
|
|
149 $PathsTraversal->PerformBreadthFirstSearch();
|
|
|
150
|
|
|
151 Performs Breadth First Search (BFS) and returns *PathsTraversal*.
|
|
|
152
|
|
|
153 PerformBreadthFirstSearchWithLimit
|
|
|
154 $PathsTraversal->PerformBreadthFirstSearchWithLimit($DepthLimit,
|
|
|
155 [$RootVertexID]);
|
|
|
156
|
|
|
157 Performs BFS with depth up to *DepthLimit* starting at
|
|
|
158 *RootVertexID* and returns *PathsTraversal*. By default, root vertex
|
|
|
159 ID corresponds to an arbitrary vertex.
|
|
|
160
|
|
|
161 PerformDepthFirstSearch
|
|
|
162 $Return = $PathsTraversal->PerformDepthFirstSearch();
|
|
|
163
|
|
|
164 Performs Depth First Search (DFS) and returns *PathsTraversal*.
|
|
|
165
|
|
|
166 PerformDepthFirstSearchWithLimit
|
|
|
167 $PathsTraversal->PerformDepthFirstSearchWithLimit($DepthLimit,
|
|
|
168 [$RootVertexID]);
|
|
|
169
|
|
|
170 Performs DFS with depth up to *DepthLimit* starting at
|
|
|
171 *RootVertexID* and returns *PathsTraversal*. By default, root vertex
|
|
|
172 ID corresponds to an arbitrary vertex.
|
|
|
173
|
|
|
174 PerformNeighborhoodVerticesSearch
|
|
|
175 $PathsTraversal->PerformNeighborhoodVerticesSearch($StartVertexID);
|
|
|
176
|
|
|
177 Searches vertices around *StartVertexID* at all neighborhood radii
|
|
|
178 and returns *PathsTraversal* object.
|
|
|
179
|
|
|
180 PerformNeighborhoodVerticesSearchWithRadiusUpto
|
|
|
181 $PathsTraversal->PerformNeighborhoodVerticesSearchWithRadiusUpto(
|
|
|
182 $StartVertexID, $Radius);
|
|
|
183
|
|
|
184 Searches vertices around *StartVertexID* with neighborhood radius up
|
|
|
185 to *Radius* and returns *PathsTraversal* object.
|
|
|
186
|
|
|
187 PerformNeighborhoodVerticesSearchWithSuccessors
|
|
|
188 $PathsTraversal->PerformNeighborhoodVerticesSearchWithSuccessors(
|
|
|
189 $StartVertexID);
|
|
|
190
|
|
|
191 Searches vertices around *StartVertexID* at all neighborhood radii
|
|
|
192 along with identification of successor vertices for each vertex
|
|
|
193 found during the traversal and returns *PathsTraversal*.
|
|
|
194
|
|
|
195 PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto
|
|
|
196 $PathsTraversal->
|
|
|
197 PerformNeighborhoodVerticesSearchWithSuccessorsAndRadiusUpto(
|
|
|
198 $StartVertexID, $Radius);
|
|
|
199
|
|
|
200 Searches vertices around *StartVertexID* with neighborhood radius
|
|
|
201 upto *Radius* along with identification of successor vertices for
|
|
|
202 each vertex found during the traversal and returns *PathsTraversal*.
|
|
|
203
|
|
|
204 PerformPathsSearch
|
|
|
205 $PathsTraversal->PerformPathsSearch($StartVertexID, [$AllowCycles]);
|
|
|
206
|
|
|
207 Searches paths starting from *StartVertexID* with no sharing of
|
|
|
208 edges in paths traversed and returns *PathsTraversal*.
|
|
|
209
|
|
|
210 By default, cycles are included in paths. A path containing a cycle
|
|
|
211 is terminated at a vertex completing the cycle.
|
|
|
212
|
|
|
213 PerformPathsSearchBetween
|
|
|
214 $PathsTraversal->PerformPathsSearchBetween($StartVertexID, $EndVertexID);
|
|
|
215
|
|
|
216 Searches paths between *StartVertexID* and *EndVertexID* and returns
|
|
|
217 *PathsTraversal*
|
|
|
218
|
|
|
219 PerformPathsSearchWithLength
|
|
|
220 $PathsTraversal->PerformPathsSearchWithLength($StartVertexID, $Length,
|
|
|
221 [$AllowCycles]);
|
|
|
222
|
|
|
223 Searches paths starting from *StartVertexID* with length *Length*
|
|
|
224 with no sharing of edges in paths traversed and returns
|
|
|
225 *PathsTraversal*.
|
|
|
226
|
|
|
227 By default, cycles are included in paths. A path containing a cycle
|
|
|
228 is terminated at a vertex completing the cycle.
|
|
|
229
|
|
|
230 PerformPathsSearchWithLengthUpto
|
|
|
231 $PathsTraversal->PerformPathsSearchWithLengthUpto($StartVertexID, $Length,
|
|
|
232 [$AllowCycles]);
|
|
|
233
|
|
|
234 Searches paths starting from *StartVertexID* with length upto
|
|
|
235 *Length* with no sharing of edges in paths traversed and returns
|
|
|
236 *PathsTraversal*.
|
|
|
237
|
|
|
238 By default, cycles are included in paths. A path containing a cycle
|
|
|
239 is terminated at a vertex completing the cycle.
|
|
|
240
|
|
|
241 StringifyPaths
|
|
|
242 $String = $PathsTraversal->StringifyPaths();
|
|
|
243
|
|
|
244 Returns a string containing information about traversed paths in
|
|
|
245 *PathsTraversal* object
|
|
|
246
|
|
|
247 StringifyPathsTraversal
|
|
|
248 $String = $PathsTraversal->StringifyPathsTraversal();
|
|
|
249
|
|
|
250 Returns a string containing information about *PathsTraversal*
|
|
|
251 object.
|
|
|
252
|
|
|
253 StringifyVerticesDepth
|
|
|
254 $String = $PathsTraversal->StringifyVerticesDepth();
|
|
|
255
|
|
|
256 Returns a string containing information about depth of vertices
|
|
|
257 found during search by *PathsTraversal* object.
|
|
|
258
|
|
|
259 StringifyVerticesNeighborhoods
|
|
|
260 $String = $PathsTraversal->StringifyVerticesNeighborhoods();
|
|
|
261
|
|
|
262 Returns a string containing information about neighborhoods of
|
|
|
263 vertices found during search by *PathsTraversal* object.
|
|
|
264
|
|
|
265 StringifyVerticesNeighborhoodsWithSuccessors
|
|
|
266 $String = $PathsTraversal->StringifyVerticesNeighborhoodsWithSuccessors();
|
|
|
267
|
|
|
268 Returns a string containing information about neighborhoods of
|
|
|
269 vertices along with their successors found during search by
|
|
|
270 *PathsTraversal* object.
|
|
|
271
|
|
|
272 StringifyVerticesPredecessors
|
|
|
273 $String = $PathsTraversal->StringifyVerticesPredecessors();
|
|
|
274
|
|
|
275 Returns a string containing information about predecessors of
|
|
|
276 vertices found during search by *PathsTraversal* object.
|
|
|
277
|
|
|
278 StringifyVerticesRoots
|
|
|
279 $String = $PathsTraversal->StringifyVerticesRoots();
|
|
|
280
|
|
|
281 Returns a string containing information about roots of vertices
|
|
|
282 found during search by *PathsTraversal* object.
|
|
|
283
|
|
|
284 StringifyVerticesSuccessors
|
|
|
285 $String = $PathsTraversal->StringifyVerticesSuccessors();
|
|
|
286
|
|
|
287 Returns a string containing information about successors of vertices
|
|
|
288 found during search by *PathsTraversal* object.
|
|
|
289
|
|
|
290 AUTHOR
|
|
|
291 Manish Sud <msud@san.rr.com>
|
|
|
292
|
|
|
293 SEE ALSO
|
|
|
294 Graph.pm, Path.pm
|
|
|
295
|
|
|
296 COPYRIGHT
|
|
|
297 Copyright (C) 2015 Manish Sud. All rights reserved.
|
|
|
298
|
|
|
299 This file is part of MayaChemTools.
|
|
|
300
|
|
|
301 MayaChemTools is free software; you can redistribute it and/or modify it
|
|
|
302 under the terms of the GNU Lesser General Public License as published by
|
|
|
303 the Free Software Foundation; either version 3 of the License, or (at
|
|
|
304 your option) any later version.
|
|
|
305
|
