]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <HTML> |
2 | <!-- | |
3 | Copyright (c) Jeremy Siek 2000 | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. | |
6 | (See accompanying file LICENSE_1_0.txt or copy at | |
7 | http://www.boost.org/LICENSE_1_0.txt) | |
8 | --> | |
9 | <Head> | |
10 | <Title>Boost Graph Library: Dijkstra's Shortest Paths</Title> | |
11 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
12 | ALINK="#ff0000"> | |
13 | <IMG SRC="../../../boost.png" | |
14 | ALT="C++ Boost" width="277" height="86"> | |
15 | ||
16 | <BR Clear> | |
17 | ||
18 | <H1><A NAME="sec:dijkstra"></A><img src="figs/python.gif" alt="(Python)"/> | |
19 | <TT>dijkstra_shortest_paths</TT> | |
20 | </H1> | |
21 | ||
22 | <P> | |
23 | <PRE> | |
24 | <i>// named parameter version</i> | |
25 | template <typename Graph, typename P, typename T, typename R> | |
26 | void | |
27 | dijkstra_shortest_paths(Graph& g, | |
28 | typename graph_traits<Graph>::vertex_descriptor s, | |
29 | const bgl_named_params<P, T, R>& params); | |
30 | ||
31 | <i>// non-named parameter version</i> | |
32 | template <typename Graph, typename <a href="DijkstraVisitor.html">DijkstraVisitor</a>, | |
33 | typename PredecessorMap, typename DistanceMap, | |
34 | typename WeightMap, typename VertexIndexMap, typename <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">CombineFunction</a>, | |
35 | typename DistInf, typename DistZero, typename ColorMap = <i>default</i>> | |
36 | void dijkstra_shortest_paths | |
37 | (const Graph& g, | |
38 | typename graph_traits<Graph>::vertex_descriptor s, | |
39 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
40 | VertexIndexMap index_map, | |
41 | CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero, | |
42 | DijkstraVisitor vis, ColorMap color = <i>default</i>) | |
43 | ||
44 | <i>// version that does not initialize the property maps (except for the default color map)</i> | |
45 | template <class Graph, class DijkstraVisitor, | |
46 | class PredecessorMap, class DistanceMap, | |
47 | class WeightMap, class IndexMap, class Compare, class Combine, | |
48 | class DistZero, class ColorMap> | |
49 | void | |
50 | dijkstra_shortest_paths_no_init | |
51 | (const Graph& g, | |
52 | typename graph_traits<Graph>::vertex_descriptor s, | |
53 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
54 | IndexMap index_map, | |
55 | Compare compare, Combine combine, DistZero zero, | |
56 | DijkstraVisitor vis, ColorMap color = <i>default</i>); | |
57 | </PRE> | |
58 | ||
59 | <P> | |
60 | This algorithm [<A HREF="bibliography.html#dijkstra59">10</A>,<A | |
61 | HREF="bibliography.html#clr90">8</A>] solves the single-source | |
62 | shortest-paths problem on a weighted, directed or undirected graph for | |
63 | the case where all edge weights are nonnegative. Use the Bellman-Ford | |
64 | algorithm for the case when some edge weights are negative. Use | |
65 | breadth-first search instead of Dijkstra's algorithm when all edge | |
66 | weights are equal to one. For the definition of the shortest-path | |
67 | problem see Section <A | |
68 | HREF="graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths | |
69 | Algorithms</A> for some background to the shortest-path problem. | |
70 | </P> | |
71 | ||
72 | <P> | |
73 | There are two main options for obtaining output from the | |
74 | <tt>dijkstra_shortest_paths()</tt> function. If you provide a | |
75 | distance property map through the <tt>distance_map()</tt> parameter | |
76 | then the shortest distance from the source vertex to every other | |
77 | vertex in the graph will be recorded in the distance map. Also you can | |
78 | record the shortest paths tree in a predecessor map: for each vertex | |
79 | <i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in | |
80 | the shortest paths tree (unless <i>p[u] = u</i>, in which case <i>u</i> is | |
81 | either the source or a vertex unreachable from the source). In | |
82 | addition to these two options, the user can provide their own | |
83 | custom-made visitor that takes actions during any of the | |
84 | algorithm's event points.</P> | |
85 | ||
86 | <P> | |
87 | Dijkstra's algorithm finds all the shortest paths from the source | |
88 | vertex to every other vertex by iteratively ``growing'' the set of | |
89 | vertices <i>S</i> to which it knows the shortest path. At each step of | |
90 | the algorithm, the next vertex added to <i>S</i> is determined by a | |
91 | priority queue. The queue contains the vertices in <i>V - S</i><a | |
92 | href="#1">[1]</a> prioritized by their distance label, which is the | |
93 | length of the shortest path seen so far for each vertex. The vertex | |
94 | <i>u</i> at the top of the priority queue is then added to <i>S</i>, | |
95 | and each of its out-edges is relaxed: if the distance to <i>u</i> plus | |
96 | the weight of the out-edge <i>(u,v)</i> is less than the distance | |
97 | label for <i>v</i> then the estimated distance for vertex <i>v</i> is | |
98 | reduced. The algorithm then loops back, processing the next vertex at | |
99 | the top of the priority queue. The algorithm finishes when the | |
100 | priority queue is empty. | |
101 | </P> | |
102 | <P> | |
103 | The algorithm uses color markers (white, gray, and black) to keep | |
104 | track of which set each vertex is in. Vertices colored black are in | |
105 | <i>S</i>. Vertices colored white or gray are in <i>V-S</i>. White vertices have | |
106 | not yet been discovered and gray vertices are in the priority queue. | |
107 | By default, the algorithm will allocate an array to store a color | |
108 | marker for each vertex in the graph. You can provide your own storage | |
109 | and access for colors with the <tt>color_map()</tt> parameter. | |
110 | </P> | |
111 | <p> | |
112 | The following is the pseudo-code for Dijkstra's single-source shortest | |
113 | paths algorithm. <i>w</i> is the edge weight, <i>d</i> is the distance label, | |
114 | and <i>p</i> is the predecessor of each vertex which is used to encode | |
115 | the shortest paths tree. <i>Q</i> is a priority queue that supports the | |
116 | DECREASE-KEY operation. The visitor event points for the algorithm are | |
117 | indicated by the labels on the right. | |
118 | </p> | |
119 | ||
120 | <table> | |
121 | <tr> | |
122 | <td valign="top"> | |
123 | <pre> | |
124 | DIJKSTRA(<i>G</i>, <i>s</i>, <i>w</i>) | |
125 | <b>for</b> each vertex <i>u in V</i> <b>(This loop is not run in dijkstra_shortest_paths_no_init)</b> | |
126 | <i>d[u] := infinity</i> | |
127 | <i>p[u] := u</i> | |
128 | <i>color[u] :=</i> WHITE | |
129 | <b>end for</b> | |
130 | <i>color[s] := </i>GRAY | |
131 | <i>d[s] := 0</i> | |
132 | INSERT(<i>Q</i>, <i>s</i>) | |
133 | <b>while</b> (<i>Q != Ø</i>) | |
134 | <i>u :=</i> EXTRACT-MIN(<i>Q</i>) | |
135 | <i>S := S U { u }</i> | |
136 | <b>for</b> each vertex <i>v in Adj[u]</i> | |
137 | <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>) | |
138 | <i>d[v] := w(u,v) + d[u]</i> | |
139 | <i>p[v] := u</i> | |
140 | <b>if</b> (<i>color[v] =</i> WHITE) | |
141 | <i>color[v] :=</i> GRAY | |
142 | INSERT(<i>Q</i>, <i>v</i>) | |
143 | <b>else if</b> (<i>color[v] =</i> GRAY) | |
144 | DECREASE-KEY(<i>Q</i>, <i>v</i>) | |
145 | <b>else</b> | |
146 | <i>...</i> | |
147 | <b>end for</b> | |
148 | <i>color[u] :=</i> BLACK | |
149 | <b>end while</b> | |
150 | return (<i>d</i>, <i>p</i>) | |
151 | </pre> | |
152 | </td> | |
153 | <td valign="top"> | |
154 | <pre> | |
155 | ||
156 | initialize vertex <i>u</i> | |
157 | ||
158 | ||
159 | ||
160 | ||
161 | ||
162 | ||
163 | discover vertex <i>s</i> | |
164 | ||
165 | examine vertex <i>u</i> | |
166 | ||
167 | examine edge <i>(u,v)</i> | |
168 | ||
169 | edge <i>(u,v)</i> relaxed | |
170 | ||
171 | ||
172 | ||
173 | discover vertex <i>v</i> | |
174 | ||
175 | ||
176 | ||
177 | edge <i>(u,v)</i> not relaxed | |
178 | ||
179 | finish vertex <i>u</i> | |
180 | </pre> | |
181 | </td> | |
182 | </tr> | |
183 | </table> | |
184 | ||
185 | <h3>Where Defined</h3> | |
186 | ||
187 | <a href="../../../boost/graph/dijkstra_shortest_paths.hpp"><tt>boost/graph/dijkstra_shortest_paths.hpp</tt></a> | |
188 | ||
189 | <h3>Parameters</h3> | |
190 | ||
191 | IN: <tt>const Graph& g</tt> | |
192 | <blockquote> | |
193 | The graph object on which the algorithm will be applied. | |
194 | The type <tt>Graph</tt> must be a model of | |
195 | <a href="./VertexListGraph.html">Vertex List Graph</a> | |
196 | and <a href="./IncidenceGraph.html">Incidence Graph</a>.<br> | |
197 | ||
198 | <b>Python</b>: The parameter is named <tt>graph</tt>. | |
199 | </blockquote> | |
200 | ||
201 | IN: <tt>vertex_descriptor s</tt> | |
202 | <blockquote> | |
203 | The source vertex. All distance will be calculated from this vertex, | |
204 | and the shortest paths tree will be rooted at this vertex.<br> | |
205 | ||
206 | <b>Python</b>: The parameter is named <tt>root_vertex</tt>. | |
207 | </blockquote> | |
208 | ||
209 | <h3>Named Parameters</h3> | |
210 | ||
211 | IN: <tt>weight_map(WeightMap w_map)</tt> | |
212 | <blockquote> | |
213 | The weight or ``length'' of each edge in the graph. The weights | |
214 | must all be non-negative, and the algorithm will throw a | |
215 | <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> | |
216 | exception is one of the edges is negative. | |
217 | The type <tt>WeightMap</tt> must be a model of | |
218 | <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of | |
219 | the graph needs to be usable as the key type for the weight | |
220 | map. The value type for this map must be | |
221 | the same as the value type of the distance map.<br> | |
222 | <b>Default:</b> <tt>get(edge_weight, g)</tt><br> | |
223 | ||
224 | <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br> | |
225 | <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt> | |
226 | </blockquote> | |
227 | ||
228 | IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> | |
229 | <blockquote> | |
230 | This maps each vertex to an integer in the range <tt>[0, | |
231 | num_vertices(g))</tt>. This is necessary for efficient updates of the | |
232 | heap data structure [<A | |
233 | HREF="bibliography.html#driscoll88">61</A>] when an edge is relaxed. | |
234 | The type | |
235 | <tt>VertexIndexMap</tt> must be a model of | |
236 | <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an | |
237 | integer type. The vertex descriptor type of the graph needs to be | |
238 | usable as the key type of the map.<br> | |
239 | <b>Default:</b> <tt>get(vertex_index, g)</tt>. | |
240 | Note: if you use this default, make sure your graph has | |
241 | an internal <tt>vertex_index</tt> property. For example, | |
242 | <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does | |
243 | not have an internal <tt>vertex_index</tt> property. | |
244 | <br> | |
245 | ||
246 | <b>Python</b>: Unsupported parameter. | |
247 | </blockquote> | |
248 | ||
249 | OUT: <tt>predecessor_map(PredecessorMap p_map)</tt> | |
250 | <blockquote> | |
251 | The predecessor map records the edges in the shortest path tree, the tree computed | |
252 | by the traversal of the graph. Upon completion of the algorithm, the edges | |
253 | <i>(p[u],u)</i> for all <i>u in V</i> are in the tree. The shortest path | |
254 | from vertex <i>s</i> to each vertex <i>v</i> in the graph consists of the | |
255 | vertices <i>v</i>, <i>p[v]</i>, <i>p[p[v]]</i>, and so on until <i>s</i> is | |
256 | reached, in reverse order. The | |
257 | tree is not guaranteed to be a minimum spanning tree. If <i>p[u] = | |
258 | u</i> then <i>u</i> is either the source vertex or a vertex that is | |
259 | not reachable from the source. The <tt>PredecessorMap</tt> type | |
260 | must be a <a | |
261 | href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write | |
262 | Property Map</a> whose key and value types are the same as the vertex | |
263 | descriptor type of the graph.<br> | |
264 | <b>Default:</b> <tt>dummy_property_map</tt><br> | |
265 | ||
266 | <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br> | |
267 | </blockquote> | |
268 | ||
269 | UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt> | |
270 | <blockquote> | |
271 | The shortest path weight from the source vertex <tt>s</tt> to each | |
272 | vertex in the graph <tt>g</tt> is recorded in this property map. The | |
273 | shortest path weight is the sum of the edge weights along the | |
274 | shortest path. The type <tt>DistanceMap</tt> must be a model of <a | |
275 | href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write | |
276 | Property Map</a>. The vertex descriptor type of the graph needs to | |
277 | be usable as the key type of the distance map. | |
278 | ||
279 | The value type of the distance map is the element type of a <a | |
280 | href="./Monoid.html">Monoid</a> formed with the <tt>combine</tt> | |
281 | function object and the <tt>zero</tt> object for the identity | |
282 | element. Also the distance value type must have a <a | |
283 | href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"> | |
284 | StrictWeakOrdering</a> provided by the <tt>compare</tt> function | |
285 | object.<br> | |
286 | <b>Default:</b> <a | |
287 | href="../../property_map/doc/iterator_property_map.html"> | |
288 | <tt>iterator_property_map</tt></a> created from a | |
289 | <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size | |
290 | <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index | |
291 | map.<br> | |
292 | ||
293 | <b>Python</b>: Must be a <tt>vertex_double_map</tt> for the graph.<br> | |
294 | </blockquote> | |
295 | ||
296 | IN: <tt>distance_compare(CompareFunction cmp)</tt> | |
297 | <blockquote> | |
298 | This function is use to compare distances to determine which vertex | |
299 | is closer to the source vertex. The <tt>CompareFunction</tt> type | |
300 | must be a model of <a | |
301 | href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary | |
302 | Predicate</a> and have argument types that match the value type of | |
303 | the <tt>DistanceMap</tt> property map.<br> | |
304 | ||
305 | <b>Default:</b> | |
306 | <tt>std::less<D></tt> with <tt>D=typename | |
307 | property_traits<DistanceMap>::value_type</tt><br> | |
308 | ||
309 | <b>Python</b>: Unsupported parameter. | |
310 | </blockquote> | |
311 | ||
312 | IN: <tt>distance_combine(CombineFunction cmb)</tt> | |
313 | <blockquote> | |
314 | This function is used to combine distances to compute the distance | |
315 | of a path. The <tt>CombineFunction</tt> type must be a model of <a | |
316 | href="http://www.sgi.com/tech/stl/BinaryFunction.html">Binary | |
317 | Function</a>. The first argument type of the binary function must | |
318 | match the value type of the <tt>DistanceMap</tt> property map and | |
319 | the second argument type must match the value type of the | |
320 | <tt>WeightMap</tt> property map. The result type must be the same | |
321 | type as the distance value type.<br> | |
322 | ||
323 | <b>Default:</b> <tt>closed_plus<D></tt> with | |
324 | <tt>D=typename property_traits<DistanceMap>::value_type</tt><br> | |
325 | ||
326 | <b>Python</b>: Unsupported parameter. | |
327 | </blockquote> | |
328 | ||
329 | IN: <tt>distance_inf(D inf)</tt> | |
330 | <blockquote> | |
331 | The <tt>inf</tt> object must be the greatest value of any <tt>D</tt> object. | |
332 | That is, <tt>compare(d, inf) == true</tt> for any <tt>d != inf</tt>. | |
333 | The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>. Edges | |
334 | are assumed to have a weight less than (using <tt>distance_compare</tt> for | |
335 | comparison) this value.<br> | |
336 | <b>Default:</b> <tt>std::numeric_limits<D>::max()</tt><br> | |
337 | ||
338 | <b>Python</b>: Unsupported parameter. | |
339 | </blockquote> | |
340 | ||
341 | IN: <tt>distance_zero(D zero)</tt> | |
342 | <blockquote> | |
343 | The <tt>zero</tt> value must be the identity element for the | |
344 | <a href="./Monoid.html">Monoid</a> formed by the distance values | |
345 | and the <tt>combine</tt> function object. | |
346 | The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br> | |
347 | <b>Default:</b> <tt>D()</tt>with | |
348 | <tt>D=typename property_traits<DistanceMap>::value_type</tt><br> | |
349 | ||
350 | <b>Python</b>: Unsupported parameter. | |
351 | </blockquote> | |
352 | ||
353 | UTIL/OUT: <tt>color_map(ColorMap c_map)</tt> | |
354 | <blockquote> | |
355 | This is used during the execution of the algorithm to mark the | |
356 | vertices. The vertices start out white and become gray when they are | |
357 | inserted in the queue. They then turn black when they are removed | |
358 | from the queue. At the end of the algorithm, vertices reachable from | |
359 | the source vertex will have been colored black. All other vertices | |
360 | will still be white. The type <tt>ColorMap</tt> must be a model of | |
361 | <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write | |
362 | Property Map</a>. A vertex descriptor must be usable as the key type | |
363 | of the map, and the value type of the map must be a model of | |
364 | <a href="./ColorValue.html">Color Value</a>.<br> | |
365 | <b>Default:</b> an <a | |
366 | href="../../property_map/doc/iterator_property_map.html"> | |
367 | <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt> | |
368 | of <tt>default_color_type</tt> of size <tt>num_vertices(g)</tt> and | |
369 | using the <tt>i_map</tt> for the index map.<br> | |
370 | ||
371 | <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for | |
372 | the graph. | |
373 | </blockquote> | |
374 | ||
375 | OUT: <tt>visitor(DijkstraVisitor v)</tt> | |
376 | <blockquote> | |
377 | Use this to specify actions that you would like to happen | |
378 | during certain event points within the algorithm. | |
379 | The type <tt>DijkstraVisitor</tt> must be a model of the | |
380 | <a href="./DijkstraVisitor.html">Dijkstra Visitor</a> concept. | |
381 | The visitor object is passed by value <a | |
382 | href="#2">[2]</a>.<br> | |
383 | <b>Default:</b> <tt>dijkstra_visitor<null_visitor></tt><br> | |
384 | ||
385 | <b>Python</b>: The parameter should be an object that derives from | |
386 | the <a | |
387 | href="DijkstraVisitor.html#python"><tt>DijkstraVisitor</tt></a> type | |
388 | of the graph. | |
389 | </blockquote> | |
390 | ||
391 | ||
392 | <H3>Complexity</H3> | |
393 | ||
394 | <P> | |
395 | The time complexity is <i>O(V log V + E)</i>. | |
396 | ||
397 | ||
398 | <h3>Visitor Event Points</h3> | |
399 | ||
400 | <ul> | |
401 | <li><b><tt>vis.initialize_vertex(u, g)</tt></b> | |
402 | is invoked on each vertex in the graph before the start of the | |
403 | algorithm. | |
404 | <li><b><tt>vis.examine_vertex(u, g)</tt></b> | |
405 | is invoked on a vertex as it is removed from the priority queue | |
406 | and added to set <i>S</i>. At this point we know that <i>(p[u],u)</i> | |
407 | is a shortest-paths tree edge so | |
408 | <i>d[u] = delta(s,u) = d[p[u]] + w(p[u],u)</i>. Also, the distances | |
409 | of the examined vertices is monotonically increasing | |
410 | <i>d[u<sub>1</sub>] <= d[u<sub>2</sub>] <= d[u<sub>n</sub>]</i>. | |
411 | <li><b><tt>vis.examine_edge(e, g)</tt></b> | |
412 | is invoked on each out-edge of a vertex immediately after it has | |
413 | been added to set <i>S</i>. | |
414 | <li><b><tt>vis.edge_relaxed(e, g)</tt></b> | |
415 | is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) < d[v]</i>. | |
416 | The edge <i>(u,v)</i> that participated in the last | |
417 | relaxation for vertex <i>v</i> is an edge in the shortest paths tree. | |
418 | <li><b><tt>vis.discover_vertex(v, g)</tt></b> | |
419 | is invoked on vertex <i>v</i> when the edge | |
420 | <i>(u,v)</i> is examined and <i>v</i> is WHITE. Since | |
421 | a vertex is colored GRAY when it is discovered, | |
422 | each reacable vertex is discovered exactly once. This | |
423 | is also when the vertex is inserted into the priority queue. | |
424 | <li><b><tt>vis.edge_not_relaxed(e, g)</tt></b> | |
425 | is invoked if the edge is not relaxed (see above). | |
426 | <li><b><tt>vis.finish_vertex(u, g)</tt></b> | |
427 | is invoked on a vertex after all of its out edges have | |
428 | been examined. | |
429 | </ul> | |
430 | ||
431 | <H3>Example</H3> | |
432 | ||
433 | <P> | |
434 | See <a href="../example/dijkstra-example.cpp"> | |
435 | <TT>example/dijkstra-example.cpp</TT></a> for an example of using Dijkstra's | |
436 | algorithm. | |
437 | ||
438 | <H3>See also</H3> <a href="dijkstra_shortest_paths_no_color_map.html">dijkstra_shortest_paths_no_color_map</a> for a version of dijkstra's shortest path that does not use a color map. | |
439 | ||
440 | <H3>Notes</H3> | |
441 | ||
442 | <a name="1">[1]</a> | |
443 | The algorithm used here saves a little space by not putting all <i>V - | |
444 | S</i> vertices in the priority queue at once, but instead only those | |
445 | vertices in <i>V - S</i> that are discovered and therefore have a | |
446 | distance less than infinity. | |
447 | ||
448 | <p><a name="2">[2]</a> | |
449 | Since the visitor parameter is passed by value, if your visitor | |
450 | contains state then any changes to the state during the algorithm | |
451 | will be made to a copy of the visitor object, not the visitor object | |
452 | passed in. Therefore you may want the visitor to hold this state by | |
453 | pointer or reference. | |
454 | ||
455 | <br> | |
456 | <HR> | |
457 | <TABLE> | |
458 | <TR valign=top> | |
459 | <TD nowrap>Copyright © 2000-2001</TD><TD> | |
460 | <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) | |
461 | </TD></TR></TABLE> | |
462 | ||
463 | </BODY> | |
464 | </HTML> |