Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | .\" Automatically generated by Pod::Man v1.34, Pod::Parser v1.13 |
2 | .\" | |
3 | .\" Standard preamble: | |
4 | .\" ======================================================================== | |
5 | .de Sh \" Subsection heading | |
6 | .br | |
7 | .if t .Sp | |
8 | .ne 5 | |
9 | .PP | |
10 | \fB\\$1\fR | |
11 | .PP | |
12 | .. | |
13 | .de Sp \" Vertical space (when we can't use .PP) | |
14 | .if t .sp .5v | |
15 | .if n .sp | |
16 | .. | |
17 | .de Vb \" Begin verbatim text | |
18 | .ft CW | |
19 | .nf | |
20 | .ne \\$1 | |
21 | .. | |
22 | .de Ve \" End verbatim text | |
23 | .ft R | |
24 | .fi | |
25 | .. | |
26 | .\" Set up some character translations and predefined strings. \*(-- will | |
27 | .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left | |
28 | .\" double quote, and \*(R" will give a right double quote. | will give a | |
29 | .\" real vertical bar. \*(C+ will give a nicer C++. Capital omega is used to | |
30 | .\" do unbreakable dashes and therefore won't be available. \*(C` and \*(C' | |
31 | .\" expand to `' in nroff, nothing in troff, for use with C<>. | |
32 | .tr \(*W-|\(bv\*(Tr | |
33 | .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' | |
34 | .ie n \{\ | |
35 | . ds -- \(*W- | |
36 | . ds PI pi | |
37 | . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch | |
38 | . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch | |
39 | . ds L" "" | |
40 | . ds R" "" | |
41 | . ds C` "" | |
42 | . ds C' "" | |
43 | 'br\} | |
44 | .el\{\ | |
45 | . ds -- \|\(em\| | |
46 | . ds PI \(*p | |
47 | . ds L" `` | |
48 | . ds R" '' | |
49 | 'br\} | |
50 | .\" | |
51 | .\" If the F register is turned on, we'll generate index entries on stderr for | |
52 | .\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index | |
53 | .\" entries marked with X<> in POD. Of course, you'll have to process the | |
54 | .\" output yourself in some meaningful fashion. | |
55 | .if \nF \{\ | |
56 | . de IX | |
57 | . tm Index:\\$1\t\\n%\t"\\$2" | |
58 | .. | |
59 | . nr % 0 | |
60 | . rr F | |
61 | .\} | |
62 | .\" | |
63 | .\" For nroff, turn off justification. Always turn off hyphenation; it makes | |
64 | .\" way too many mistakes in technical documents. | |
65 | .hy 0 | |
66 | .if n .na | |
67 | .\" | |
68 | .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). | |
69 | .\" Fear. Run. Save yourself. No user-serviceable parts. | |
70 | . \" fudge factors for nroff and troff | |
71 | .if n \{\ | |
72 | . ds #H 0 | |
73 | . ds #V .8m | |
74 | . ds #F .3m | |
75 | . ds #[ \f1 | |
76 | . ds #] \fP | |
77 | .\} | |
78 | .if t \{\ | |
79 | . ds #H ((1u-(\\\\n(.fu%2u))*.13m) | |
80 | . ds #V .6m | |
81 | . ds #F 0 | |
82 | . ds #[ \& | |
83 | . ds #] \& | |
84 | .\} | |
85 | . \" simple accents for nroff and troff | |
86 | .if n \{\ | |
87 | . ds ' \& | |
88 | . ds ` \& | |
89 | . ds ^ \& | |
90 | . ds , \& | |
91 | . ds ~ ~ | |
92 | . ds / | |
93 | .\} | |
94 | .if t \{\ | |
95 | . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" | |
96 | . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' | |
97 | . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' | |
98 | . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' | |
99 | . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' | |
100 | . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' | |
101 | .\} | |
102 | . \" troff and (daisy-wheel) nroff accents | |
103 | .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' | |
104 | .ds 8 \h'\*(#H'\(*b\h'-\*(#H' | |
105 | .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] | |
106 | .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' | |
107 | .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' | |
108 | .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] | |
109 | .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] | |
110 | .ds ae a\h'-(\w'a'u*4/10)'e | |
111 | .ds Ae A\h'-(\w'A'u*4/10)'E | |
112 | . \" corrections for vroff | |
113 | .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' | |
114 | .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' | |
115 | . \" for low resolution devices (crt and lpr) | |
116 | .if \n(.H>23 .if \n(.V>19 \ | |
117 | \{\ | |
118 | . ds : e | |
119 | . ds 8 ss | |
120 | . ds o a | |
121 | . ds d- d\h'-1'\(ga | |
122 | . ds D- D\h'-1'\(hy | |
123 | . ds th \o'bp' | |
124 | . ds Th \o'LP' | |
125 | . ds ae ae | |
126 | . ds Ae AE | |
127 | .\} | |
128 | .rm #[ #] #H #V #F C | |
129 | .\" ======================================================================== | |
130 | .\" | |
131 | .IX Title "Graph::Base 3" | |
132 | .TH Graph::Base 3 "2004-04-04" "perl v5.8.0" "User Contributed Perl Documentation" | |
133 | .SH "NAME" | |
134 | Graph::Base \- graph base class | |
135 | .SH "SYNOPSIS" | |
136 | .IX Header "SYNOPSIS" | |
137 | .Vb 2 | |
138 | \& use Graph::Directed; | |
139 | \& use Graph::Undirected; | |
140 | .Ve | |
141 | .PP | |
142 | .Vb 3 | |
143 | \& $d1 = new Graph; | |
144 | \& $d2 = new Graph::Directed; | |
145 | \& $u = new Graph::Undirected; | |
146 | .Ve | |
147 | .SH "DESCRIPTION" | |
148 | .IX Header "DESCRIPTION" | |
149 | You create new graphs by calling the \f(CW\*(C`new\*(C'\fR constructors of classes | |
150 | \&\f(CW\*(C`Graph\*(C'\fR, \f(CW\*(C`Graph::Directed\*(C'\fR, and \f(CW\*(C`Graph::Undirected\*(C'\fR. The classes | |
151 | \&\f(CW\*(C`Graph\*(C'\fR and \f(CW\*(C`Graph::Directed\*(C'\fR are identical. After creating the | |
152 | graph you can modify and explore the graph with following methods. | |
153 | .IP "new" 4 | |
154 | .IX Item "new" | |
155 | .Vb 1 | |
156 | \& $G = Graph->new(@V) | |
157 | .Ve | |
158 | .Sp | |
159 | Returns a new graph \f(CW$G\fR with the optional vertices \f(CW@V\fR. | |
160 | .IP "add_vertices" 4 | |
161 | .IX Item "add_vertices" | |
162 | .Vb 1 | |
163 | \& $G = $G->add_vertices(@v) | |
164 | .Ve | |
165 | .Sp | |
166 | Adds the vertices to the graph \f(CW$G\fR, returns the graph. | |
167 | .IP "add_vertex" 4 | |
168 | .IX Item "add_vertex" | |
169 | .Vb 1 | |
170 | \& $G = $G->add_vertex($v) | |
171 | .Ve | |
172 | .Sp | |
173 | Adds the vertex \f(CW$v\fR to the graph \f(CW$G\fR, returns the graph. | |
174 | .IP "vertices" 4 | |
175 | .IX Item "vertices" | |
176 | .Vb 1 | |
177 | \& @V = $G->vertices | |
178 | .Ve | |
179 | .Sp | |
180 | In list context returns the vertices \f(CW@V\fR of the graph \f(CW$G\fR. | |
181 | In scalar context returns the number of the vertices. | |
182 | .IP "has_vertices" 4 | |
183 | .IX Item "has_vertices" | |
184 | .Vb 1 | |
185 | \& $G->has_vertices(@v) | |
186 | .Ve | |
187 | .Sp | |
188 | In list context returns a list which contains the vertex | |
189 | of the vertices \f(CW@v\fR if the vertex exists in the graph \f(CW$G\fR | |
190 | and undef if it doesn't. In scalar context returns the | |
191 | number of the existing vertices. | |
192 | .IP "has_vertex" 4 | |
193 | .IX Item "has_vertex" | |
194 | .Vb 1 | |
195 | \& $b = $G->has_vertex($v) | |
196 | .Ve | |
197 | .Sp | |
198 | Returns true if the vertex \f(CW$v\fR exists in | |
199 | the graph \f(CW$G\fR and false if it doesn't. | |
200 | .IP "vertex" 4 | |
201 | .IX Item "vertex" | |
202 | .Vb 1 | |
203 | \& $v = $G->has_vertex($v) | |
204 | .Ve | |
205 | .Sp | |
206 | Returns the vertex \f(CW$v\fR if the vertex exists in the graph \f(CW$G\fR | |
207 | or undef if it doesn't. | |
208 | .IP "directed" 4 | |
209 | .IX Item "directed" | |
210 | .Vb 1 | |
211 | \& $b = $G->directed($d) | |
212 | .Ve | |
213 | .Sp | |
214 | Set the directedness of the graph \f(CW$G\fR to \f(CW$d\fR or return the | |
215 | current directedness. Directedness defaults to true. | |
216 | .IP "undirected" 4 | |
217 | .IX Item "undirected" | |
218 | .Vb 1 | |
219 | \& $b = $G->undirected($d) | |
220 | .Ve | |
221 | .Sp | |
222 | Set the undirectedness of the graph \f(CW$G\fR to \f(CW$u\fR or return the | |
223 | current undirectedness. Undirectedness defaults to false. | |
224 | .IP "has_edge" 4 | |
225 | .IX Item "has_edge" | |
226 | .Vb 1 | |
227 | \& $b = $G->has_edge($u, $v) | |
228 | .Ve | |
229 | .Sp | |
230 | Return true if the graph \f(CW$G\fR has the edge between | |
231 | the vertices \f(CW$u\fR, \f(CW$v\fR. | |
232 | .IP "has_edges" 4 | |
233 | .IX Item "has_edges" | |
234 | .Vb 1 | |
235 | \& $G->has_edges($u1, $v1, $u2, $v2, ...) | |
236 | .Ve | |
237 | .Sp | |
238 | In list context returns a list which contains true for each | |
239 | edge in the graph \f(CW$G\fR defined by the vertices \f(CW$u1\fR, \f(CW$v1\fR, ..., | |
240 | and false for each non-existing edge. In scalar context | |
241 | returns the number of the existing edges. | |
242 | .IP "has_path" 4 | |
243 | .IX Item "has_path" | |
244 | .Vb 1 | |
245 | \& $G->has_path($u, $v, ...) | |
246 | .Ve | |
247 | .Sp | |
248 | Return true if the graph \f(CW$G\fR has the cycle defined by | |
249 | the vertices \f(CW$u\fR, \f(CW$v\fR, ..., false otherwise. | |
250 | .IP "has_cycle" 4 | |
251 | .IX Item "has_cycle" | |
252 | .Vb 1 | |
253 | \& $G->has_cycle($u, $v, ...) | |
254 | .Ve | |
255 | .Sp | |
256 | Return true if the graph \f(CW$G\fR has the cycle defined by | |
257 | the vertices \f(CW$u\fR, \f(CW$v\fR, ...,false otherwise. | |
258 | .IP "vertex_set" 4 | |
259 | .IX Item "vertex_set" | |
260 | .Vb 1 | |
261 | \& $s = $G->vertex_set($v) | |
262 | .Ve | |
263 | .Sp | |
264 | Returns the vertex set of the vertex \f(CW$v\fR in the graph \f(CW$G\fR. | |
265 | A \*(L"vertex set\*(R" is represented by its parent vertex. | |
266 | .IP "add_edge" 4 | |
267 | .IX Item "add_edge" | |
268 | .Vb 1 | |
269 | \& $G = $G->add_edge($u, $v) | |
270 | .Ve | |
271 | .Sp | |
272 | Adds the edge defined by the vertices \f(CW$u\fR, \f(CW$v\fR, to the graph \f(CW$G\fR. | |
273 | Also implicitly adds the vertices. Returns the graph. | |
274 | .IP "add_edges" 4 | |
275 | .IX Item "add_edges" | |
276 | .Vb 1 | |
277 | \& $G = $G->add_edges($u1, $v1, $u2, $v2, ...) | |
278 | .Ve | |
279 | .Sp | |
280 | Adds the edge defined by the vertices \f(CW$u1\fR, \f(CW$v1\fR, ..., | |
281 | to the graph \f(CW$G\fR. Also implicitly adds the vertices. | |
282 | Returns the graph. | |
283 | .IP "add_path" 4 | |
284 | .IX Item "add_path" | |
285 | .Vb 1 | |
286 | \& $G->add_path($u, $v, ...) | |
287 | .Ve | |
288 | .Sp | |
289 | Adds the path defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ..., | |
290 | to the graph \f(CW$G\fR. Also implicitly adds the vertices. | |
291 | Returns the graph. | |
292 | .IP "add_cycle" 4 | |
293 | .IX Item "add_cycle" | |
294 | .Vb 1 | |
295 | \& $G = $G->add_cycle($u, $v, ...) | |
296 | .Ve | |
297 | .Sp | |
298 | Adds the cycle defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ..., | |
299 | to the graph \f(CW$G\fR. Also implicitly adds the vertices. | |
300 | Returns the graph. | |
301 | .IP "neighbors" 4 | |
302 | .IX Item "neighbors" | |
303 | .Vb 1 | |
304 | \& @n = $G->neighbors($v) | |
305 | .Ve | |
306 | .Sp | |
307 | Returns the neighbor vertices of the vertex in the graph. | |
308 | (Also 'neighbours' works.) | |
309 | .IP "successors" 4 | |
310 | .IX Item "successors" | |
311 | .Vb 1 | |
312 | \& @s = $G->successors($v) | |
313 | .Ve | |
314 | .Sp | |
315 | Returns the successor vertices of the vertex in the graph. | |
316 | .IP "predecessors" 4 | |
317 | .IX Item "predecessors" | |
318 | .Vb 1 | |
319 | \& @p = $G->predecessors($v) | |
320 | .Ve | |
321 | .Sp | |
322 | Returns the predecessor vertices of the vertex in the graph. | |
323 | .IP "out_edges" 4 | |
324 | .IX Item "out_edges" | |
325 | .Vb 1 | |
326 | \& @e = $G->out_edges($v) | |
327 | .Ve | |
328 | .Sp | |
329 | Returns the edges leading out of the vertex \f(CW$v\fR in the graph \f(CW$G\fR. | |
330 | In list context returns the edges as ($start_vertex, \f(CW$end_vertex\fR) | |
331 | pairs. In scalar context returns the number of the edges. | |
332 | .IP "in_edges" 4 | |
333 | .IX Item "in_edges" | |
334 | .Vb 1 | |
335 | \& @e = $G->in_edges($v) | |
336 | .Ve | |
337 | .Sp | |
338 | Returns the edges leading into the vertex \f(CW$v\fR in the graph \f(CW$G\fR. | |
339 | In list context returns the edges as ($start_vertex, \f(CW$end_vertex\fR) | |
340 | pairs; in scalar context returns the number of the edges. | |
341 | .IP "edges" 4 | |
342 | .IX Item "edges" | |
343 | .Vb 1 | |
344 | \& @e = $G->edges($u, $v) | |
345 | .Ve | |
346 | .Sp | |
347 | Returns the edges between the vertices \f(CW$u\fR and \f(CW$v\fR, or if \f(CW$v\fR | |
348 | is undefined, the edges leading into or out of the vertex \f(CW$u\fR, | |
349 | or if \f(CW$u\fR is undefined, returns all the edges, of the graph \f(CW$G\fR. | |
350 | In list context returns the edges as a list of | |
351 | \&\f(CW$start_vertex\fR, \f(CW$end_vertex\fR pairs; in scalar context | |
352 | returns the number of the edges. | |
353 | .IP "delete_edge" 4 | |
354 | .IX Item "delete_edge" | |
355 | .Vb 1 | |
356 | \& $G = $G->delete_edge($u, $v) | |
357 | .Ve | |
358 | .Sp | |
359 | Deletes an edge defined by the vertices \f(CW$u\fR, \f(CW$v\fR from the graph \f(CW$G\fR. | |
360 | Note that the edge need not actually exist. | |
361 | Returns the graph. | |
362 | .IP "delete_edges" 4 | |
363 | .IX Item "delete_edges" | |
364 | .Vb 1 | |
365 | \& $G = $G->delete_edges($u1, $v1, $u2, $v2, ..) | |
366 | .Ve | |
367 | .Sp | |
368 | Deletes edges defined by the vertices \f(CW$u1\fR, \f(CW$v1\fR, ..., | |
369 | from the graph \f(CW$G\fR. | |
370 | Note that the edges need not actually exist. | |
371 | Returns the graph. | |
372 | .IP "delete_path" 4 | |
373 | .IX Item "delete_path" | |
374 | .Vb 1 | |
375 | \& $G = $G->delete_path($u, $v, ...) | |
376 | .Ve | |
377 | .Sp | |
378 | Deletes a path defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ..., from the graph \f(CW$G\fR. | |
379 | Note that the path need not actually exist. Returns the graph. | |
380 | .IP "delete_cycle" 4 | |
381 | .IX Item "delete_cycle" | |
382 | .Vb 1 | |
383 | \& $G = $G->delete_cycle($u, $v, ...) | |
384 | .Ve | |
385 | .Sp | |
386 | Deletes a cycle defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ..., from the graph \f(CW$G\fR. | |
387 | Note that the cycle need not actually exist. Returns the graph. | |
388 | .IP "delete_vertex" 4 | |
389 | .IX Item "delete_vertex" | |
390 | .Vb 1 | |
391 | \& $G = $G->delete_vertex($v) | |
392 | .Ve | |
393 | .Sp | |
394 | Deletes the vertex \f(CW$v\fR and all its edges from the graph \f(CW$G\fR. | |
395 | Note that the vertex need not actually exist. | |
396 | Returns the graph. | |
397 | .IP "delete_vertices" 4 | |
398 | .IX Item "delete_vertices" | |
399 | .Vb 1 | |
400 | \& $G = $G->delete_vertices(@v) | |
401 | .Ve | |
402 | .Sp | |
403 | Deletes the vertices \f(CW@v\fR and all their edges from the graph \f(CW$G\fR. | |
404 | Note that the vertices need not actually exist. | |
405 | Returns the graph. | |
406 | .IP "in_degree" 4 | |
407 | .IX Item "in_degree" | |
408 | .Vb 1 | |
409 | \& $d = $G->in_degree($v) | |
410 | .Ve | |
411 | .Sp | |
412 | Returns the in-degree of the vertex \f(CW$v\fR in the graph \f(CW$G\fR, | |
413 | or, if \f(CW$v\fR is undefined, the total in-degree of all the | |
414 | vertices of the graph, or undef if the vertex doesn't | |
415 | exist in the graph. | |
416 | .IP "out_degree" 4 | |
417 | .IX Item "out_degree" | |
418 | .Vb 1 | |
419 | \& $d = $G->out_degree($v) | |
420 | .Ve | |
421 | .Sp | |
422 | Returns the out-degree of the vertex \f(CW$v\fR in the graph \f(CW$G\fR, | |
423 | or, if \f(CW$v\fR is undefined, the total out-degree of all the | |
424 | vertices of the graph, of undef if the vertex doesn't | |
425 | exist in the graph. | |
426 | .IP "degree" 4 | |
427 | .IX Item "degree" | |
428 | .Vb 1 | |
429 | \& $d = $G->degree($v) | |
430 | .Ve | |
431 | .Sp | |
432 | Returns the degree of the vertex \f(CW$v\fR in the graph \f(CW$G\fR | |
433 | or, if \f(CW$v\fR is undefined, the total degree of all the | |
434 | vertices of the graph, or undef if the vertex \f(CW$v\fR | |
435 | doesn't exist in the graph. | |
436 | .IP "average_degree" 4 | |
437 | .IX Item "average_degree" | |
438 | .Vb 1 | |
439 | \& $d = $G->average_degree | |
440 | .Ve | |
441 | .Sp | |
442 | Returns the average degree of the vertices of the graph \f(CW$G\fR. | |
443 | .IP "is_source_vertex" 4 | |
444 | .IX Item "is_source_vertex" | |
445 | .Vb 1 | |
446 | \& $b = $G->is_source_vertex($v) | |
447 | .Ve | |
448 | .Sp | |
449 | Returns true if the vertex \f(CW$v\fR is a source vertex of the graph \f(CW$G\fR. | |
450 | .IP "is_sink_vertex" 4 | |
451 | .IX Item "is_sink_vertex" | |
452 | .Vb 1 | |
453 | \& $b = $G->is_sink_vertex($v) | |
454 | .Ve | |
455 | .Sp | |
456 | Returns true if the vertex \f(CW$v\fR is a sink vertex of the graph \f(CW$G\fR. | |
457 | .IP "is_isolated_vertex" 4 | |
458 | .IX Item "is_isolated_vertex" | |
459 | .Vb 1 | |
460 | \& $b = $G->is_isolated_vertex($v) | |
461 | .Ve | |
462 | .Sp | |
463 | Returns true if the vertex \f(CW$v\fR is a isolated vertex of the graph \f(CW$G\fR. | |
464 | .IP "is_exterior_vertex" 4 | |
465 | .IX Item "is_exterior_vertex" | |
466 | .Vb 1 | |
467 | \& $b = $G->is_exterior_vertex($v) | |
468 | .Ve | |
469 | .Sp | |
470 | Returns true if the vertex \f(CW$v\fR is a exterior vertex of the graph \f(CW$G\fR. | |
471 | .IP "is_interior_vertex" 4 | |
472 | .IX Item "is_interior_vertex" | |
473 | .Vb 1 | |
474 | \& $b = $G->is_interior_vertex($v) | |
475 | .Ve | |
476 | .Sp | |
477 | Returns true if the vertex \f(CW$v\fR is a interior vertex of the graph \f(CW$G\fR. | |
478 | .IP "is_self_loop_vertex" 4 | |
479 | .IX Item "is_self_loop_vertex" | |
480 | .Vb 1 | |
481 | \& $b = $G->is_self_loop_vertex($v) | |
482 | .Ve | |
483 | .Sp | |
484 | Returns true if the vertex \f(CW$v\fR is a self-loop vertex of the graph \f(CW$G\fR. | |
485 | .IP "source_vertices" 4 | |
486 | .IX Item "source_vertices" | |
487 | .Vb 1 | |
488 | \& @s = $G->source_vertices | |
489 | .Ve | |
490 | .Sp | |
491 | Returns the source vertices \f(CW@s\fR of the graph \f(CW$G\fR. | |
492 | .IP "sink_vertices" 4 | |
493 | .IX Item "sink_vertices" | |
494 | .Vb 1 | |
495 | \& @s = $G->sink_vertices | |
496 | .Ve | |
497 | .Sp | |
498 | Returns the sink vertices \f(CW@s\fR of the graph \f(CW$G\fR. | |
499 | .IP "isolated_vertices" 4 | |
500 | .IX Item "isolated_vertices" | |
501 | .Vb 1 | |
502 | \& @i = $G->isolated_vertices | |
503 | .Ve | |
504 | .Sp | |
505 | Returns the isolated vertices \f(CW@i\fR of the graph \f(CW$G\fR. | |
506 | .IP "exterior_vertices" 4 | |
507 | .IX Item "exterior_vertices" | |
508 | .Vb 1 | |
509 | \& @e = $G->exterior_vertices | |
510 | .Ve | |
511 | .Sp | |
512 | Returns the exterior vertices \f(CW@e\fR of the graph \f(CW$G\fR. | |
513 | .IP "interior_vertices" 4 | |
514 | .IX Item "interior_vertices" | |
515 | .Vb 1 | |
516 | \& @i = $G->interior_vertices | |
517 | .Ve | |
518 | .Sp | |
519 | Returns the interior vertices \f(CW@i\fR of the graph \f(CW$G\fR. | |
520 | .IP "self_loop_vertices" 4 | |
521 | .IX Item "self_loop_vertices" | |
522 | .Vb 1 | |
523 | \& @s = $G->self_loop_vertices | |
524 | .Ve | |
525 | .Sp | |
526 | Returns the self-loop vertices \f(CW@s\fR of the graph \f(CW$G\fR. | |
527 | .IP "density_limits" 4 | |
528 | .IX Item "density_limits" | |
529 | .Vb 1 | |
530 | \& ($sparse, $dense, $complete) = $G->density_limits | |
531 | .Ve | |
532 | .Sp | |
533 | Returns the density limits for the number of edges | |
534 | in the graph \f(CW$G\fR. Note that reaching \f(CW$complete\fR edges | |
535 | does not really guarantee completeness because we | |
536 | can have multigraphs. The limit of sparse is less | |
537 | than 1/4 of the edges of the complete graph, the | |
538 | limit of dense is more than 3/4 of the edges of the | |
539 | complete graph. | |
540 | .IP "density" 4 | |
541 | .IX Item "density" | |
542 | .Vb 1 | |
543 | \& $d = $G->density | |
544 | .Ve | |
545 | .Sp | |
546 | Returns the density \f(CW$d\fR of the graph \f(CW$G\fR. | |
547 | .IP "is_sparse" 4 | |
548 | .IX Item "is_sparse" | |
549 | .Vb 1 | |
550 | \& $d = $G->is_sparse | |
551 | .Ve | |
552 | .Sp | |
553 | Returns true if the graph \f(CW$G\fR is sparse. | |
554 | .IP "is_dense" 4 | |
555 | .IX Item "is_dense" | |
556 | .Vb 1 | |
557 | \& $d = $G->is_dense | |
558 | .Ve | |
559 | .Sp | |
560 | Returns true if the graph \f(CW$G\fR is dense. | |
561 | .IP "complete" 4 | |
562 | .IX Item "complete" | |
563 | .Vb 1 | |
564 | \& $C = $G->complete; | |
565 | .Ve | |
566 | .Sp | |
567 | Returns a new complete graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR. | |
568 | .IP "complement" 4 | |
569 | .IX Item "complement" | |
570 | .Vb 1 | |
571 | \& $C = $G->complement; | |
572 | .Ve | |
573 | .Sp | |
574 | Returns a new complement graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR. | |
575 | .IP "copy" 4 | |
576 | .IX Item "copy" | |
577 | .Vb 1 | |
578 | \& $C = $G->copy; | |
579 | .Ve | |
580 | .Sp | |
581 | Returns a new graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR. | |
582 | .IP "transpose" 4 | |
583 | .IX Item "transpose" | |
584 | .Vb 1 | |
585 | \& $T = $G->transpose; | |
586 | .Ve | |
587 | .Sp | |
588 | Returns a new transpose graph \f(CW$T\fR corresponding to the graph \f(CW$G\fR. | |
589 | .IP "set_attribute" 4 | |
590 | .IX Item "set_attribute" | |
591 | .Vb 3 | |
592 | \& $G->set_attribute($attribute, $value) | |
593 | \& $G->set_attribute($attribute, $v, $value) | |
594 | \& $G->set_attribute($attribute, $u, $v, $value) | |
595 | .Ve | |
596 | .Sp | |
597 | Sets the \f(CW$attribute\fR of graph/vertex/edge to \f(CW$value\fR | |
598 | but only if the vertex/edge already exists. Returns | |
599 | true if the attribute is set successfully, false if not. | |
600 | .IP "get_attribute" 4 | |
601 | .IX Item "get_attribute" | |
602 | .Vb 3 | |
603 | \& $value = $G->get_attribute($attribute) | |
604 | \& $value = $G->get_attribute($attribute, $v) | |
605 | \& $value = $G->get_attribute($attribute, $u, $v) | |
606 | .Ve | |
607 | .Sp | |
608 | Returns the \f(CW$value\fR of \f(CW$attribute\fR of graph/vertex/edge. | |
609 | .IP "has_attribute" 4 | |
610 | .IX Item "has_attribute" | |
611 | .Vb 3 | |
612 | \& $value = $G->has_attribute($attribute) | |
613 | \& $value = $G->has_attribute($attribute, $v) | |
614 | \& $value = $G->has_attribute($attribute, $u, $v) | |
615 | .Ve | |
616 | .Sp | |
617 | Returns the \f(CW$value\fR of \f(CW$attribute\fR of graph/vertex/edge. | |
618 | .IP "get_attributes" 4 | |
619 | .IX Item "get_attributes" | |
620 | .Vb 3 | |
621 | \& %attributes = $G->get_attributes() | |
622 | \& %attributes = $G->get_attributes($v) | |
623 | \& %attributes = $G->get_attributes($u, $v) | |
624 | .Ve | |
625 | .Sp | |
626 | Returns as a hash all the attribute names and values | |
627 | of graph/vertex/edge. | |
628 | .IP "delete_attribute" 4 | |
629 | .IX Item "delete_attribute" | |
630 | .Vb 3 | |
631 | \& $G->delete_attribute($attribute) | |
632 | \& $G->delete_attribute($attribute, $v) | |
633 | \& $G->delete_attribute($attribute, $u, $v) | |
634 | .Ve | |
635 | .Sp | |
636 | Deletes the \f(CW$attribute\fR of graph/vertex/edge. | |
637 | .IP "delete_attributes" 4 | |
638 | .IX Item "delete_attributes" | |
639 | .Vb 3 | |
640 | \& $G->delete_attributes() | |
641 | \& $G->delete_attributes($v) | |
642 | \& $G->delete_attributes($u, $v) | |
643 | .Ve | |
644 | .Sp | |
645 | Deletes all the attributes of graph/vertex/edge. | |
646 | .IP "add_weighted_edge" 4 | |
647 | .IX Item "add_weighted_edge" | |
648 | .Vb 1 | |
649 | \& $G->add_weighted_edge($u, $w, $v, $a) | |
650 | .Ve | |
651 | .Sp | |
652 | Adds in the graph \f(CW$G\fR an edge from vertex \f(CW$u\fR to vertex \f(CW$v\fR | |
653 | and the edge attribute 'weight' set to \f(CW$w\fR. | |
654 | .IP "add_weighted_edges" 4 | |
655 | .IX Item "add_weighted_edges" | |
656 | .Vb 1 | |
657 | \& $G->add_weighted_edges($u1, $w1, $v1, $u2, $w2, $v2, ...) | |
658 | .Ve | |
659 | .Sp | |
660 | Adds in the graph \f(CW$G\fR the weighted edges. | |
661 | .IP "add_weighted_path" 4 | |
662 | .IX Item "add_weighted_path" | |
663 | .Vb 1 | |
664 | \& $G->add_weighted_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn) | |
665 | .Ve | |
666 | .Sp | |
667 | Adds in the graph \f(CW$G\fR the n edges defined by the path \f(CW$v1\fR ... \f(CW$vn\fR | |
668 | with the n\-1 'weight' attributes \f(CW$w1\fR ... \f(CW$wnm1\fR | |
669 | .IP "MST_Kruskal" 4 | |
670 | .IX Item "MST_Kruskal" | |
671 | .Vb 1 | |
672 | \& $MST = $G->MST_Kruskal; | |
673 | .Ve | |
674 | .Sp | |
675 | Returns Kruskal's Minimum Spanning Tree (as a graph) of | |
676 | the graph \f(CW$G\fR based on the 'weight' attributes of the edges. | |
677 | (Needs the \->\fIvertex_set()\fR method.) | |
678 | .IP "edge_classify" 4 | |
679 | .IX Item "edge_classify" | |
680 | .Vb 1 | |
681 | \& @C = $G->edge_classify(%param) | |
682 | .Ve | |
683 | .Sp | |
684 | Returns the edge classification as a list where each element | |
685 | is a triplet [$u, \f(CW$v\fR, \f(CW$class\fR] the \f(CW$u\fR, \f(CW$v\fR being the vertices | |
686 | of an edge and \f(CW$class\fR being the class. The \f(CW%param\fR can be | |
687 | used to control the search. | |
688 | .IP "toposort" 4 | |
689 | .IX Item "toposort" | |
690 | .Vb 1 | |
691 | \& @toposort = $G->toposort | |
692 | .Ve | |
693 | .Sp | |
694 | Returns the vertices of the graph \f(CW$G\fR sorted topologically. | |
695 | .IP "strongly_connected_components" 4 | |
696 | .IX Item "strongly_connected_components" | |
697 | .Vb 1 | |
698 | \& @S = $G->strongly_connected_components | |
699 | .Ve | |
700 | .Sp | |
701 | Returns the strongly connected components \f(CW@S\fR of the graph \f(CW$G\fR | |
702 | as a list of anonymous lists of vertices, each anonymous list | |
703 | containing the vertices belonging to one strongly connected | |
704 | component. | |
705 | .IP "strongly_connected_graph" 4 | |
706 | .IX Item "strongly_connected_graph" | |
707 | .Vb 1 | |
708 | \& $T = $G->strongly_connected_graph | |
709 | .Ve | |
710 | .Sp | |
711 | Returns the strongly connected graph \f(CW$T\fR of the graph \f(CW$G\fR. | |
712 | The names of the strongly connected components are | |
713 | formed from their constituent vertices by concatenating | |
714 | their names by '+'\-characters: \*(L"a\*(R" and \*(L"b\*(R" \-\-> \*(L"a+b\*(R". | |
715 | .IP "APSP_Floyd_Warshall" 4 | |
716 | .IX Item "APSP_Floyd_Warshall" | |
717 | .Vb 1 | |
718 | \& $APSP = $G->APSP_Floyd_Warshall | |
719 | .Ve | |
720 | .Sp | |
721 | Returns the All-pairs Shortest Paths graph of the graph \f(CW$G\fR | |
722 | computed using the Floyd-Warshall algorithm and the attribute | |
723 | \&'weight' on the edges. | |
724 | The returned graph has an edge for each shortest path. | |
725 | An edge has attributes \*(L"weight\*(R" and \*(L"path\*(R"; for the length of | |
726 | the shortest path and for the path (an anonymous list) itself. | |
727 | .IP "TransitiveClosure_Floyd_Warshall" 4 | |
728 | .IX Item "TransitiveClosure_Floyd_Warshall" | |
729 | .Vb 1 | |
730 | \& $TransitiveClosure = $G->TransitiveClosure_Floyd_Warshall | |
731 | .Ve | |
732 | .Sp | |
733 | Returns the Transitive Closure graph of the graph \f(CW$G\fR computed | |
734 | using the Floyd-Warshall algorithm. | |
735 | The resulting graph has an edge between each *ordered* pair of | |
736 | vertices in which the second vertex is reachable from the first. | |
737 | .IP "articulation points" 4 | |
738 | .IX Item "articulation points" | |
739 | .Vb 1 | |
740 | \& @A = $G->articulation_points(%param) | |
741 | .Ve | |
742 | .Sp | |
743 | Returns the articulation points (vertices) \f(CW@A\fR of the graph \f(CW$G\fR. | |
744 | The \f(CW%param\fR can be used to control the search. | |
745 | .IP "is_biconnected" 4 | |
746 | .IX Item "is_biconnected" | |
747 | .Vb 1 | |
748 | \& $b = $G->is_biconnected | |
749 | .Ve | |
750 | .Sp | |
751 | Returns true is the graph \f(CW$G\fR is biconnected | |
752 | (has no articulation points), false otherwise. | |
753 | .IP "largest_out_degree" 4 | |
754 | .IX Item "largest_out_degree" | |
755 | .Vb 1 | |
756 | \& $v = $G->largest_out_degree( @V ) | |
757 | .Ve | |
758 | .Sp | |
759 | Selects the vertex \f(CW$v\fR from the vertices \f(CW@V\fR having | |
760 | the largest out degree in the graph \f(CW$G\fR. | |
761 | .IP "MST_Prim" 4 | |
762 | .IX Item "MST_Prim" | |
763 | .Vb 1 | |
764 | \& $MST = $G->MST_Prim($u) | |
765 | .Ve | |
766 | .Sp | |
767 | Returns Prim's Minimum Spanning Tree (as a graph) of | |
768 | the graph \f(CW$G\fR based on the 'weight' attributes of the edges. | |
769 | The optional start vertex is \f(CW$u\fR, if none is given, a hopefully | |
770 | good one (a vertex with a large out degree) is chosen. | |
771 | .IP "SSSP_Dijkstra" 4 | |
772 | .IX Item "SSSP_Dijkstra" | |
773 | .Vb 1 | |
774 | \& $SSSP = $G->SSSP_Dijkstra($s) | |
775 | .Ve | |
776 | .Sp | |
777 | Returns the Single-source Shortest Paths (as a graph) | |
778 | of the graph \f(CW$G\fR starting from the vertex \f(CW$s\fR using Dijktra's | |
779 | \&\s-1SSSP\s0 algorithm. | |
780 | .IP "SSSP_Bellman_Ford" 4 | |
781 | .IX Item "SSSP_Bellman_Ford" | |
782 | .Vb 1 | |
783 | \& $SSSP = $G->SSSP_Bellman_Ford($s) | |
784 | .Ve | |
785 | .Sp | |
786 | Returns the Single-source Shortest Paths (as a graph) | |
787 | of the graph \f(CW$G\fR starting from the vertex \f(CW$s\fR using Bellman-Ford | |
788 | \&\s-1SSSP\s0 algorithm. If there are one or more negatively weighted | |
789 | cycles, returns undef. | |
790 | .IP "\s-1SSSP_DAG\s0" 4 | |
791 | .IX Item "SSSP_DAG" | |
792 | .Vb 1 | |
793 | \& $SSSP = $G->SSSP_DAG($s) | |
794 | .Ve | |
795 | .Sp | |
796 | Returns the Single-source Shortest Paths (as a graph) | |
797 | of the \s-1DAG\s0 \f(CW$G\fR starting from vertex \f(CW$s\fR. | |
798 | .IP "add_capacity_edge" 4 | |
799 | .IX Item "add_capacity_edge" | |
800 | .Vb 1 | |
801 | \& $G->add_capacity_edge($u, $w, $v, $a) | |
802 | .Ve | |
803 | .Sp | |
804 | Adds in the graph \f(CW$G\fR an edge from vertex \f(CW$u\fR to vertex \f(CW$v\fR | |
805 | and the edge attribute 'capacity' set to \f(CW$w\fR. | |
806 | .IP "add_capacity_edges" 4 | |
807 | .IX Item "add_capacity_edges" | |
808 | .Vb 1 | |
809 | \& $G->add_capacity_edges($u1, $w1, $v1, $u2, $w2, $v2, ...) | |
810 | .Ve | |
811 | .Sp | |
812 | Adds in the graph \f(CW$G\fR the capacity edges. | |
813 | .IP "add_capacity_path" 4 | |
814 | .IX Item "add_capacity_path" | |
815 | .Vb 1 | |
816 | \& $G->add_capacity_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn) | |
817 | .Ve | |
818 | .Sp | |
819 | Adds in the graph \f(CW$G\fR the n edges defined by the path \f(CW$v1\fR ... \f(CW$vn\fR | |
820 | with the n\-1 'capacity' attributes \f(CW$w1\fR ... \f(CW$wnm1\fR | |
821 | .IP "Flow_Ford_Fulkerson" 4 | |
822 | .IX Item "Flow_Ford_Fulkerson" | |
823 | .Vb 1 | |
824 | \& $F = $G->Flow_Ford_Fulkerson($S) | |
825 | .Ve | |
826 | .Sp | |
827 | Returns the (maximal) flow network of the flow network \f(CW$G\fR, | |
828 | parametrized by the state \f(CW$S\fR. The \f(CW$G\fR must have 'capacity' | |
829 | attributes on its edges. \f(CW$S\fR\->{ source } must contain the | |
830 | source vertex and \f(CW$S\fR\->{ sink } the sink vertex, and | |
831 | most importantly \f(CW$S\fR\->{ next_augmenting_path } must contain | |
832 | an anonymous subroutine which takes \f(CW$F\fR and \f(CW$S\fR as arguments | |
833 | and returns the next potential augmenting path. | |
834 | Flow_Ford_Fulkerson will do the augmenting. | |
835 | The result graph \f(CW$F\fR will have 'flow' and (residual) 'capacity' | |
836 | attributes on its edges. | |
837 | .IP "Flow_Edmonds_Karp" 4 | |
838 | .IX Item "Flow_Edmonds_Karp" | |
839 | .Vb 1 | |
840 | \& $F = $G->Flow_Edmonds_Karp($source, $sink) | |
841 | .Ve | |
842 | .Sp | |
843 | Return the maximal flow network of the graph \f(CW$G\fR built | |
844 | using the Edmonds-Karp version of Ford\-Fulkerson. | |
845 | The input graph \f(CW$G\fR must have 'capacity' attributes on | |
846 | its edges; resulting flow graph will have 'capacity' and 'flow' | |
847 | attributes on its edges. | |
848 | .IP "eq" 4 | |
849 | .IX Item "eq" | |
850 | .Vb 1 | |
851 | \& $G->eq($H) | |
852 | .Ve | |
853 | .Sp | |
854 | Return true if the graphs (actually, their string representations) | |
855 | are identical. This means really identical: they must have identical | |
856 | vertex names and identical edges between the vertices, and they must | |
857 | be similarly directed. (Just isomorphism isn't enough.) | |
858 | .SH "COPYRIGHT" | |
859 | .IX Header "COPYRIGHT" | |
860 | Copyright 1999, O'Reilly & Associates. | |
861 | .PP | |
862 | This code is distributed under the same copyright terms as Perl itself. |