3 Copyright (c) Jeremy Siek 2000
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)
10 <Title>Boost Graph Library: Directed Acyclic Graph Shortest Paths
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><A NAME=
"sec:dag_shortest_paths"></A>
19 <img src=
"figs/python.gif" alt=
"(Python)"/>
20 <TT>dag_shortest_paths
</TT>
26 <i>// named paramter version
</i>
27 template
<class VertexListGraph, class Param, class Tag, class Rest
>
28 void dag_shortest_paths(const VertexListGraph
& g,
29 typename graph_traits
<VertexListGraph
>::vertex_descriptor s,
30 const bgl_named_params
<Param,Tag,Rest
>& params)
32 <i>// non-named parameter version
</i>
33 template
<class VertexListGraph, class DijkstraVisitor,
34 class DistanceMap, class WeightMap, class ColorMap,
36 class Compare, class Combine,
37 class DistInf, class DistZero
>
38 void dag_shortest_paths(const VertexListGraph
& g,
39 typename graph_traits
<VertexListGraph
>::vertex_descriptor s,
40 DistanceMap distance, WeightMap weight, ColorMap color,
41 PredecessorMap pred, DijkstraVisitor vis,
42 Compare compare, Combine combine, DistInf inf, DistZero zero)
46 This algorithm
[
<A HREF=
"bibliography.html#clr90">8</A>] solves
47 the single-source shortest-paths problem on a weighted, directed
48 acyclic graph (DAG). This algorithm is more efficient for DAG's
49 than either the Dijkstra or Bellman-Ford algorithm.
50 Use breadth-first search instead of this algorithm
51 when all edge weights are equal to one. For the definition of the
52 shortest-path problem see Section
<A
53 HREF=
"graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths
54 Algorithms
</A> for some background to the shortest-path problem.
58 There are two main options for obtaining output from the
59 <tt>dag_shortest_paths()
</tt> function. If you provide a
60 distance property map through the
<tt>distance_map()
</tt> parameter
61 then the shortest distance from the source vertex to every other
62 vertex in the graph will be recorded in the distance map. Also you can
63 record the shortest paths tree in a predecessor map: for each vertex
64 <i>u in V
</i>,
<i>p[u]
</i> will be the predecessor of
<i>u
</i> in
65 the shortest paths tree (unless
<i>p[u] = u
</i>, in which case
<i>u
</i> is
66 either the source or a vertex unreachable from the source). In
67 addition to these two options, the user can provide there own
68 custom-made visitor that can takes actions during any of the
69 algorithm's event points.
</P>
71 <h3>Where Defined
</h3>
73 <a href=
"../../../boost/graph/dag_shortest_paths.hpp"><tt>boost/graph/dag_shortest_paths.hpp
</tt></a>
77 IN:
<tt>const VertexListGraph
& g
</tt>
79 The graph object on which the algorithm will be applied.
80 The type
<tt>VertexListGraph
</tt> must be a model of \concept{VertexListGraph}.
<br>
82 <b>Python
</b>: The parameter is named
<tt>graph
</tt>.
85 IN:
<tt>vertex_descriptor s
</tt>
87 The source vertex. All distance will be calculated from this vertex,
88 and the shortest paths tree will be rooted at this vertex.
<br>
90 <b>Python
</b>: The parameter is named
<tt>root_vertex
</tt>.
93 <h3>Named Parameters
</h3>
95 IN:
<tt>weight_map(WeightMap w_map)
</tt>
97 The weight or ``length'' of each edge in the graph.
98 The type
<tt>WeightMap
</tt> must be a model of
99 <a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
</a>. The edge descriptor type of
100 the graph needs to be usable as the key type for the weight
101 map. The value type for the map must be
102 <i>Addable
</i> with the value type of the distance map.
<br>
103 <b>Default:
</b> <tt>get(edge_weight, g)
</tt><br>
104 <b>Python
</b>: Must be an
<tt>edge_double_map
</tt> for the graph.
<br>
105 <b>Python default
</b>:
<tt>graph.get_edge_double_map(
"weight")
</tt>
109 IN:
<tt>vertex_index_map(VertexIndexMap i_map)
</tt>
111 This maps each vertex to an integer in the range
<tt>[
0,
112 num_vertices(g))
</tt>. This is necessary for efficient updates of the
113 heap data structure when an edge is relaxed. The type
114 <tt>VertexIndexMap
</tt> must be a model of
115 <a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
</a>. The value type of the map must be an
116 integer type. The vertex descriptor type of the graph needs to be
117 usable as the key type of the map.
<br>
118 <b>Default:
</b> <tt>get(vertex_index, g)
</tt>.
119 Note: if you use this default, make sure your graph has
120 an internal
<tt>vertex_index
</tt> property. For example,
121 <tt>adjacency_list
</tt> with
<tt>VertexList=listS
</tt> does
122 not have an internal
<tt>vertex_index
</tt> property.
<br>
124 <b>Python
</b>: Unsupported parameter.
127 OUT:
<tt>predecessor_map(PredecessorMap p_map)
</tt>
129 The predecessor map records the edges in the minimum spanning
130 tree. Upon completion of the algorithm, the edges
<i>(p[u],u)
</i>
131 for all
<i>u in V
</i> are in the minimum spanning tree. If
<i>p[u] =
132 u
</i> then
<i>u
</i> is either the source vertex or a vertex that is
133 not reachable from the source. The
<tt>PredecessorMap
</tt> type
135 href=
"../../property_map/doc/ReadWritePropertyMap.html">Read/Write
136 Property Map
</a> which key and vertex types the same as the vertex
137 descriptor type of the graph.
<br>
138 <b>Default:
</b> <tt>dummy_property_map
</tt><br>
139 <b>Python
</b>: Must be a
<tt>vertex_vertex_map
</tt> for the graph.
<br>
142 UTIL/OUT:
<tt>distance_map(DistanceMap d_map)
</tt>
144 The shortest path weight from the source vertex
<tt>s
</tt> to each
145 vertex in the graph
<tt>g
</tt> is recorded in this property map. The
146 shortest path weight is the sum of the edge weights along the
147 shortest path. The type
<tt>DistanceMap
</tt> must be a model of
<a
148 href=
"../../property_map/doc/ReadWritePropertyMap.html">Read/Write
149 Property Map
</a>. The vertex descriptor type of the graph needs to
150 be usable as the key type of the distance map.
152 The value type of the distance map is the element type of a
<a
153 href=
"./Monoid.html">Monoid
</tt> formed with the
<tt>combine
</tt>
154 function object and the
<tt>zero
</tt> object for the identity
155 element. Also the distance value type must have a
<a
156 href=
"http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
157 StrictWeakOrdering
</a> provided by the
<tt>compare
</tt> function
160 href=
"../../property_map/doc/iterator_property_map.html">
161 <tt>iterator_property_map
</tt></a> created from a
162 <tt>std::vector
</tt> of the
<tt>WeightMap
</tt>'s value type of size
163 <tt>num_vertices(g)
</tt> and using the
<tt>i_map
</tt> for the index
166 <b>Python
</b>: Must be a
<tt>vertex_double_map
</tt> for the graph.
169 IN:
<tt>distance_compare(CompareFunction cmp)
</tt>
171 This function is use to compare distances to determine which vertex
172 is closer to the source vertex. The
<tt>CompareFunction
</tt> type
173 must be a model of
<a
174 href=
"http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
175 Predicate
</a> and have argument types that match the value type of
176 the
<tt>DistanceMap
</tt> property map.
<br>
179 <tt>std::less
<D
></tt> with
<tt>D=typename
180 property_traits
<DistanceMap
>::value_type
</tt><br>
182 <b>Python
</b>: Unsupported parameter.
185 IN:
<tt>distance_combine(CombineFunction cmb)
</tt>
187 This function is used to combine distances to compute the distance
188 of a path. The
<tt>CombineFunction
</tt> type must be a model of
<a
189 href=
"http://www.sgi.com/tech/stl/BinaryFunction.html">Binary
190 Function
</a>. The first argument type of the binary function must
191 match the value type of the
<tt>DistanceMap
</tt> property map and
192 the second argument type must match the value type of the
193 <tt>WeightMap
</tt> property map. The result type must be the same
194 type as the distance value type.
<br>
196 <b>Default:
</b> <tt>std::plus
<D
></tt> with
197 <tt>D=typename property_traits
<DistanceMap
>::value_type
</tt><br>
199 <b>Python
</b>: Unsupported parameter.
202 IN:
<tt>distance_inf(D inf)
</tt>
204 The
<tt>inf
</tt> object must be the greatest value of any
<tt>D
</tt> object.
205 That is,
<tt>compare(d, inf) == true
</tt> for any
<tt>d != inf
</tt>.
206 The type
<tt>D
</tt> is the value type of the
<tt>DistanceMap
</tt>.
<br>
207 <b>Default:
</b> <tt>std::numeric_limits
<D
>::max()
</tt><br>
209 <b>Python
</b>: Unsupported parameter.
212 IN:
<tt>distance_zero(D zero)
</tt>
214 The
<tt>zero
</tt> value must be the identity element for the
215 <a href=
"./Monoid.html">Monoid
</a> formed by the distance values
216 and the
<tt>combine
</tt> function object.
217 The type \code{D} is the value type of the \code{DistanceMap}
218 <b>Default:
</b> <tt>D()
</tt><br>
220 <b>Python
</b>: Unsupported parameter.
223 UTIL/OUT:
<tt>color_map(ColorMap c_map)
</tt>
225 This is used during the execution of the algorithm to mark the
226 vertices. The vertices start out white and become gray when they are
227 inserted in the queue. They then turn black when they are removed
228 from the queue. At the end of the algorithm, vertices reachable from
229 the source vertex will have been colored black. All other vertices
230 will still be white. The type
<tt>ColorMap
</tt> must be a model of
231 <a href=
"../../property_map/doc/ReadWritePropertyMap.html">Read/Write
232 Property Map
</a>. A vertex descriptor must be usable as the key type
233 of the map, and the value type of the map must be a model of
234 <a href=
"./ColorValue.html">Color Value
</a>.
<br>
235 <b>Default:
</b> an
<a
236 href=
"../../property_map/doc/iterator_property_map.html">
237 <tt>iterator_property_map
</tt></a> created from a
<tt>std::vector
</tt>
238 of
<tt>default_color_type
</tt> of size
<tt>num_vertices(g)
</tt> and
239 using the
<tt>i_map
</tt> for the index map.
<br>
241 <b>Python
</b>: The color map must be a
<tt>vertex_color_map
</tt> for
246 OUT:
<tt>visitor(DijkstraVisitor v)
</tt>
248 Use this to specify actions that you would like to happen
249 during certain event points within the algorithm.
250 The type
<tt>DijkstraVisitor
</tt> must be a model of the
251 <a href=
"./DijkstraVisitor.html">Dijkstra Visitor
</a> concept.
252 The visitor object is passed by value
<a
253 href=
"#1">[
1]
</a>.
<br>
254 <b>Default:
</b> <tt>dijkstra_visitor
<null_visitor
></tt><br>
256 <b>Python
</b>: The parameter should be an object that derives from
258 href=
"DijkstraVisitor.html#python"><tt>DijkstraVisitor
</tt></a> type
266 The time complexity is
<i>O(V + E)
</i>.
268 <h3>Visitor Event Points
</h3>
271 <li><b><tt>vis.initialize_vertex(u, g)
</tt></b>
272 is invoked on each vertex in the graph before the start of the
274 <li><b><tt>vis.examine_vertex(u, g)
</tt></b>
275 is invoked on a vertex as it is added to set
<i>S
</i>.
276 At this point we know that
<i>(p[u],u)
</i>
277 is a shortest-paths tree edge so
278 <i>d[u] = delta(s,u) = d[p[u]] + w(p[u],u)
</i>. Also, the distances
279 of the examined vertices is monotonically increasing
280 <i>d[u
<sub>1</sub>] <= d[u
<sub>2</sub>] <= d[u
<sub>n
</sub>]
</i>.
281 <li><b><tt>vis.examine_edge(e, g)
</tt></b>
282 is invoked on each out-edge of a vertex immediately after it has
283 been added to set
<i>S
</i>.
284 <li><b><tt>vis.edge_relaxed(e, g)
</tt></b>
285 is invoked on edge
<i>(u,v)
</i> if
<i>d[u] + w(u,v) < d[v]
</i>.
286 The edge
<i>(u,v)
</i> that participated in the last
287 relaxation for vertex
<i>v
</i> is an edge in the shortest paths tree.
288 <li><b><tt>vis.discover_vertex(v, g)
</tt></b>
289 is invoked on vertex
<i>v
</i> when the edge
290 <i>(u,v)
</i> is examined and
<i>v
</i> is WHITE. Since
291 a vertex is colored GRAY when it is discovered,
292 each reacable vertex is discovered exactly once.
293 <li><b><tt>vis.edge_not_relaxed(e, g)
</tt></b>
294 is invoked if the edge is not relaxed (see above).
295 <li><b><tt>vis.finish_vertex(u, g)
</tt></b>
296 is invoked on a vertex after all of its out edges have
303 See
<a href=
"../example/dag_shortest_paths.cpp">
304 <TT>example/dag_shortest_paths.cpp
</TT></a> for an example of using this
309 <p><a name=
"1">[
1]
</a>
310 Since the visitor parameter is passed by value, if your visitor
311 contains state then any changes to the state during the algorithm
312 will be made to a copy of the visitor object, not the visitor object
313 passed in. Therefore you may want the visitor to hold this state by
314 pointer or reference.
320 <TD nowrap
>Copyright
© 2000-
2001</TD><TD>
321 <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>)