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.minmax</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 Module minmax |
|
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 <!-- ==================== MODULE DESCRIPTION ==================== --> |
|
57 <h1 class="epydoc">Module minmax</h1><p class="nomargin-top"></p> |
|
58 <p>Minimization and maximization algorithms for python-graph.</p> |
|
59 |
|
60 <!-- ==================== FUNCTIONS ==================== --> |
|
61 <a name="section-Functions"></a> |
|
62 <table class="summary" border="1" cellpadding="3" |
|
63 cellspacing="0" width="100%" bgcolor="white"> |
|
64 <tr bgcolor="#70b0f0" class="table-header"> |
|
65 <td align="left" colspan="2" class="table-header"> |
|
66 <span class="table-header">Functions</span></td> |
|
67 </tr> |
|
68 <tr> |
|
69 <td width="15%" align="right" valign="top" class="summary"> |
|
70 <span class="summary-type">dictionary</span> |
|
71 </td><td class="summary"> |
|
72 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
73 <tr> |
|
74 <td><span class="summary-sig"><a href="graph.minmax-module.html#minimal_spanning_tree" class="summary-sig-name">minimal_spanning_tree</a>(<span class="summary-sig-arg">graph</span>, |
|
75 <span class="summary-sig-arg">root</span>=<span class="summary-sig-default">None</span>)</span><br /> |
|
76 Minimal spanning tree.</td> |
|
77 <td align="right" valign="top"> |
|
78 |
|
79 |
|
80 </td> |
|
81 </tr> |
|
82 </table> |
|
83 |
|
84 </td> |
|
85 </tr> |
|
86 <tr> |
|
87 <td width="15%" align="right" valign="top" class="summary"> |
|
88 <span class="summary-type">tuple</span> |
|
89 </td><td class="summary"> |
|
90 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
91 <tr> |
|
92 <td><span class="summary-sig"><a href="graph.minmax-module.html#shortest_path" class="summary-sig-name">shortest_path</a>(<span class="summary-sig-arg">graph</span>, |
|
93 <span class="summary-sig-arg">source</span>)</span><br /> |
|
94 Return the shortest path distance between source and all other nodes |
|
95 using Dijkstra's algorithm.</td> |
|
96 <td align="right" valign="top"> |
|
97 |
|
98 |
|
99 </td> |
|
100 </tr> |
|
101 </table> |
|
102 |
|
103 </td> |
|
104 </tr> |
|
105 </table> |
|
106 <!-- ==================== FUNCTION DETAILS ==================== --> |
|
107 <a name="section-FunctionDetails"></a> |
|
108 <table class="details" border="1" cellpadding="3" |
|
109 cellspacing="0" width="100%" bgcolor="white"> |
|
110 <tr bgcolor="#70b0f0" class="table-header"> |
|
111 <td align="left" colspan="2" class="table-header"> |
|
112 <span class="table-header">Function Details</span></td> |
|
113 </tr> |
|
114 </table> |
|
115 <a name="minimal_spanning_tree"></a> |
|
116 <div> |
|
117 <table class="details" border="1" cellpadding="3" |
|
118 cellspacing="0" width="100%" bgcolor="white"> |
|
119 <tr><td> |
|
120 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
121 <tr valign="top"><td> |
|
122 <h3 class="epydoc"><span class="sig"><span class="sig-name">minimal_spanning_tree</span>(<span class="sig-arg">graph</span>, |
|
123 <span class="sig-arg">root</span>=<span class="sig-default">None</span>)</span> |
|
124 </h3> |
|
125 </td><td align="right" valign="top" |
|
126 > |
|
127 </td> |
|
128 </tr></table> |
|
129 |
|
130 <p>Minimal spanning tree.</p> |
|
131 <dl class="fields"> |
|
132 <dt>Parameters:</dt> |
|
133 <dd><ul class="nomargin-top"> |
|
134 <li><strong class="pname"><code>graph</code></strong> (graph) - Graph.</li> |
|
135 <li><strong class="pname"><code>root</code></strong> (node) - Optional root node (will explore only root's connected component)</li> |
|
136 </ul></dd> |
|
137 <dt>Returns: dictionary</dt> |
|
138 <dd>Generated spanning tree.</dd> |
|
139 </dl> |
|
140 <div class="fields"> <p><strong>Attention:</strong> |
|
141 Minimal spanning tree meaningful only for weighted graphs. |
|
142 </p> |
|
143 </div></td></tr></table> |
|
144 </div> |
|
145 <a name="shortest_path"></a> |
|
146 <div> |
|
147 <table class="details" border="1" cellpadding="3" |
|
148 cellspacing="0" width="100%" bgcolor="white"> |
|
149 <tr><td> |
|
150 <table width="100%" cellpadding="0" cellspacing="0" border="0"> |
|
151 <tr valign="top"><td> |
|
152 <h3 class="epydoc"><span class="sig"><span class="sig-name">shortest_path</span>(<span class="sig-arg">graph</span>, |
|
153 <span class="sig-arg">source</span>)</span> |
|
154 </h3> |
|
155 </td><td align="right" valign="top" |
|
156 > |
|
157 </td> |
|
158 </tr></table> |
|
159 |
|
160 <p>Return the shortest path distance between source and all other nodes |
|
161 using Dijkstra's algorithm.</p> |
|
162 <dl class="fields"> |
|
163 <dt>Parameters:</dt> |
|
164 <dd><ul class="nomargin-top"> |
|
165 <li><strong class="pname"><code>graph</code></strong> (graph) - Graph.</li> |
|
166 <li><strong class="pname"><code>source</code></strong> (node) - Node from which to start the search.</li> |
|
167 </ul></dd> |
|
168 <dt>Returns: tuple</dt> |
|
169 <dd>A tuple containing two dictionaries, each keyed by target nodes. |
|
170 <ol start="1"> |
|
171 <li> |
|
172 Shortest path spanning tree |
|
173 </li> |
|
174 <li> |
|
175 Shortest distance from given source to each target node |
|
176 </li> |
|
177 </ol> |
|
178 <p>Inaccessible target nodes do not appear in either |
|
179 dictionary.</p></dd> |
|
180 </dl> |
|
181 <div class="fields"> <p><strong>Attention:</strong> |
|
182 All weights must be nonnegative. |
|
183 </p> |
|
184 </div></td></tr></table> |
|
185 </div> |
|
186 <br /> |
|
187 <!-- ==================== NAVIGATION BAR ==================== --> |
|
188 <table class="navbar" border="0" width="100%" cellpadding="0" |
|
189 bgcolor="#a0c0ff" cellspacing="0"> |
|
190 <tr valign="middle"> |
|
191 <!-- Home link --> |
|
192 <th> <a |
|
193 href="graph-module.html">Home</a> </th> |
|
194 |
|
195 <!-- Tree link --> |
|
196 <th> <a |
|
197 href="module-tree.html">Trees</a> </th> |
|
198 |
|
199 <!-- Index link --> |
|
200 <th> <a |
|
201 href="identifier-index.html">Indices</a> </th> |
|
202 |
|
203 <!-- Help link --> |
|
204 <th> <a |
|
205 href="help.html">Help</a> </th> |
|
206 |
|
207 <!-- Project homepage --> |
|
208 <th class="navbar" align="right" width="100%"> |
|
209 <table border="0" cellpadding="0" cellspacing="0"> |
|
210 <tr><th class="navbar" align="center" |
|
211 ><a class="navbar" target="_top" href="http://code.google.com/p/python-graph/">python-graph</a></th> |
|
212 </tr></table></th> |
|
213 </tr> |
|
214 </table> |
|
215 <table border="0" cellpadding="0" cellspacing="0" width="100%%"> |
|
216 <tr> |
|
217 <td align="left" class="footer"> |
|
218 Generated by Epydoc 3.0.1 on Mon Oct 27 20:36:37 2008 |
|
219 </td> |
|
220 <td align="right" class="footer"> |
|
221 <a target="mainFrame" href="http://epydoc.sourceforge.net" |
|
222 >http://epydoc.sourceforge.net</a> |
|
223 </td> |
|
224 </tr> |
|
225 </table> |
|
226 |
|
227 <script type="text/javascript"> |
|
228 <!-- |
|
229 // Private objects are initially displayed (because if |
|
230 // javascript is turned off then we want them to be |
|
231 // visible); but by default, we want to hide them. So hide |
|
232 // them unless we have a cookie that says to show them. |
|
233 checkCookie(); |
|
234 // --> |
|
235 </script> |
|
236 </body> |
|
237 </html> |
|