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: Directed Acyclic Graph 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:dag_shortest_paths"></A> 19<img src="figs/python.gif" alt="(Python)"/> 20<TT>dag_shortest_paths</TT> 21</H1> 22 23 24<P> 25<PRE> 26<i>// named paramter version</i> 27template <class VertexListGraph, class Param, class Tag, class Rest> 28void dag_shortest_paths(const VertexListGraph& g, 29 typename graph_traits<VertexListGraph>::vertex_descriptor s, 30 const bgl_named_params<Param,Tag,Rest>& params) 31 32<i>// non-named parameter version</i> 33template <class VertexListGraph, class DijkstraVisitor, 34 class DistanceMap, class WeightMap, class ColorMap, 35 class PredecessorMap, 36 class Compare, class Combine, 37 class DistInf, class DistZero> 38void 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) 43</PRE> 44 45<P> 46This algorithm [<A HREF="bibliography.html#clr90">8</A>] solves 47the single-source shortest-paths problem on a weighted, directed 48acyclic graph (DAG). This algorithm is more efficient for DAG's 49than either the Dijkstra or Bellman-Ford algorithm. 50Use breadth-first search instead of this algorithm 51when all edge weights are equal to one. For the definition of the 52shortest-path problem see Section <A 53HREF="graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths 54Algorithms</A> for some background to the shortest-path problem. 55</P> 56 57<P> 58There are two main options for obtaining output from the 59<tt>dag_shortest_paths()</tt> function. If you provide a 60distance property map through the <tt>distance_map()</tt> parameter 61then the shortest distance from the source vertex to every other 62vertex in the graph will be recorded in the distance map. Also you can 63record 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 65the shortest paths tree (unless <i>p[u] = u</i>, in which case <i>u</i> is 66either the source or a vertex unreachable from the source). In 67addition to these two options, the user can provide there own 68custom-made visitor that can takes actions during any of the 69algorithm's event points.</P> 70 71<h3>Where Defined</h3> 72 73<a href="../../../boost/graph/dag_shortest_paths.hpp"><tt>boost/graph/dag_shortest_paths.hpp</tt></a> 74 75<h3>Parameters</h3> 76 77IN: <tt>const VertexListGraph& g</tt> 78<blockquote> 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> 81 82 <b>Python</b>: The parameter is named <tt>graph</tt>. 83</blockquote> 84 85IN: <tt>vertex_descriptor s</tt> 86<blockquote> 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> 89 90 <b>Python</b>: The parameter is named <tt>root_vertex</tt>. 91</blockquote> 92 93<h3>Named Parameters</h3> 94 95IN: <tt>weight_map(WeightMap w_map)</tt> 96<blockquote> 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> 106 107</blockquote> 108 109IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 110<blockquote> 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> 123 124 <b>Python</b>: Unsupported parameter. 125</blockquote> 126 127OUT: <tt>predecessor_map(PredecessorMap p_map)</tt> 128<blockquote> 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 134 must be a <a 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> 140</blockquote> 141 142UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt> 143<blockquote> 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. 151 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.boost.org/sgi/stl/StrictWeakOrdering.html"> 157 StrictWeakOrdering</a> provided by the <tt>compare</tt> function 158 object.<br> 159 <b>Default:</b> <a 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 164 map.<br> 165 166 <b>Python</b>: Must be a <tt>vertex_double_map</tt> for the graph. 167</blockquote> 168 169IN: <tt>distance_compare(CompareFunction cmp)</tt> 170<blockquote> 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.boost.org/sgi/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> 177 178 <b>Default:</b> 179 <tt>std::less<D></tt> with <tt>D=typename 180 property_traits<DistanceMap>::value_type</tt><br> 181 182 <b>Python</b>: Unsupported parameter. 183</blockquote> 184 185IN: <tt>distance_combine(CombineFunction cmb)</tt> 186<blockquote> 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.boost.org/sgi/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> 195 196 <b>Default:</b> <tt>std::plus<D></tt> with 197 <tt>D=typename property_traits<DistanceMap>::value_type</tt><br> 198 199 <b>Python</b>: Unsupported parameter. 200</blockquote> 201 202IN: <tt>distance_inf(D inf)</tt> 203<blockquote> 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> 208 209 <b>Python</b>: Unsupported parameter. 210</blockquote> 211 212IN: <tt>distance_zero(D zero)</tt> 213<blockquote> 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> 219 220 <b>Python</b>: Unsupported parameter. 221</blockquote> 222 223UTIL/OUT: <tt>color_map(ColorMap c_map)</tt> 224<blockquote> 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> 240 241 <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for 242 the graph. 243 244</blockquote> 245 246OUT: <tt>visitor(DijkstraVisitor v)</tt> 247<blockquote> 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> 255 256 <b>Python</b>: The parameter should be an object that derives from 257 the <a 258 href="DijkstraVisitor.html#python"><tt>DijkstraVisitor</tt></a> type 259 of the graph. 260</blockquote> 261 262 263<H3>Complexity</H3> 264 265<P> 266The time complexity is <i>O(V + E)</i>. 267 268<h3>Visitor Event Points</h3> 269 270<ul> 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 273 algorithm. 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 297 been examined. 298</ul> 299 300<H3>Example</H3> 301 302<P> 303See <a href="../example/dag_shortest_paths.cpp"> 304<TT>example/dag_shortest_paths.cpp</TT></a> for an example of using this 305algorithm. 306 307<H3>Notes</H3> 308 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. 315 316<br> 317<HR> 318<TABLE> 319<TR valign=top> 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>) 322</TD></TR></TABLE> 323 324</BODY> 325</HTML> 326 327
