|
1 <?xml version="1.0" encoding="ascii"?> |
|
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" |
|
3 "DTD/xhtml1-transitional.dtd"> |
|
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> |
|
5 <head> |
|
6 <title>graph.graph</title> |
|
7 <link rel="stylesheet" href="epydoc.css" type="text/css" /> |
|
8 <script type="text/javascript" src="epydoc.js"></script> |
|
9 </head> |
|
10 |
|
11 <body bgcolor="white" text="black" link="blue" vlink="#204080" |
|
12 alink="#204080"> |
|
13 <!-- ==================== NAVIGATION BAR ==================== --> |
|
14 <table class="navbar" border="0" width="100%" cellpadding="0" |
|
15 bgcolor="#a0c0ff" cellspacing="0"> |
|
16 <tr valign="middle"> |
|
17 <!-- Home link --> |
|
18 <th> <a |
|
19 href="graph-module.html">Home</a> </th> |
|
20 |
|
21 <!-- Tree link --> |
|
22 <th> <a |
|
23 href="module-tree.html">Trees</a> </th> |
|
24 |
|
25 <!-- Index link --> |
|
26 <th> <a |
|
27 href="identifier-index.html">Indices</a> </th> |
|
28 |
|
29 <!-- Help link --> |
|
30 <th> <a |
|
31 href="help.html">Help</a> </th> |
|
32 |
|
33 <!-- Project homepage --> |
|
34 <th class="navbar" align="right" width="100%"> |
|
35 <table border="0" cellpadding="0" cellspacing="0"> |
|
36 <tr><th class="navbar" align="center" |
|
37 ><a class="navbar" target="_top" href="http://code.google.com/p/python-graph/">python-graph</a></th> |
|
38 </tr></table></th> |
|
39 </tr> |
|
40 </table> |
|
41 <table width="100%" cellpadding="0" cellspacing="0"> |
|
42 <tr valign="top"> |
|
43 <td width="100%"> |
|
44 <span class="breadcrumbs"> |
|
45 <a href="graph-module.html">Package graph</a> :: |
|
46 Class graph |
|
47 </span> |
|
48 </td> |
|
49 <td> |
|
50 <table cellpadding="0" cellspacing="0"> |
|
51 <!-- hide/show private --> |
|
52 </table> |
|
53 </td> |
|
54 </tr> |
|
55 </table> |
|
56 <!-- ==================== CLASS DESCRIPTION ==================== --> |
|
57 <h1 class="epydoc">Class graph</h1><p class="nomargin-top"></p> |
|
58 <pre class="base-tree"> |
|
59 object --+ |
|
60 | |
|
61 <strong class="uidshort">graph</strong> |
|
62 </pre> |
|
63 |
|
64 <hr /> |
|
65 <p>Graph class.</p> |
|
66 <p>Graphs are built of nodes and edges.</p> |
|
67 |
|
68 <!-- ==================== INSTANCE METHODS ==================== --> |
|
69 <a name="section-InstanceMethods"></a> |
|
70 <table class="summary" border="1" cellpadding="3" |
|
71 cellspacing="0" width="100%" bgcolor="white"> |
|
72 <tr bgcolor="#70b0f0" class="table-header"> |
|
73 <td align="left" colspan="2" class="table-header"> |
|
74 <span class="table-header">Instance Methods</span></td> |
|
75 </tr> |
|
76 <tr> |
|
77 <td width="15%" align="right" valign="top" class="summary"> |
|
78 <span class="summary-type"> </span> |
|
79 </td><td class="summary"> |
|
80 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
81 <tr> |
|
82 <td><span class="summary-sig"><a href="graph.graph-class.html#__init__" class="summary-sig-name">__init__</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
83 Initialize a graph.</td> |
|
84 <td align="right" valign="top"> |
|
85 |
|
86 |
|
87 </td> |
|
88 </tr> |
|
89 </table> |
|
90 |
|
91 </td> |
|
92 </tr> |
|
93 <tr> |
|
94 <td width="15%" align="right" valign="top" class="summary"> |
|
95 <span class="summary-type">iterator</span> |
|
96 </td><td class="summary"> |
|
97 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
98 <tr> |
|
99 <td><span class="summary-sig"><a href="graph.graph-class.html#__getitem__" class="summary-sig-name">__getitem__</a>(<span class="summary-sig-arg">self</span>, |
|
100 <span class="summary-sig-arg">node</span>)</span><br /> |
|
101 Return a iterator passing through all neighbors of the given node.</td> |
|
102 <td align="right" valign="top"> |
|
103 |
|
104 |
|
105 </td> |
|
106 </tr> |
|
107 </table> |
|
108 |
|
109 </td> |
|
110 </tr> |
|
111 <tr> |
|
112 <td width="15%" align="right" valign="top" class="summary"> |
|
113 <span class="summary-type">iterator</span> |
|
114 </td><td class="summary"> |
|
115 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
116 <tr> |
|
117 <td><span class="summary-sig"><a href="graph.graph-class.html#__iter__" class="summary-sig-name">__iter__</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
118 Return a iterator passing through all nodes in the graph.</td> |
|
119 <td align="right" valign="top"> |
|
120 |
|
121 |
|
122 </td> |
|
123 </tr> |
|
124 </table> |
|
125 |
|
126 </td> |
|
127 </tr> |
|
128 <tr> |
|
129 <td width="15%" align="right" valign="top" class="summary"> |
|
130 <span class="summary-type">number</span> |
|
131 </td><td class="summary"> |
|
132 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
133 <tr> |
|
134 <td><span class="summary-sig"><a href="graph.graph-class.html#__len__" class="summary-sig-name">__len__</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
135 Return the order of the graph when requested by len().</td> |
|
136 <td align="right" valign="top"> |
|
137 |
|
138 |
|
139 </td> |
|
140 </tr> |
|
141 </table> |
|
142 |
|
143 </td> |
|
144 </tr> |
|
145 <tr> |
|
146 <td width="15%" align="right" valign="top" class="summary"> |
|
147 <span class="summary-type">string</span> |
|
148 </td><td class="summary"> |
|
149 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
150 <tr> |
|
151 <td><span class="summary-sig"><a href="graph.graph-class.html#__str__" class="summary-sig-name">__str__</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
152 Return a string representing the graph when requested by str() (or |
|
153 print).</td> |
|
154 <td align="right" valign="top"> |
|
155 |
|
156 |
|
157 </td> |
|
158 </tr> |
|
159 </table> |
|
160 |
|
161 </td> |
|
162 </tr> |
|
163 <tr> |
|
164 <td width="15%" align="right" valign="top" class="summary"> |
|
165 <span class="summary-type"> </span> |
|
166 </td><td class="summary"> |
|
167 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
168 <tr> |
|
169 <td><span class="summary-sig"><a href="graph.graph-class.html#add_edge" class="summary-sig-name">add_edge</a>(<span class="summary-sig-arg">self</span>, |
|
170 <span class="summary-sig-arg">u</span>, |
|
171 <span class="summary-sig-arg">v</span>, |
|
172 <span class="summary-sig-arg">wt</span>=<span class="summary-sig-default">1</span>, |
|
173 <span class="summary-sig-arg">label</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string"></code><code class="variable-quote">'</code></span>, |
|
174 <span class="summary-sig-arg">attrs</span>=<span class="summary-sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span><br /> |
|
175 Add an edge (u,v) to the graph connecting nodes u and v.</td> |
|
176 <td align="right" valign="top"> |
|
177 |
|
178 |
|
179 </td> |
|
180 </tr> |
|
181 </table> |
|
182 |
|
183 </td> |
|
184 </tr> |
|
185 <tr> |
|
186 <td width="15%" align="right" valign="top" class="summary"> |
|
187 <span class="summary-type"> </span> |
|
188 </td><td class="summary"> |
|
189 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
190 <tr> |
|
191 <td><span class="summary-sig"><a href="graph.graph-class.html#add_edge_attribute" class="summary-sig-name">add_edge_attribute</a>(<span class="summary-sig-arg">self</span>, |
|
192 <span class="summary-sig-arg">u</span>, |
|
193 <span class="summary-sig-arg">v</span>, |
|
194 <span class="summary-sig-arg">attr</span>)</span><br /> |
|
195 Add attribute to the given edge.</td> |
|
196 <td align="right" valign="top"> |
|
197 |
|
198 |
|
199 </td> |
|
200 </tr> |
|
201 </table> |
|
202 |
|
203 </td> |
|
204 </tr> |
|
205 <tr> |
|
206 <td width="15%" align="right" valign="top" class="summary"> |
|
207 <span class="summary-type"> </span> |
|
208 </td><td class="summary"> |
|
209 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
210 <tr> |
|
211 <td><span class="summary-sig"><a href="graph.graph-class.html#add_graph" class="summary-sig-name">add_graph</a>(<span class="summary-sig-arg">self</span>, |
|
212 <span class="summary-sig-arg">graph</span>)</span><br /> |
|
213 Add other graph to the graph.</td> |
|
214 <td align="right" valign="top"> |
|
215 |
|
216 |
|
217 </td> |
|
218 </tr> |
|
219 </table> |
|
220 |
|
221 </td> |
|
222 </tr> |
|
223 <tr> |
|
224 <td width="15%" align="right" valign="top" class="summary"> |
|
225 <span class="summary-type"> </span> |
|
226 </td><td class="summary"> |
|
227 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
228 <tr> |
|
229 <td><span class="summary-sig"><a href="graph.graph-class.html#add_node" class="summary-sig-name">add_node</a>(<span class="summary-sig-arg">self</span>, |
|
230 <span class="summary-sig-arg">node</span>, |
|
231 <span class="summary-sig-arg">attrs</span>=<span class="summary-sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span><br /> |
|
232 Add given node to the graph.</td> |
|
233 <td align="right" valign="top"> |
|
234 |
|
235 |
|
236 </td> |
|
237 </tr> |
|
238 </table> |
|
239 |
|
240 </td> |
|
241 </tr> |
|
242 <tr> |
|
243 <td width="15%" align="right" valign="top" class="summary"> |
|
244 <span class="summary-type"> </span> |
|
245 </td><td class="summary"> |
|
246 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
247 <tr> |
|
248 <td><span class="summary-sig"><a href="graph.graph-class.html#add_node_attribute" class="summary-sig-name">add_node_attribute</a>(<span class="summary-sig-arg">self</span>, |
|
249 <span class="summary-sig-arg">node</span>, |
|
250 <span class="summary-sig-arg">attr</span>)</span><br /> |
|
251 Add attribute to the given node.</td> |
|
252 <td align="right" valign="top"> |
|
253 |
|
254 |
|
255 </td> |
|
256 </tr> |
|
257 </table> |
|
258 |
|
259 </td> |
|
260 </tr> |
|
261 <tr> |
|
262 <td width="15%" align="right" valign="top" class="summary"> |
|
263 <span class="summary-type"> </span> |
|
264 </td><td class="summary"> |
|
265 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
266 <tr> |
|
267 <td><span class="summary-sig"><a href="graph.graph-class.html#add_nodes" class="summary-sig-name">add_nodes</a>(<span class="summary-sig-arg">self</span>, |
|
268 <span class="summary-sig-arg">nodelist</span>)</span><br /> |
|
269 Add given nodes to the graph.</td> |
|
270 <td align="right" valign="top"> |
|
271 |
|
272 |
|
273 </td> |
|
274 </tr> |
|
275 </table> |
|
276 |
|
277 </td> |
|
278 </tr> |
|
279 <tr> |
|
280 <td width="15%" align="right" valign="top" class="summary"> |
|
281 <span class="summary-type"> </span> |
|
282 </td><td class="summary"> |
|
283 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
284 <tr> |
|
285 <td><span class="summary-sig"><a href="graph.graph-class.html#add_spanning_tree" class="summary-sig-name">add_spanning_tree</a>(<span class="summary-sig-arg">self</span>, |
|
286 <span class="summary-sig-arg">st</span>)</span><br /> |
|
287 Add a spanning tree to the graph.</td> |
|
288 <td align="right" valign="top"> |
|
289 |
|
290 |
|
291 </td> |
|
292 </tr> |
|
293 </table> |
|
294 |
|
295 </td> |
|
296 </tr> |
|
297 <tr> |
|
298 <td width="15%" align="right" valign="top" class="summary"> |
|
299 <span class="summary-type"> </span> |
|
300 </td><td class="summary"> |
|
301 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
302 <tr> |
|
303 <td><span class="summary-sig"><a href="graph.graph-class.html#complete" class="summary-sig-name">complete</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
304 Make the graph a complete graph.</td> |
|
305 <td align="right" valign="top"> |
|
306 |
|
307 |
|
308 </td> |
|
309 </tr> |
|
310 </table> |
|
311 |
|
312 </td> |
|
313 </tr> |
|
314 <tr> |
|
315 <td width="15%" align="right" valign="top" class="summary"> |
|
316 <span class="summary-type"> </span> |
|
317 </td><td class="summary"> |
|
318 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
319 <tr> |
|
320 <td><span class="summary-sig"><a href="graph.graph-class.html#del_edge" class="summary-sig-name">del_edge</a>(<span class="summary-sig-arg">self</span>, |
|
321 <span class="summary-sig-arg">u</span>, |
|
322 <span class="summary-sig-arg">v</span>)</span><br /> |
|
323 Remove an edge (u, v) from the graph.</td> |
|
324 <td align="right" valign="top"> |
|
325 |
|
326 |
|
327 </td> |
|
328 </tr> |
|
329 </table> |
|
330 |
|
331 </td> |
|
332 </tr> |
|
333 <tr> |
|
334 <td width="15%" align="right" valign="top" class="summary"> |
|
335 <span class="summary-type"> </span> |
|
336 </td><td class="summary"> |
|
337 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
338 <tr> |
|
339 <td><span class="summary-sig"><a href="graph.graph-class.html#del_node" class="summary-sig-name">del_node</a>(<span class="summary-sig-arg">self</span>, |
|
340 <span class="summary-sig-arg">node</span>)</span><br /> |
|
341 Remove a node from the graph.</td> |
|
342 <td align="right" valign="top"> |
|
343 |
|
344 |
|
345 </td> |
|
346 </tr> |
|
347 </table> |
|
348 |
|
349 </td> |
|
350 </tr> |
|
351 <tr> |
|
352 <td width="15%" align="right" valign="top" class="summary"> |
|
353 <span class="summary-type">list</span> |
|
354 </td><td class="summary"> |
|
355 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
356 <tr> |
|
357 <td><span class="summary-sig"><a href="graph.graph-class.html#edges" class="summary-sig-name">edges</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
358 Return all edges in the graph.</td> |
|
359 <td align="right" valign="top"> |
|
360 |
|
361 |
|
362 </td> |
|
363 </tr> |
|
364 </table> |
|
365 |
|
366 </td> |
|
367 </tr> |
|
368 <tr> |
|
369 <td width="15%" align="right" valign="top" class="summary"> |
|
370 <span class="summary-type">list</span> |
|
371 </td><td class="summary"> |
|
372 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
373 <tr> |
|
374 <td><span class="summary-sig"><a href="graph.graph-class.html#get_edge_attributes" class="summary-sig-name">get_edge_attributes</a>(<span class="summary-sig-arg">self</span>, |
|
375 <span class="summary-sig-arg">u</span>, |
|
376 <span class="summary-sig-arg">v</span>)</span><br /> |
|
377 Return the attributes of the given edge.</td> |
|
378 <td align="right" valign="top"> |
|
379 |
|
380 |
|
381 </td> |
|
382 </tr> |
|
383 </table> |
|
384 |
|
385 </td> |
|
386 </tr> |
|
387 <tr> |
|
388 <td width="15%" align="right" valign="top" class="summary"> |
|
389 <span class="summary-type">string</span> |
|
390 </td><td class="summary"> |
|
391 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
392 <tr> |
|
393 <td><span class="summary-sig"><a href="graph.graph-class.html#get_edge_label" class="summary-sig-name">get_edge_label</a>(<span class="summary-sig-arg">self</span>, |
|
394 <span class="summary-sig-arg">u</span>, |
|
395 <span class="summary-sig-arg">v</span>)</span><br /> |
|
396 Get the label of an edge.</td> |
|
397 <td align="right" valign="top"> |
|
398 |
|
399 |
|
400 </td> |
|
401 </tr> |
|
402 </table> |
|
403 |
|
404 </td> |
|
405 </tr> |
|
406 <tr> |
|
407 <td width="15%" align="right" valign="top" class="summary"> |
|
408 <span class="summary-type">number</span> |
|
409 </td><td class="summary"> |
|
410 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
411 <tr> |
|
412 <td><span class="summary-sig"><a href="graph.graph-class.html#get_edge_weight" class="summary-sig-name">get_edge_weight</a>(<span class="summary-sig-arg">self</span>, |
|
413 <span class="summary-sig-arg">u</span>, |
|
414 <span class="summary-sig-arg">v</span>)</span><br /> |
|
415 Get the weight of an edge.</td> |
|
416 <td align="right" valign="top"> |
|
417 |
|
418 |
|
419 </td> |
|
420 </tr> |
|
421 </table> |
|
422 |
|
423 </td> |
|
424 </tr> |
|
425 <tr> |
|
426 <td width="15%" align="right" valign="top" class="summary"> |
|
427 <span class="summary-type">list</span> |
|
428 </td><td class="summary"> |
|
429 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
430 <tr> |
|
431 <td><span class="summary-sig"><a href="graph.graph-class.html#get_node_attributes" class="summary-sig-name">get_node_attributes</a>(<span class="summary-sig-arg">self</span>, |
|
432 <span class="summary-sig-arg">node</span>)</span><br /> |
|
433 Return the attributes of the given node.</td> |
|
434 <td align="right" valign="top"> |
|
435 |
|
436 |
|
437 </td> |
|
438 </tr> |
|
439 </table> |
|
440 |
|
441 </td> |
|
442 </tr> |
|
443 <tr> |
|
444 <td width="15%" align="right" valign="top" class="summary"> |
|
445 <span class="summary-type">boolean</span> |
|
446 </td><td class="summary"> |
|
447 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
448 <tr> |
|
449 <td><span class="summary-sig"><a href="graph.graph-class.html#has_edge" class="summary-sig-name">has_edge</a>(<span class="summary-sig-arg">self</span>, |
|
450 <span class="summary-sig-arg">u</span>, |
|
451 <span class="summary-sig-arg">v</span>)</span><br /> |
|
452 Return whether an edge between nodes u and v exists.</td> |
|
453 <td align="right" valign="top"> |
|
454 |
|
455 |
|
456 </td> |
|
457 </tr> |
|
458 </table> |
|
459 |
|
460 </td> |
|
461 </tr> |
|
462 <tr> |
|
463 <td width="15%" align="right" valign="top" class="summary"> |
|
464 <span class="summary-type">boolean</span> |
|
465 </td><td class="summary"> |
|
466 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
467 <tr> |
|
468 <td><span class="summary-sig"><a href="graph.graph-class.html#has_node" class="summary-sig-name">has_node</a>(<span class="summary-sig-arg">self</span>, |
|
469 <span class="summary-sig-arg">node</span>)</span><br /> |
|
470 Return whether the requested node exists.</td> |
|
471 <td align="right" valign="top"> |
|
472 |
|
473 |
|
474 </td> |
|
475 </tr> |
|
476 </table> |
|
477 |
|
478 </td> |
|
479 </tr> |
|
480 <tr> |
|
481 <td width="15%" align="right" valign="top" class="summary"> |
|
482 <span class="summary-type">graph</span> |
|
483 </td><td class="summary"> |
|
484 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
485 <tr> |
|
486 <td><span class="summary-sig"><a href="graph.graph-class.html#inverse" class="summary-sig-name">inverse</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
487 Return the inverse of the graph.</td> |
|
488 <td align="right" valign="top"> |
|
489 |
|
490 |
|
491 </td> |
|
492 </tr> |
|
493 </table> |
|
494 |
|
495 </td> |
|
496 </tr> |
|
497 <tr> |
|
498 <td width="15%" align="right" valign="top" class="summary"> |
|
499 <span class="summary-type">list</span> |
|
500 </td><td class="summary"> |
|
501 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
502 <tr> |
|
503 <td><span class="summary-sig"><a href="graph.graph-class.html#neighbors" class="summary-sig-name">neighbors</a>(<span class="summary-sig-arg">self</span>, |
|
504 <span class="summary-sig-arg">node</span>)</span><br /> |
|
505 Return all nodes that are directly accessible from given node.</td> |
|
506 <td align="right" valign="top"> |
|
507 |
|
508 |
|
509 </td> |
|
510 </tr> |
|
511 </table> |
|
512 |
|
513 </td> |
|
514 </tr> |
|
515 <tr> |
|
516 <td width="15%" align="right" valign="top" class="summary"> |
|
517 <span class="summary-type">list</span> |
|
518 </td><td class="summary"> |
|
519 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
520 <tr> |
|
521 <td><span class="summary-sig"><a href="graph.graph-class.html#nodes" class="summary-sig-name">nodes</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
522 Return node list.</td> |
|
523 <td align="right" valign="top"> |
|
524 |
|
525 |
|
526 </td> |
|
527 </tr> |
|
528 </table> |
|
529 |
|
530 </td> |
|
531 </tr> |
|
532 <tr> |
|
533 <td width="15%" align="right" valign="top" class="summary"> |
|
534 <span class="summary-type">number</span> |
|
535 </td><td class="summary"> |
|
536 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
537 <tr> |
|
538 <td><span class="summary-sig"><a href="graph.graph-class.html#order" class="summary-sig-name">order</a>(<span class="summary-sig-arg">self</span>, |
|
539 <span class="summary-sig-arg">node</span>)</span><br /> |
|
540 Return the order of the given node.</td> |
|
541 <td align="right" valign="top"> |
|
542 |
|
543 |
|
544 </td> |
|
545 </tr> |
|
546 </table> |
|
547 |
|
548 </td> |
|
549 </tr> |
|
550 <tr> |
|
551 <td width="15%" align="right" valign="top" class="summary"> |
|
552 <span class="summary-type"> </span> |
|
553 </td><td class="summary"> |
|
554 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
555 <tr> |
|
556 <td><span class="summary-sig"><a href="graph.graph-class.html#set_edge_label" class="summary-sig-name">set_edge_label</a>(<span class="summary-sig-arg">self</span>, |
|
557 <span class="summary-sig-arg">u</span>, |
|
558 <span class="summary-sig-arg">v</span>, |
|
559 <span class="summary-sig-arg">label</span>)</span><br /> |
|
560 Set the label of an edge.</td> |
|
561 <td align="right" valign="top"> |
|
562 |
|
563 |
|
564 </td> |
|
565 </tr> |
|
566 </table> |
|
567 |
|
568 </td> |
|
569 </tr> |
|
570 <tr> |
|
571 <td width="15%" align="right" valign="top" class="summary"> |
|
572 <span class="summary-type"> </span> |
|
573 </td><td class="summary"> |
|
574 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
575 <tr> |
|
576 <td><span class="summary-sig"><a href="graph.graph-class.html#set_edge_weight" class="summary-sig-name">set_edge_weight</a>(<span class="summary-sig-arg">self</span>, |
|
577 <span class="summary-sig-arg">u</span>, |
|
578 <span class="summary-sig-arg">v</span>, |
|
579 <span class="summary-sig-arg">wt</span>)</span><br /> |
|
580 Set the weight of an edge.</td> |
|
581 <td align="right" valign="top"> |
|
582 |
|
583 |
|
584 </td> |
|
585 </tr> |
|
586 </table> |
|
587 |
|
588 </td> |
|
589 </tr> |
|
590 <tr> |
|
591 <td width="15%" align="right" valign="top" class="summary"> |
|
592 <span class="summary-type">iterator</span> |
|
593 </td><td class="summary"> |
|
594 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
595 <tr> |
|
596 <td><span class="summary-sig"><a href="graph.graph-class.html#traversal" class="summary-sig-name">traversal</a>(<span class="summary-sig-arg">self</span>, |
|
597 <span class="summary-sig-arg">node</span>, |
|
598 <span class="summary-sig-arg">order</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string">pre</code><code class="variable-quote">'</code></span>)</span><br /> |
|
599 Graph traversal iterator.</td> |
|
600 <td align="right" valign="top"> |
|
601 |
|
602 |
|
603 </td> |
|
604 </tr> |
|
605 </table> |
|
606 |
|
607 </td> |
|
608 </tr> |
|
609 <tr> |
|
610 <td width="15%" align="right" valign="top" class="summary"> |
|
611 <span class="summary-type"> </span> |
|
612 </td><td class="summary"> |
|
613 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
614 <tr> |
|
615 <td><span class="summary-sig"><a href="graph.graph-class.html#generate" class="summary-sig-name">generate</a>(<span class="summary-sig-arg">self</span>, |
|
616 <span class="summary-sig-arg">num_nodes</span>, |
|
617 <span class="summary-sig-arg">num_edges</span>, |
|
618 <span class="summary-sig-arg">weight_range</span>=<span class="summary-sig-default"><code class="variable-group">(</code>1<code class="variable-op">, </code>1<code class="variable-group">)</code></span>)</span><br /> |
|
619 Add nodes and random edges to the graph.</td> |
|
620 <td align="right" valign="top"> |
|
621 |
|
622 |
|
623 </td> |
|
624 </tr> |
|
625 </table> |
|
626 |
|
627 </td> |
|
628 </tr> |
|
629 <tr> |
|
630 <td width="15%" align="right" valign="top" class="summary"> |
|
631 <span class="summary-type"> </span> |
|
632 </td><td class="summary"> |
|
633 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
634 <tr> |
|
635 <td><span class="summary-sig"><a href="graph.graph-class.html#read" class="summary-sig-name">read</a>(<span class="summary-sig-arg">self</span>, |
|
636 <span class="summary-sig-arg">string</span>, |
|
637 <span class="summary-sig-arg">fmt</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span><br /> |
|
638 Read a graph from a string.</td> |
|
639 <td align="right" valign="top"> |
|
640 |
|
641 |
|
642 </td> |
|
643 </tr> |
|
644 </table> |
|
645 |
|
646 </td> |
|
647 </tr> |
|
648 <tr> |
|
649 <td width="15%" align="right" valign="top" class="summary"> |
|
650 <span class="summary-type">string</span> |
|
651 </td><td class="summary"> |
|
652 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
653 <tr> |
|
654 <td><span class="summary-sig"><a href="graph.graph-class.html#write" class="summary-sig-name">write</a>(<span class="summary-sig-arg">self</span>, |
|
655 <span class="summary-sig-arg">fmt</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span><br /> |
|
656 Write the graph to a string.</td> |
|
657 <td align="right" valign="top"> |
|
658 |
|
659 |
|
660 </td> |
|
661 </tr> |
|
662 </table> |
|
663 |
|
664 </td> |
|
665 </tr> |
|
666 <tr> |
|
667 <td width="15%" align="right" valign="top" class="summary"> |
|
668 <span class="summary-type">dictionary</span> |
|
669 </td><td class="summary"> |
|
670 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
671 <tr> |
|
672 <td><span class="summary-sig"><a href="graph.graph-class.html#accessibility" class="summary-sig-name">accessibility</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
673 Accessibility matrix (transitive closure).</td> |
|
674 <td align="right" valign="top"> |
|
675 |
|
676 |
|
677 </td> |
|
678 </tr> |
|
679 </table> |
|
680 |
|
681 </td> |
|
682 </tr> |
|
683 <tr> |
|
684 <td width="15%" align="right" valign="top" class="summary"> |
|
685 <span class="summary-type">dictionary</span> |
|
686 </td><td class="summary"> |
|
687 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
688 <tr> |
|
689 <td><span class="summary-sig"><a href="graph.graph-class.html#breadth_first_search" class="summary-sig-name">breadth_first_search</a>(<span class="summary-sig-arg">self</span>, |
|
690 <span class="summary-sig-arg">root</span>=<span class="summary-sig-default">None</span>)</span><br /> |
|
691 Breadth-first search.</td> |
|
692 <td align="right" valign="top"> |
|
693 |
|
694 |
|
695 </td> |
|
696 </tr> |
|
697 </table> |
|
698 |
|
699 </td> |
|
700 </tr> |
|
701 <tr> |
|
702 <td width="15%" align="right" valign="top" class="summary"> |
|
703 <span class="summary-type">dictionary</span> |
|
704 </td><td class="summary"> |
|
705 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
706 <tr> |
|
707 <td><span class="summary-sig"><a href="graph.graph-class.html#connected_components" class="summary-sig-name">connected_components</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
708 Connected components.</td> |
|
709 <td align="right" valign="top"> |
|
710 |
|
711 |
|
712 </td> |
|
713 </tr> |
|
714 </table> |
|
715 |
|
716 </td> |
|
717 </tr> |
|
718 <tr> |
|
719 <td width="15%" align="right" valign="top" class="summary"> |
|
720 <span class="summary-type">list</span> |
|
721 </td><td class="summary"> |
|
722 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
723 <tr> |
|
724 <td><span class="summary-sig"><a href="graph.graph-class.html#cut_edges" class="summary-sig-name">cut_edges</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
725 Return the cut-edges of the given graph.</td> |
|
726 <td align="right" valign="top"> |
|
727 |
|
728 |
|
729 </td> |
|
730 </tr> |
|
731 </table> |
|
732 |
|
733 </td> |
|
734 </tr> |
|
735 <tr> |
|
736 <td width="15%" align="right" valign="top" class="summary"> |
|
737 <span class="summary-type">list</span> |
|
738 </td><td class="summary"> |
|
739 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
740 <tr> |
|
741 <td><span class="summary-sig"><a href="graph.graph-class.html#cut_nodes" class="summary-sig-name">cut_nodes</a>(<span class="summary-sig-arg">self</span>)</span><br /> |
|
742 Return the cut-nodes of the given graph.</td> |
|
743 <td align="right" valign="top"> |
|
744 |
|
745 |
|
746 </td> |
|
747 </tr> |
|
748 </table> |
|
749 |
|
750 </td> |
|
751 </tr> |
|
752 <tr> |
|
753 <td width="15%" align="right" valign="top" class="summary"> |
|
754 <span class="summary-type">tuple</span> |
|
755 </td><td class="summary"> |
|
756 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
757 <tr> |
|
758 <td><span class="summary-sig"><a href="graph.graph-class.html#depth_first_search" class="summary-sig-name">depth_first_search</a>(<span class="summary-sig-arg">self</span>, |
|
759 <span class="summary-sig-arg">root</span>=<span class="summary-sig-default">None</span>)</span><br /> |
|
760 Depht-first search.</td> |
|
761 <td align="right" valign="top"> |
|
762 |
|
763 |
|
764 </td> |
|
765 </tr> |
|
766 </table> |
|
767 |
|
768 </td> |
|
769 </tr> |
|
770 <tr> |
|
771 <td width="15%" align="right" valign="top" class="summary"> |
|
772 <span class="summary-type">list</span> |
|
773 </td><td class="summary"> |
|
774 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
775 <tr> |
|
776 <td><span class="summary-sig"><a href="graph.graph-class.html#minimal_spanning_tree" class="summary-sig-name">minimal_spanning_tree</a>(<span class="summary-sig-arg">self</span>, |
|
777 <span class="summary-sig-arg">root</span>=<span class="summary-sig-default">None</span>)</span><br /> |
|
778 Minimal spanning tree.</td> |
|
779 <td align="right" valign="top"> |
|
780 |
|
781 |
|
782 </td> |
|
783 </tr> |
|
784 </table> |
|
785 |
|
786 </td> |
|
787 </tr> |
|
788 <tr> |
|
789 <td width="15%" align="right" valign="top" class="summary"> |
|
790 <span class="summary-type">tuple</span> |
|
791 </td><td class="summary"> |
|
792 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
793 <tr> |
|
794 <td><span class="summary-sig"><a href="graph.graph-class.html#shortest_path" class="summary-sig-name">shortest_path</a>(<span class="summary-sig-arg">self</span>, |
|
795 <span class="summary-sig-arg">source</span>)</span><br /> |
|
796 Return the shortest path distance between source node and all other |
|
797 nodes using Dijkstra's algorithm.</td> |
|
798 <td align="right" valign="top"> |
|
799 |
|
800 |
|
801 </td> |
|
802 </tr> |
|
803 </table> |
|
804 |
|
805 </td> |
|
806 </tr> |
|
807 <tr> |
|
808 <td colspan="2" class="summary"> |
|
809 <p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>: |
|
810 <code>__delattr__</code>, |
|
811 <code>__getattribute__</code>, |
|
812 <code>__hash__</code>, |
|
813 <code>__new__</code>, |
|
814 <code>__reduce__</code>, |
|
815 <code>__reduce_ex__</code>, |
|
816 <code>__repr__</code>, |
|
817 <code>__setattr__</code> |
|
818 </p> |
|
819 </td> |
|
820 </tr> |
|
821 </table> |
|
822 <!-- ==================== PROPERTIES ==================== --> |
|
823 <a name="section-Properties"></a> |
|
824 <table class="summary" border="1" cellpadding="3" |
|
825 cellspacing="0" width="100%" bgcolor="white"> |
|
826 <tr bgcolor="#70b0f0" class="table-header"> |
|
827 <td align="left" colspan="2" class="table-header"> |
|
828 <span class="table-header">Properties</span></td> |
|
829 </tr> |
|
830 <tr> |
|
831 <td colspan="2" class="summary"> |
|
832 <p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>: |
|
833 <code>__class__</code> |
|
834 </p> |
|
835 </td> |
|
836 </tr> |
|
837 </table> |
|
838 <!-- ==================== METHOD DETAILS ==================== --> |
|
839 <a name="section-MethodDetails"></a> |
|
840 <table class="details" border="1" cellpadding="3" |
|
841 cellspacing="0" width="100%" bgcolor="white"> |
|
842 <tr bgcolor="#70b0f0" class="table-header"> |
|
843 <td align="left" colspan="2" class="table-header"> |
|
844 <span class="table-header">Method Details</span></td> |
|
845 </tr> |
|
846 </table> |
|
847 <a name="__init__"></a> |
|
848 <div> |
|
849 <table class="details" border="1" cellpadding="3" |
|
850 cellspacing="0" width="100%" bgcolor="white"> |
|
851 <tr><td> |
|
852 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
853 <tr valign="top"><td> |
|
854 <h3 class="epydoc"><span class="sig"><span class="sig-name">__init__</span>(<span class="sig-arg">self</span>)</span> |
|
855 <br /><em class="fname">(Constructor)</em> |
|
856 </h3> |
|
857 </td><td align="right" valign="top" |
|
858 > |
|
859 </td> |
|
860 </tr></table> |
|
861 |
|
862 <p>Initialize a graph.</p> |
|
863 <dl class="fields"> |
|
864 <dt>Overrides: |
|
865 object.__init__ |
|
866 </dt> |
|
867 </dl> |
|
868 </td></tr></table> |
|
869 </div> |
|
870 <a name="__getitem__"></a> |
|
871 <div> |
|
872 <table class="details" border="1" cellpadding="3" |
|
873 cellspacing="0" width="100%" bgcolor="white"> |
|
874 <tr><td> |
|
875 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
876 <tr valign="top"><td> |
|
877 <h3 class="epydoc"><span class="sig"><span class="sig-name">__getitem__</span>(<span class="sig-arg">self</span>, |
|
878 <span class="sig-arg">node</span>)</span> |
|
879 <br /><em class="fname">(Indexing operator)</em> |
|
880 </h3> |
|
881 </td><td align="right" valign="top" |
|
882 > |
|
883 </td> |
|
884 </tr></table> |
|
885 |
|
886 <p>Return a iterator passing through all neighbors of the given node.</p> |
|
887 <dl class="fields"> |
|
888 <dt>Returns: iterator</dt> |
|
889 <dd>Iterator passing through all neighbors of the given node.</dd> |
|
890 </dl> |
|
891 </td></tr></table> |
|
892 </div> |
|
893 <a name="__iter__"></a> |
|
894 <div> |
|
895 <table class="details" border="1" cellpadding="3" |
|
896 cellspacing="0" width="100%" bgcolor="white"> |
|
897 <tr><td> |
|
898 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
899 <tr valign="top"><td> |
|
900 <h3 class="epydoc"><span class="sig"><span class="sig-name">__iter__</span>(<span class="sig-arg">self</span>)</span> |
|
901 </h3> |
|
902 </td><td align="right" valign="top" |
|
903 > |
|
904 </td> |
|
905 </tr></table> |
|
906 |
|
907 <p>Return a iterator passing through all nodes in the graph.</p> |
|
908 <dl class="fields"> |
|
909 <dt>Returns: iterator</dt> |
|
910 <dd>Iterator passing through all nodes in the graph.</dd> |
|
911 </dl> |
|
912 </td></tr></table> |
|
913 </div> |
|
914 <a name="__len__"></a> |
|
915 <div> |
|
916 <table class="details" border="1" cellpadding="3" |
|
917 cellspacing="0" width="100%" bgcolor="white"> |
|
918 <tr><td> |
|
919 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
920 <tr valign="top"><td> |
|
921 <h3 class="epydoc"><span class="sig"><span class="sig-name">__len__</span>(<span class="sig-arg">self</span>)</span> |
|
922 <br /><em class="fname">(Length operator)</em> |
|
923 </h3> |
|
924 </td><td align="right" valign="top" |
|
925 > |
|
926 </td> |
|
927 </tr></table> |
|
928 |
|
929 <p>Return the order of the graph when requested by len().</p> |
|
930 <dl class="fields"> |
|
931 <dt>Returns: number</dt> |
|
932 <dd>Size of the graph.</dd> |
|
933 </dl> |
|
934 </td></tr></table> |
|
935 </div> |
|
936 <a name="__str__"></a> |
|
937 <div> |
|
938 <table class="details" border="1" cellpadding="3" |
|
939 cellspacing="0" width="100%" bgcolor="white"> |
|
940 <tr><td> |
|
941 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
942 <tr valign="top"><td> |
|
943 <h3 class="epydoc"><span class="sig"><span class="sig-name">__str__</span>(<span class="sig-arg">self</span>)</span> |
|
944 <br /><em class="fname">(Informal representation operator)</em> |
|
945 </h3> |
|
946 </td><td align="right" valign="top" |
|
947 > |
|
948 </td> |
|
949 </tr></table> |
|
950 |
|
951 <p>Return a string representing the graph when requested by str() (or |
|
952 print).</p> |
|
953 <dl class="fields"> |
|
954 <dt>Returns: string</dt> |
|
955 <dd>String representing the graph.</dd> |
|
956 <dt>Overrides: |
|
957 object.__str__ |
|
958 </dt> |
|
959 </dl> |
|
960 </td></tr></table> |
|
961 </div> |
|
962 <a name="add_edge"></a> |
|
963 <div> |
|
964 <table class="details" border="1" cellpadding="3" |
|
965 cellspacing="0" width="100%" bgcolor="white"> |
|
966 <tr><td> |
|
967 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
968 <tr valign="top"><td> |
|
969 <h3 class="epydoc"><span class="sig"><span class="sig-name">add_edge</span>(<span class="sig-arg">self</span>, |
|
970 <span class="sig-arg">u</span>, |
|
971 <span class="sig-arg">v</span>, |
|
972 <span class="sig-arg">wt</span>=<span class="sig-default">1</span>, |
|
973 <span class="sig-arg">label</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string"></code><code class="variable-quote">'</code></span>, |
|
974 <span class="sig-arg">attrs</span>=<span class="sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span> |
|
975 </h3> |
|
976 </td><td align="right" valign="top" |
|
977 > |
|
978 </td> |
|
979 </tr></table> |
|
980 |
|
981 <p>Add an edge (u,v) to the graph connecting nodes u and v.</p> |
|
982 <dl class="fields"> |
|
983 <dt>Parameters:</dt> |
|
984 <dd><ul class="nomargin-top"> |
|
985 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
986 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
987 <li><strong class="pname"><code>wt</code></strong> (number) - Edge weight.</li> |
|
988 <li><strong class="pname"><code>label</code></strong> (string) - Edge label.</li> |
|
989 <li><strong class="pname"><code>attrs</code></strong> (list) - List of node attributes specified as (attribute, value) tuples.</li> |
|
990 </ul></dd> |
|
991 </dl> |
|
992 </td></tr></table> |
|
993 </div> |
|
994 <a name="add_edge_attribute"></a> |
|
995 <div> |
|
996 <table class="details" border="1" cellpadding="3" |
|
997 cellspacing="0" width="100%" bgcolor="white"> |
|
998 <tr><td> |
|
999 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1000 <tr valign="top"><td> |
|
1001 <h3 class="epydoc"><span class="sig"><span class="sig-name">add_edge_attribute</span>(<span class="sig-arg">self</span>, |
|
1002 <span class="sig-arg">u</span>, |
|
1003 <span class="sig-arg">v</span>, |
|
1004 <span class="sig-arg">attr</span>)</span> |
|
1005 </h3> |
|
1006 </td><td align="right" valign="top" |
|
1007 > |
|
1008 </td> |
|
1009 </tr></table> |
|
1010 |
|
1011 <p>Add attribute to the given edge.</p> |
|
1012 <dl class="fields"> |
|
1013 <dt>Parameters:</dt> |
|
1014 <dd><ul class="nomargin-top"> |
|
1015 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1016 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1017 <li><strong class="pname"><code>attr</code></strong> (tuple) - Node attribute specified as a tuple in the form (attribute, |
|
1018 value).</li> |
|
1019 </ul></dd> |
|
1020 </dl> |
|
1021 </td></tr></table> |
|
1022 </div> |
|
1023 <a name="add_graph"></a> |
|
1024 <div> |
|
1025 <table class="details" border="1" cellpadding="3" |
|
1026 cellspacing="0" width="100%" bgcolor="white"> |
|
1027 <tr><td> |
|
1028 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1029 <tr valign="top"><td> |
|
1030 <h3 class="epydoc"><span class="sig"><span class="sig-name">add_graph</span>(<span class="sig-arg">self</span>, |
|
1031 <span class="sig-arg">graph</span>)</span> |
|
1032 </h3> |
|
1033 </td><td align="right" valign="top" |
|
1034 > |
|
1035 </td> |
|
1036 </tr></table> |
|
1037 |
|
1038 <p>Add other graph to the graph.</p> |
|
1039 <dl class="fields"> |
|
1040 <dt>Parameters:</dt> |
|
1041 <dd><ul class="nomargin-top"> |
|
1042 <li><strong class="pname"><code>graph</code></strong> (graph) - Graph</li> |
|
1043 </ul></dd> |
|
1044 </dl> |
|
1045 <div class="fields"> <p><strong>Attention:</strong> |
|
1046 Attributes and labels are not preserved. |
|
1047 </p> |
|
1048 </div></td></tr></table> |
|
1049 </div> |
|
1050 <a name="add_node"></a> |
|
1051 <div> |
|
1052 <table class="details" border="1" cellpadding="3" |
|
1053 cellspacing="0" width="100%" bgcolor="white"> |
|
1054 <tr><td> |
|
1055 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1056 <tr valign="top"><td> |
|
1057 <h3 class="epydoc"><span class="sig"><span class="sig-name">add_node</span>(<span class="sig-arg">self</span>, |
|
1058 <span class="sig-arg">node</span>, |
|
1059 <span class="sig-arg">attrs</span>=<span class="sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span> |
|
1060 </h3> |
|
1061 </td><td align="right" valign="top" |
|
1062 > |
|
1063 </td> |
|
1064 </tr></table> |
|
1065 |
|
1066 <p>Add given node to the graph.</p> |
|
1067 <dl class="fields"> |
|
1068 <dt>Parameters:</dt> |
|
1069 <dd><ul class="nomargin-top"> |
|
1070 <li><strong class="pname"><code>node</code></strong> (node) - Node identifier.</li> |
|
1071 <li><strong class="pname"><code>attrs</code></strong> (list) - List of node attributes specified as (attribute, value) tuples.</li> |
|
1072 </ul></dd> |
|
1073 </dl> |
|
1074 <div class="fields"> <p><strong>Attention:</strong> |
|
1075 While nodes can be of any type, it's strongly recommended to use |
|
1076 only numbers and single-line strings as node identifiers if you |
|
1077 intend to use write(). |
|
1078 </p> |
|
1079 </div></td></tr></table> |
|
1080 </div> |
|
1081 <a name="add_node_attribute"></a> |
|
1082 <div> |
|
1083 <table class="details" border="1" cellpadding="3" |
|
1084 cellspacing="0" width="100%" bgcolor="white"> |
|
1085 <tr><td> |
|
1086 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1087 <tr valign="top"><td> |
|
1088 <h3 class="epydoc"><span class="sig"><span class="sig-name">add_node_attribute</span>(<span class="sig-arg">self</span>, |
|
1089 <span class="sig-arg">node</span>, |
|
1090 <span class="sig-arg">attr</span>)</span> |
|
1091 </h3> |
|
1092 </td><td align="right" valign="top" |
|
1093 > |
|
1094 </td> |
|
1095 </tr></table> |
|
1096 |
|
1097 <p>Add attribute to the given node.</p> |
|
1098 <dl class="fields"> |
|
1099 <dt>Parameters:</dt> |
|
1100 <dd><ul class="nomargin-top"> |
|
1101 <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li> |
|
1102 <li><strong class="pname"><code>attr</code></strong> (tuple) - Node attribute specified as a tuple in the form (attribute, |
|
1103 value).</li> |
|
1104 </ul></dd> |
|
1105 </dl> |
|
1106 </td></tr></table> |
|
1107 </div> |
|
1108 <a name="add_nodes"></a> |
|
1109 <div> |
|
1110 <table class="details" border="1" cellpadding="3" |
|
1111 cellspacing="0" width="100%" bgcolor="white"> |
|
1112 <tr><td> |
|
1113 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1114 <tr valign="top"><td> |
|
1115 <h3 class="epydoc"><span class="sig"><span class="sig-name">add_nodes</span>(<span class="sig-arg">self</span>, |
|
1116 <span class="sig-arg">nodelist</span>)</span> |
|
1117 </h3> |
|
1118 </td><td align="right" valign="top" |
|
1119 > |
|
1120 </td> |
|
1121 </tr></table> |
|
1122 |
|
1123 <p>Add given nodes to the graph.</p> |
|
1124 <dl class="fields"> |
|
1125 <dt>Parameters:</dt> |
|
1126 <dd><ul class="nomargin-top"> |
|
1127 <li><strong class="pname"><code>nodelist</code></strong> (list) - List of nodes to be added to the graph.</li> |
|
1128 </ul></dd> |
|
1129 </dl> |
|
1130 <div class="fields"> <p><strong>Attention:</strong> |
|
1131 While nodes can be of any type, it's strongly recommended to use |
|
1132 only numbers and single-line strings as node identifiers if you |
|
1133 intend to use write(). |
|
1134 </p> |
|
1135 </div></td></tr></table> |
|
1136 </div> |
|
1137 <a name="add_spanning_tree"></a> |
|
1138 <div> |
|
1139 <table class="details" border="1" cellpadding="3" |
|
1140 cellspacing="0" width="100%" bgcolor="white"> |
|
1141 <tr><td> |
|
1142 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1143 <tr valign="top"><td> |
|
1144 <h3 class="epydoc"><span class="sig"><span class="sig-name">add_spanning_tree</span>(<span class="sig-arg">self</span>, |
|
1145 <span class="sig-arg">st</span>)</span> |
|
1146 </h3> |
|
1147 </td><td align="right" valign="top" |
|
1148 > |
|
1149 </td> |
|
1150 </tr></table> |
|
1151 |
|
1152 <p>Add a spanning tree to the graph.</p> |
|
1153 <dl class="fields"> |
|
1154 <dt>Parameters:</dt> |
|
1155 <dd><ul class="nomargin-top"> |
|
1156 <li><strong class="pname"><code>st</code></strong> (dictionary) - Spanning tree.</li> |
|
1157 </ul></dd> |
|
1158 </dl> |
|
1159 </td></tr></table> |
|
1160 </div> |
|
1161 <a name="complete"></a> |
|
1162 <div> |
|
1163 <table class="details" border="1" cellpadding="3" |
|
1164 cellspacing="0" width="100%" bgcolor="white"> |
|
1165 <tr><td> |
|
1166 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1167 <tr valign="top"><td> |
|
1168 <h3 class="epydoc"><span class="sig"><span class="sig-name">complete</span>(<span class="sig-arg">self</span>)</span> |
|
1169 </h3> |
|
1170 </td><td align="right" valign="top" |
|
1171 > |
|
1172 </td> |
|
1173 </tr></table> |
|
1174 |
|
1175 <p>Make the graph a complete graph.</p> |
|
1176 <dl class="fields"> |
|
1177 </dl> |
|
1178 <div class="fields"> <p><strong>Attention:</strong> |
|
1179 This will modify the current graph. |
|
1180 </p> |
|
1181 </div></td></tr></table> |
|
1182 </div> |
|
1183 <a name="del_edge"></a> |
|
1184 <div> |
|
1185 <table class="details" border="1" cellpadding="3" |
|
1186 cellspacing="0" width="100%" bgcolor="white"> |
|
1187 <tr><td> |
|
1188 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1189 <tr valign="top"><td> |
|
1190 <h3 class="epydoc"><span class="sig"><span class="sig-name">del_edge</span>(<span class="sig-arg">self</span>, |
|
1191 <span class="sig-arg">u</span>, |
|
1192 <span class="sig-arg">v</span>)</span> |
|
1193 </h3> |
|
1194 </td><td align="right" valign="top" |
|
1195 > |
|
1196 </td> |
|
1197 </tr></table> |
|
1198 |
|
1199 <p>Remove an edge (u, v) from the graph.</p> |
|
1200 <dl class="fields"> |
|
1201 <dt>Parameters:</dt> |
|
1202 <dd><ul class="nomargin-top"> |
|
1203 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1204 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1205 </ul></dd> |
|
1206 </dl> |
|
1207 </td></tr></table> |
|
1208 </div> |
|
1209 <a name="del_node"></a> |
|
1210 <div> |
|
1211 <table class="details" border="1" cellpadding="3" |
|
1212 cellspacing="0" width="100%" bgcolor="white"> |
|
1213 <tr><td> |
|
1214 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1215 <tr valign="top"><td> |
|
1216 <h3 class="epydoc"><span class="sig"><span class="sig-name">del_node</span>(<span class="sig-arg">self</span>, |
|
1217 <span class="sig-arg">node</span>)</span> |
|
1218 </h3> |
|
1219 </td><td align="right" valign="top" |
|
1220 > |
|
1221 </td> |
|
1222 </tr></table> |
|
1223 |
|
1224 <p>Remove a node from the graph.</p> |
|
1225 <dl class="fields"> |
|
1226 <dt>Parameters:</dt> |
|
1227 <dd><ul class="nomargin-top"> |
|
1228 <li><strong class="pname"><code>node</code></strong> (node) - Node identifier.</li> |
|
1229 </ul></dd> |
|
1230 </dl> |
|
1231 </td></tr></table> |
|
1232 </div> |
|
1233 <a name="edges"></a> |
|
1234 <div> |
|
1235 <table class="details" border="1" cellpadding="3" |
|
1236 cellspacing="0" width="100%" bgcolor="white"> |
|
1237 <tr><td> |
|
1238 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1239 <tr valign="top"><td> |
|
1240 <h3 class="epydoc"><span class="sig"><span class="sig-name">edges</span>(<span class="sig-arg">self</span>)</span> |
|
1241 </h3> |
|
1242 </td><td align="right" valign="top" |
|
1243 > |
|
1244 </td> |
|
1245 </tr></table> |
|
1246 |
|
1247 <p>Return all edges in the graph.</p> |
|
1248 <dl class="fields"> |
|
1249 <dt>Returns: list</dt> |
|
1250 <dd>List of all edges in the graph.</dd> |
|
1251 </dl> |
|
1252 </td></tr></table> |
|
1253 </div> |
|
1254 <a name="get_edge_attributes"></a> |
|
1255 <div> |
|
1256 <table class="details" border="1" cellpadding="3" |
|
1257 cellspacing="0" width="100%" bgcolor="white"> |
|
1258 <tr><td> |
|
1259 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1260 <tr valign="top"><td> |
|
1261 <h3 class="epydoc"><span class="sig"><span class="sig-name">get_edge_attributes</span>(<span class="sig-arg">self</span>, |
|
1262 <span class="sig-arg">u</span>, |
|
1263 <span class="sig-arg">v</span>)</span> |
|
1264 </h3> |
|
1265 </td><td align="right" valign="top" |
|
1266 > |
|
1267 </td> |
|
1268 </tr></table> |
|
1269 |
|
1270 <p>Return the attributes of the given edge.</p> |
|
1271 <dl class="fields"> |
|
1272 <dt>Parameters:</dt> |
|
1273 <dd><ul class="nomargin-top"> |
|
1274 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1275 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1276 </ul></dd> |
|
1277 <dt>Returns: list</dt> |
|
1278 <dd>List of attributes specified tuples in the form (attribute, |
|
1279 value).</dd> |
|
1280 </dl> |
|
1281 </td></tr></table> |
|
1282 </div> |
|
1283 <a name="get_edge_label"></a> |
|
1284 <div> |
|
1285 <table class="details" border="1" cellpadding="3" |
|
1286 cellspacing="0" width="100%" bgcolor="white"> |
|
1287 <tr><td> |
|
1288 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1289 <tr valign="top"><td> |
|
1290 <h3 class="epydoc"><span class="sig"><span class="sig-name">get_edge_label</span>(<span class="sig-arg">self</span>, |
|
1291 <span class="sig-arg">u</span>, |
|
1292 <span class="sig-arg">v</span>)</span> |
|
1293 </h3> |
|
1294 </td><td align="right" valign="top" |
|
1295 > |
|
1296 </td> |
|
1297 </tr></table> |
|
1298 |
|
1299 <p>Get the label of an edge.</p> |
|
1300 <dl class="fields"> |
|
1301 <dt>Parameters:</dt> |
|
1302 <dd><ul class="nomargin-top"> |
|
1303 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1304 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1305 </ul></dd> |
|
1306 <dt>Returns: string</dt> |
|
1307 <dd>Edge label</dd> |
|
1308 </dl> |
|
1309 </td></tr></table> |
|
1310 </div> |
|
1311 <a name="get_edge_weight"></a> |
|
1312 <div> |
|
1313 <table class="details" border="1" cellpadding="3" |
|
1314 cellspacing="0" width="100%" bgcolor="white"> |
|
1315 <tr><td> |
|
1316 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1317 <tr valign="top"><td> |
|
1318 <h3 class="epydoc"><span class="sig"><span class="sig-name">get_edge_weight</span>(<span class="sig-arg">self</span>, |
|
1319 <span class="sig-arg">u</span>, |
|
1320 <span class="sig-arg">v</span>)</span> |
|
1321 </h3> |
|
1322 </td><td align="right" valign="top" |
|
1323 > |
|
1324 </td> |
|
1325 </tr></table> |
|
1326 |
|
1327 <p>Get the weight of an edge.</p> |
|
1328 <dl class="fields"> |
|
1329 <dt>Parameters:</dt> |
|
1330 <dd><ul class="nomargin-top"> |
|
1331 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1332 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1333 </ul></dd> |
|
1334 <dt>Returns: number</dt> |
|
1335 <dd>Edge weight.</dd> |
|
1336 </dl> |
|
1337 </td></tr></table> |
|
1338 </div> |
|
1339 <a name="get_node_attributes"></a> |
|
1340 <div> |
|
1341 <table class="details" border="1" cellpadding="3" |
|
1342 cellspacing="0" width="100%" bgcolor="white"> |
|
1343 <tr><td> |
|
1344 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1345 <tr valign="top"><td> |
|
1346 <h3 class="epydoc"><span class="sig"><span class="sig-name">get_node_attributes</span>(<span class="sig-arg">self</span>, |
|
1347 <span class="sig-arg">node</span>)</span> |
|
1348 </h3> |
|
1349 </td><td align="right" valign="top" |
|
1350 > |
|
1351 </td> |
|
1352 </tr></table> |
|
1353 |
|
1354 <p>Return the attributes of the given node.</p> |
|
1355 <dl class="fields"> |
|
1356 <dt>Parameters:</dt> |
|
1357 <dd><ul class="nomargin-top"> |
|
1358 <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li> |
|
1359 </ul></dd> |
|
1360 <dt>Returns: list</dt> |
|
1361 <dd>List of attributes specified tuples in the form (attribute, |
|
1362 value).</dd> |
|
1363 </dl> |
|
1364 </td></tr></table> |
|
1365 </div> |
|
1366 <a name="has_edge"></a> |
|
1367 <div> |
|
1368 <table class="details" border="1" cellpadding="3" |
|
1369 cellspacing="0" width="100%" bgcolor="white"> |
|
1370 <tr><td> |
|
1371 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1372 <tr valign="top"><td> |
|
1373 <h3 class="epydoc"><span class="sig"><span class="sig-name">has_edge</span>(<span class="sig-arg">self</span>, |
|
1374 <span class="sig-arg">u</span>, |
|
1375 <span class="sig-arg">v</span>)</span> |
|
1376 </h3> |
|
1377 </td><td align="right" valign="top" |
|
1378 > |
|
1379 </td> |
|
1380 </tr></table> |
|
1381 |
|
1382 <p>Return whether an edge between nodes u and v exists.</p> |
|
1383 <dl class="fields"> |
|
1384 <dt>Parameters:</dt> |
|
1385 <dd><ul class="nomargin-top"> |
|
1386 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1387 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1388 </ul></dd> |
|
1389 <dt>Returns: boolean</dt> |
|
1390 <dd>Truth-value for edge existence.</dd> |
|
1391 </dl> |
|
1392 </td></tr></table> |
|
1393 </div> |
|
1394 <a name="has_node"></a> |
|
1395 <div> |
|
1396 <table class="details" border="1" cellpadding="3" |
|
1397 cellspacing="0" width="100%" bgcolor="white"> |
|
1398 <tr><td> |
|
1399 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1400 <tr valign="top"><td> |
|
1401 <h3 class="epydoc"><span class="sig"><span class="sig-name">has_node</span>(<span class="sig-arg">self</span>, |
|
1402 <span class="sig-arg">node</span>)</span> |
|
1403 </h3> |
|
1404 </td><td align="right" valign="top" |
|
1405 > |
|
1406 </td> |
|
1407 </tr></table> |
|
1408 |
|
1409 <p>Return whether the requested node exists.</p> |
|
1410 <dl class="fields"> |
|
1411 <dt>Parameters:</dt> |
|
1412 <dd><ul class="nomargin-top"> |
|
1413 <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li> |
|
1414 </ul></dd> |
|
1415 <dt>Returns: boolean</dt> |
|
1416 <dd>Truth-value for node existence.</dd> |
|
1417 </dl> |
|
1418 </td></tr></table> |
|
1419 </div> |
|
1420 <a name="inverse"></a> |
|
1421 <div> |
|
1422 <table class="details" border="1" cellpadding="3" |
|
1423 cellspacing="0" width="100%" bgcolor="white"> |
|
1424 <tr><td> |
|
1425 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1426 <tr valign="top"><td> |
|
1427 <h3 class="epydoc"><span class="sig"><span class="sig-name">inverse</span>(<span class="sig-arg">self</span>)</span> |
|
1428 </h3> |
|
1429 </td><td align="right" valign="top" |
|
1430 > |
|
1431 </td> |
|
1432 </tr></table> |
|
1433 |
|
1434 <p>Return the inverse of the graph.</p> |
|
1435 <dl class="fields"> |
|
1436 <dt>Returns: graph</dt> |
|
1437 <dd>Complement graph for the graph.</dd> |
|
1438 </dl> |
|
1439 </td></tr></table> |
|
1440 </div> |
|
1441 <a name="neighbors"></a> |
|
1442 <div> |
|
1443 <table class="details" border="1" cellpadding="3" |
|
1444 cellspacing="0" width="100%" bgcolor="white"> |
|
1445 <tr><td> |
|
1446 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1447 <tr valign="top"><td> |
|
1448 <h3 class="epydoc"><span class="sig"><span class="sig-name">neighbors</span>(<span class="sig-arg">self</span>, |
|
1449 <span class="sig-arg">node</span>)</span> |
|
1450 </h3> |
|
1451 </td><td align="right" valign="top" |
|
1452 > |
|
1453 </td> |
|
1454 </tr></table> |
|
1455 |
|
1456 <p>Return all nodes that are directly accessible from given node.</p> |
|
1457 <dl class="fields"> |
|
1458 <dt>Parameters:</dt> |
|
1459 <dd><ul class="nomargin-top"> |
|
1460 <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li> |
|
1461 </ul></dd> |
|
1462 <dt>Returns: list</dt> |
|
1463 <dd>List of nodes directly accessible from given node.</dd> |
|
1464 </dl> |
|
1465 </td></tr></table> |
|
1466 </div> |
|
1467 <a name="nodes"></a> |
|
1468 <div> |
|
1469 <table class="details" border="1" cellpadding="3" |
|
1470 cellspacing="0" width="100%" bgcolor="white"> |
|
1471 <tr><td> |
|
1472 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1473 <tr valign="top"><td> |
|
1474 <h3 class="epydoc"><span class="sig"><span class="sig-name">nodes</span>(<span class="sig-arg">self</span>)</span> |
|
1475 </h3> |
|
1476 </td><td align="right" valign="top" |
|
1477 > |
|
1478 </td> |
|
1479 </tr></table> |
|
1480 |
|
1481 <p>Return node list.</p> |
|
1482 <dl class="fields"> |
|
1483 <dt>Returns: list</dt> |
|
1484 <dd>Node list.</dd> |
|
1485 </dl> |
|
1486 </td></tr></table> |
|
1487 </div> |
|
1488 <a name="order"></a> |
|
1489 <div> |
|
1490 <table class="details" border="1" cellpadding="3" |
|
1491 cellspacing="0" width="100%" bgcolor="white"> |
|
1492 <tr><td> |
|
1493 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1494 <tr valign="top"><td> |
|
1495 <h3 class="epydoc"><span class="sig"><span class="sig-name">order</span>(<span class="sig-arg">self</span>, |
|
1496 <span class="sig-arg">node</span>)</span> |
|
1497 </h3> |
|
1498 </td><td align="right" valign="top" |
|
1499 > |
|
1500 </td> |
|
1501 </tr></table> |
|
1502 |
|
1503 <p>Return the order of the given node.</p> |
|
1504 <dl class="fields"> |
|
1505 <dt>Returns: number</dt> |
|
1506 <dd>Order of the given node.</dd> |
|
1507 </dl> |
|
1508 </td></tr></table> |
|
1509 </div> |
|
1510 <a name="set_edge_label"></a> |
|
1511 <div> |
|
1512 <table class="details" border="1" cellpadding="3" |
|
1513 cellspacing="0" width="100%" bgcolor="white"> |
|
1514 <tr><td> |
|
1515 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1516 <tr valign="top"><td> |
|
1517 <h3 class="epydoc"><span class="sig"><span class="sig-name">set_edge_label</span>(<span class="sig-arg">self</span>, |
|
1518 <span class="sig-arg">u</span>, |
|
1519 <span class="sig-arg">v</span>, |
|
1520 <span class="sig-arg">label</span>)</span> |
|
1521 </h3> |
|
1522 </td><td align="right" valign="top" |
|
1523 > |
|
1524 </td> |
|
1525 </tr></table> |
|
1526 |
|
1527 <p>Set the label of an edge.</p> |
|
1528 <dl class="fields"> |
|
1529 <dt>Parameters:</dt> |
|
1530 <dd><ul class="nomargin-top"> |
|
1531 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1532 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1533 <li><strong class="pname"><code>label</code></strong> (string) - Edge label.</li> |
|
1534 </ul></dd> |
|
1535 </dl> |
|
1536 </td></tr></table> |
|
1537 </div> |
|
1538 <a name="set_edge_weight"></a> |
|
1539 <div> |
|
1540 <table class="details" border="1" cellpadding="3" |
|
1541 cellspacing="0" width="100%" bgcolor="white"> |
|
1542 <tr><td> |
|
1543 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1544 <tr valign="top"><td> |
|
1545 <h3 class="epydoc"><span class="sig"><span class="sig-name">set_edge_weight</span>(<span class="sig-arg">self</span>, |
|
1546 <span class="sig-arg">u</span>, |
|
1547 <span class="sig-arg">v</span>, |
|
1548 <span class="sig-arg">wt</span>)</span> |
|
1549 </h3> |
|
1550 </td><td align="right" valign="top" |
|
1551 > |
|
1552 </td> |
|
1553 </tr></table> |
|
1554 |
|
1555 <p>Set the weight of an edge.</p> |
|
1556 <dl class="fields"> |
|
1557 <dt>Parameters:</dt> |
|
1558 <dd><ul class="nomargin-top"> |
|
1559 <li><strong class="pname"><code>u</code></strong> (node) - One node.</li> |
|
1560 <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li> |
|
1561 <li><strong class="pname"><code>wt</code></strong> (number) - Edge weight.</li> |
|
1562 </ul></dd> |
|
1563 </dl> |
|
1564 </td></tr></table> |
|
1565 </div> |
|
1566 <a name="traversal"></a> |
|
1567 <div> |
|
1568 <table class="details" border="1" cellpadding="3" |
|
1569 cellspacing="0" width="100%" bgcolor="white"> |
|
1570 <tr><td> |
|
1571 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1572 <tr valign="top"><td> |
|
1573 <h3 class="epydoc"><span class="sig"><span class="sig-name">traversal</span>(<span class="sig-arg">self</span>, |
|
1574 <span class="sig-arg">node</span>, |
|
1575 <span class="sig-arg">order</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string">pre</code><code class="variable-quote">'</code></span>)</span> |
|
1576 </h3> |
|
1577 </td><td align="right" valign="top" |
|
1578 > |
|
1579 </td> |
|
1580 </tr></table> |
|
1581 |
|
1582 <p>Graph traversal iterator.</p> |
|
1583 <dl class="fields"> |
|
1584 <dt>Parameters:</dt> |
|
1585 <dd><ul class="nomargin-top"> |
|
1586 <li><strong class="pname"><code>node</code></strong> (node) - Node.</li> |
|
1587 <li><strong class="pname"><code>order</code></strong> (string) - traversal ordering. Possible values are: |
|
1588 <ol start="2"> |
|
1589 <li> |
|
1590 'pre' - Preordering (default) |
|
1591 </li> |
|
1592 </ol> |
|
1593 <ol start="1"> |
|
1594 <li> |
|
1595 'post' - Postordering |
|
1596 </li> |
|
1597 </ol></li> |
|
1598 </ul></dd> |
|
1599 <dt>Returns: iterator</dt> |
|
1600 <dd>Traversal iterator.</dd> |
|
1601 </dl> |
|
1602 </td></tr></table> |
|
1603 </div> |
|
1604 <a name="generate"></a> |
|
1605 <div> |
|
1606 <table class="details" border="1" cellpadding="3" |
|
1607 cellspacing="0" width="100%" bgcolor="white"> |
|
1608 <tr><td> |
|
1609 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1610 <tr valign="top"><td> |
|
1611 <h3 class="epydoc"><span class="sig"><span class="sig-name">generate</span>(<span class="sig-arg">self</span>, |
|
1612 <span class="sig-arg">num_nodes</span>, |
|
1613 <span class="sig-arg">num_edges</span>, |
|
1614 <span class="sig-arg">weight_range</span>=<span class="sig-default"><code class="variable-group">(</code>1<code class="variable-op">, </code>1<code class="variable-group">)</code></span>)</span> |
|
1615 </h3> |
|
1616 </td><td align="right" valign="top" |
|
1617 > |
|
1618 </td> |
|
1619 </tr></table> |
|
1620 |
|
1621 <p>Add nodes and random edges to the graph.</p> |
|
1622 <dl class="fields"> |
|
1623 <dt>Parameters:</dt> |
|
1624 <dd><ul class="nomargin-top"> |
|
1625 <li><strong class="pname"><code>num_nodes</code></strong> (number) - Number of nodes.</li> |
|
1626 <li><strong class="pname"><code>num_edges</code></strong> (number) - Number of edges.</li> |
|
1627 <li><strong class="pname"><code>weight_range</code></strong> (tuple) - tuple of two integers as lower and upper limits on randomly |
|
1628 generated weights (uniform distribution).</li> |
|
1629 </ul></dd> |
|
1630 </dl> |
|
1631 </td></tr></table> |
|
1632 </div> |
|
1633 <a name="read"></a> |
|
1634 <div> |
|
1635 <table class="details" border="1" cellpadding="3" |
|
1636 cellspacing="0" width="100%" bgcolor="white"> |
|
1637 <tr><td> |
|
1638 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1639 <tr valign="top"><td> |
|
1640 <h3 class="epydoc"><span class="sig"><span class="sig-name">read</span>(<span class="sig-arg">self</span>, |
|
1641 <span class="sig-arg">string</span>, |
|
1642 <span class="sig-arg">fmt</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span> |
|
1643 </h3> |
|
1644 </td><td align="right" valign="top" |
|
1645 > |
|
1646 </td> |
|
1647 </tr></table> |
|
1648 |
|
1649 <p>Read a graph from a string. Nodes and edges specified in the input |
|
1650 will be added to the current graph.</p> |
|
1651 <dl class="fields"> |
|
1652 <dt>Parameters:</dt> |
|
1653 <dd><ul class="nomargin-top"> |
|
1654 <li><strong class="pname"><code>string</code></strong> (string) - Input string specifying a graph.</li> |
|
1655 <li><strong class="pname"><code>fmt</code></strong> (string) - Input format. Possible formats are: |
|
1656 <ol start="1"> |
|
1657 <li> |
|
1658 'xml' - XML (default) |
|
1659 </li> |
|
1660 </ol></li> |
|
1661 </ul></dd> |
|
1662 </dl> |
|
1663 </td></tr></table> |
|
1664 </div> |
|
1665 <a name="write"></a> |
|
1666 <div> |
|
1667 <table class="details" border="1" cellpadding="3" |
|
1668 cellspacing="0" width="100%" bgcolor="white"> |
|
1669 <tr><td> |
|
1670 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1671 <tr valign="top"><td> |
|
1672 <h3 class="epydoc"><span class="sig"><span class="sig-name">write</span>(<span class="sig-arg">self</span>, |
|
1673 <span class="sig-arg">fmt</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span> |
|
1674 </h3> |
|
1675 </td><td align="right" valign="top" |
|
1676 > |
|
1677 </td> |
|
1678 </tr></table> |
|
1679 |
|
1680 <p>Write the graph to a string. Depending of the output format, this |
|
1681 string can be used by read() to rebuild the graph.</p> |
|
1682 <dl class="fields"> |
|
1683 <dt>Parameters:</dt> |
|
1684 <dd><ul class="nomargin-top"> |
|
1685 <li><strong class="pname"><code>fmt</code></strong> (string) - Output format. Possible formats are: |
|
1686 <ol start="1"> |
|
1687 <li> |
|
1688 'xml' - XML (default) |
|
1689 </li> |
|
1690 <li> |
|
1691 'dot' - DOT Language (for GraphViz) |
|
1692 </li> |
|
1693 <li> |
|
1694 'dotwt' - DOT Language with weight information |
|
1695 </li> |
|
1696 </ol></li> |
|
1697 </ul></dd> |
|
1698 <dt>Returns: string</dt> |
|
1699 <dd>String specifying the graph.</dd> |
|
1700 </dl> |
|
1701 </td></tr></table> |
|
1702 </div> |
|
1703 <a name="accessibility"></a> |
|
1704 <div> |
|
1705 <table class="details" border="1" cellpadding="3" |
|
1706 cellspacing="0" width="100%" bgcolor="white"> |
|
1707 <tr><td> |
|
1708 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1709 <tr valign="top"><td> |
|
1710 <h3 class="epydoc"><span class="sig"><span class="sig-name">accessibility</span>(<span class="sig-arg">self</span>)</span> |
|
1711 </h3> |
|
1712 </td><td align="right" valign="top" |
|
1713 > |
|
1714 </td> |
|
1715 </tr></table> |
|
1716 |
|
1717 <p>Accessibility matrix (transitive closure).</p> |
|
1718 <dl class="fields"> |
|
1719 <dt>Returns: dictionary</dt> |
|
1720 <dd>Accessibility information for each node.</dd> |
|
1721 </dl> |
|
1722 </td></tr></table> |
|
1723 </div> |
|
1724 <a name="breadth_first_search"></a> |
|
1725 <div> |
|
1726 <table class="details" border="1" cellpadding="3" |
|
1727 cellspacing="0" width="100%" bgcolor="white"> |
|
1728 <tr><td> |
|
1729 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1730 <tr valign="top"><td> |
|
1731 <h3 class="epydoc"><span class="sig"><span class="sig-name">breadth_first_search</span>(<span class="sig-arg">self</span>, |
|
1732 <span class="sig-arg">root</span>=<span class="sig-default">None</span>)</span> |
|
1733 </h3> |
|
1734 </td><td align="right" valign="top" |
|
1735 > |
|
1736 </td> |
|
1737 </tr></table> |
|
1738 |
|
1739 <p>Breadth-first search.</p> |
|
1740 <dl class="fields"> |
|
1741 <dt>Parameters:</dt> |
|
1742 <dd><ul class="nomargin-top"> |
|
1743 <li><strong class="pname"><code>root</code></strong> (node) - Optional root node (will explore only root's connected component)</li> |
|
1744 </ul></dd> |
|
1745 <dt>Returns: dictionary</dt> |
|
1746 <dd>A tuple containing a dictionary and a list. |
|
1747 <ol start="1"> |
|
1748 <li> |
|
1749 Generated spanning tree |
|
1750 </li> |
|
1751 <li> |
|
1752 Graph's level-based ordering |
|
1753 </li> |
|
1754 </ol></dd> |
|
1755 </dl> |
|
1756 </td></tr></table> |
|
1757 </div> |
|
1758 <a name="connected_components"></a> |
|
1759 <div> |
|
1760 <table class="details" border="1" cellpadding="3" |
|
1761 cellspacing="0" width="100%" bgcolor="white"> |
|
1762 <tr><td> |
|
1763 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1764 <tr valign="top"><td> |
|
1765 <h3 class="epydoc"><span class="sig"><span class="sig-name">connected_components</span>(<span class="sig-arg">self</span>)</span> |
|
1766 </h3> |
|
1767 </td><td align="right" valign="top" |
|
1768 > |
|
1769 </td> |
|
1770 </tr></table> |
|
1771 |
|
1772 <p>Connected components.</p> |
|
1773 <dl class="fields"> |
|
1774 <dt>Returns: dictionary</dt> |
|
1775 <dd>Pairing that associates each node to its connected component.</dd> |
|
1776 </dl> |
|
1777 <div class="fields"> <p><strong>Attention:</strong> |
|
1778 Indentification of connected components is meaningful only for |
|
1779 non-directed graphs. |
|
1780 </p> |
|
1781 </div></td></tr></table> |
|
1782 </div> |
|
1783 <a name="cut_edges"></a> |
|
1784 <div> |
|
1785 <table class="details" border="1" cellpadding="3" |
|
1786 cellspacing="0" width="100%" bgcolor="white"> |
|
1787 <tr><td> |
|
1788 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1789 <tr valign="top"><td> |
|
1790 <h3 class="epydoc"><span class="sig"><span class="sig-name">cut_edges</span>(<span class="sig-arg">self</span>)</span> |
|
1791 </h3> |
|
1792 </td><td align="right" valign="top" |
|
1793 > |
|
1794 </td> |
|
1795 </tr></table> |
|
1796 |
|
1797 <p>Return the cut-edges of the given graph.</p> |
|
1798 <dl class="fields"> |
|
1799 <dt>Returns: list</dt> |
|
1800 <dd>List of cut-edges.</dd> |
|
1801 </dl> |
|
1802 </td></tr></table> |
|
1803 </div> |
|
1804 <a name="cut_nodes"></a> |
|
1805 <div> |
|
1806 <table class="details" border="1" cellpadding="3" |
|
1807 cellspacing="0" width="100%" bgcolor="white"> |
|
1808 <tr><td> |
|
1809 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1810 <tr valign="top"><td> |
|
1811 <h3 class="epydoc"><span class="sig"><span class="sig-name">cut_nodes</span>(<span class="sig-arg">self</span>)</span> |
|
1812 </h3> |
|
1813 </td><td align="right" valign="top" |
|
1814 > |
|
1815 </td> |
|
1816 </tr></table> |
|
1817 |
|
1818 <p>Return the cut-nodes of the given graph.</p> |
|
1819 <dl class="fields"> |
|
1820 <dt>Returns: list</dt> |
|
1821 <dd>List of cut-nodes.</dd> |
|
1822 </dl> |
|
1823 </td></tr></table> |
|
1824 </div> |
|
1825 <a name="depth_first_search"></a> |
|
1826 <div> |
|
1827 <table class="details" border="1" cellpadding="3" |
|
1828 cellspacing="0" width="100%" bgcolor="white"> |
|
1829 <tr><td> |
|
1830 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1831 <tr valign="top"><td> |
|
1832 <h3 class="epydoc"><span class="sig"><span class="sig-name">depth_first_search</span>(<span class="sig-arg">self</span>, |
|
1833 <span class="sig-arg">root</span>=<span class="sig-default">None</span>)</span> |
|
1834 </h3> |
|
1835 </td><td align="right" valign="top" |
|
1836 > |
|
1837 </td> |
|
1838 </tr></table> |
|
1839 |
|
1840 <p>Depht-first search.</p> |
|
1841 <dl class="fields"> |
|
1842 <dt>Parameters:</dt> |
|
1843 <dd><ul class="nomargin-top"> |
|
1844 <li><strong class="pname"><code>root</code></strong> (node) - Optional root node (will explore only root's connected component)</li> |
|
1845 </ul></dd> |
|
1846 <dt>Returns: tuple</dt> |
|
1847 <dd>tupple containing a dictionary and two lists: |
|
1848 <ol start="1"> |
|
1849 <li> |
|
1850 Generated spanning tree |
|
1851 </li> |
|
1852 <li> |
|
1853 Graph's preordering |
|
1854 </li> |
|
1855 <li> |
|
1856 Graph's postordering |
|
1857 </li> |
|
1858 </ol></dd> |
|
1859 </dl> |
|
1860 </td></tr></table> |
|
1861 </div> |
|
1862 <a name="minimal_spanning_tree"></a> |
|
1863 <div> |
|
1864 <table class="details" border="1" cellpadding="3" |
|
1865 cellspacing="0" width="100%" bgcolor="white"> |
|
1866 <tr><td> |
|
1867 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1868 <tr valign="top"><td> |
|
1869 <h3 class="epydoc"><span class="sig"><span class="sig-name">minimal_spanning_tree</span>(<span class="sig-arg">self</span>, |
|
1870 <span class="sig-arg">root</span>=<span class="sig-default">None</span>)</span> |
|
1871 </h3> |
|
1872 </td><td align="right" valign="top" |
|
1873 > |
|
1874 </td> |
|
1875 </tr></table> |
|
1876 |
|
1877 <p>Minimal spanning tree.</p> |
|
1878 <dl class="fields"> |
|
1879 <dt>Parameters:</dt> |
|
1880 <dd><ul class="nomargin-top"> |
|
1881 <li><strong class="pname"><code>root</code></strong> (node) - Optional root node (will explore only root's connected component)</li> |
|
1882 </ul></dd> |
|
1883 <dt>Returns: list</dt> |
|
1884 <dd>Generated spanning tree.</dd> |
|
1885 </dl> |
|
1886 <div class="fields"> <p><strong>Attention:</strong> |
|
1887 Minimal spanning tree meaningful only for weighted graphs. |
|
1888 </p> |
|
1889 </div></td></tr></table> |
|
1890 </div> |
|
1891 <a name="shortest_path"></a> |
|
1892 <div> |
|
1893 <table class="details" border="1" cellpadding="3" |
|
1894 cellspacing="0" width="100%" bgcolor="white"> |
|
1895 <tr><td> |
|
1896 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
1897 <tr valign="top"><td> |
|
1898 <h3 class="epydoc"><span class="sig"><span class="sig-name">shortest_path</span>(<span class="sig-arg">self</span>, |
|
1899 <span class="sig-arg">source</span>)</span> |
|
1900 </h3> |
|
1901 </td><td align="right" valign="top" |
|
1902 > |
|
1903 </td> |
|
1904 </tr></table> |
|
1905 |
|
1906 <p>Return the shortest path distance between source node and all other |
|
1907 nodes using Dijkstra's algorithm.</p> |
|
1908 <dl class="fields"> |
|
1909 <dt>Parameters:</dt> |
|
1910 <dd><ul class="nomargin-top"> |
|
1911 <li><strong class="pname"><code>source</code></strong> (node) - Node from which to start the search.</li> |
|
1912 </ul></dd> |
|
1913 <dt>Returns: tuple</dt> |
|
1914 <dd>A tuple containing two dictionaries, each keyed by target nodes. |
|
1915 <ol start="1"> |
|
1916 <li> |
|
1917 Shortest path spanning tree |
|
1918 </li> |
|
1919 <li> |
|
1920 Shortest distance from given source to each target node |
|
1921 </li> |
|
1922 </ol> |
|
1923 <p>Inaccessible target nodes do not appear in either |
|
1924 dictionary.</p></dd> |
|
1925 </dl> |
|
1926 <div class="fields"> <p><strong>Attention:</strong> |
|
1927 All weights must be nonnegative. |
|
1928 </p> |
|
1929 </div></td></tr></table> |
|
1930 </div> |
|
1931 <br /> |
|
1932 <!-- ==================== NAVIGATION BAR ==================== --> |
|
1933 <table class="navbar" border="0" width="100%" cellpadding="0" |
|
1934 bgcolor="#a0c0ff" cellspacing="0"> |
|
1935 <tr valign="middle"> |
|
1936 <!-- Home link --> |
|
1937 <th> <a |
|
1938 href="graph-module.html">Home</a> </th> |
|
1939 |
|
1940 <!-- Tree link --> |
|
1941 <th> <a |
|
1942 href="module-tree.html">Trees</a> </th> |
|
1943 |
|
1944 <!-- Index link --> |
|
1945 <th> <a |
|
1946 href="identifier-index.html">Indices</a> </th> |
|
1947 |
|
1948 <!-- Help link --> |
|
1949 <th> <a |
|
1950 href="help.html">Help</a> </th> |
|
1951 |
|
1952 <!-- Project homepage --> |
|
1953 <th class="navbar" align="right" width="100%"> |
|
1954 <table border="0" cellpadding="0" cellspacing="0"> |
|
1955 <tr><th class="navbar" align="center" |
|
1956 ><a class="navbar" target="_top" href="http://code.google.com/p/python-graph/">python-graph</a></th> |
|
1957 </tr></table></th> |
|
1958 </tr> |
|
1959 </table> |
|
1960 <table border="0" cellpadding="0" cellspacing="0" width="100%%"> |
|
1961 <tr> |
|
1962 <td align="left" class="footer"> |
|
1963 Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 |
|
1964 </td> |
|
1965 <td align="right" class="footer"> |
|
1966 <a target="mainFrame" href="http://epydoc.sourceforge.net" |
|
1967 >http://epydoc.sourceforge.net</a> |
|
1968 </td> |
|
1969 </tr> |
|
1970 </table> |
|
1971 |
|
1972 <script type="text/javascript"> |
|
1973 <!-- |
|
1974 // Private objects are initially displayed (because if |
|
1975 // javascript is turned off then we want them to be |
|
1976 // visible); but by default, we want to hide them. So hide |
|
1977 // them unless we have a cookie that says to show them. |
|
1978 checkCookie(); |
|
1979 // --> |
|
1980 </script> |
|
1981 </body> |
|
1982 </html> |