ceph/src/boost/libs/graph/doc/dag_shortest_paths.html

   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>
  27 template &lt;class VertexListGraph, class Param, class Tag, class Rest&gt;
  28 void dag_shortest_paths(const VertexListGraph&amp; g,
  29    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
  30    const bgl_named_params&lt;Param,Tag,Rest&gt;&amp; params)
  31
  32 <i>// non-named parameter version</i>
  33 template &lt;class VertexListGraph, class DijkstraVisitor,
  34           class DistanceMap, class WeightMap, class ColorMap,
  35           class PredecessorMap,
  36           class Compare, class Combine,
  37           class DistInf, class DistZero&gt;
  38 void dag_shortest_paths(const VertexListGraph&amp; g,
  39    typename graph_traits&lt;VertexListGraph&gt;::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>
  46 This algorithm&nbsp;[<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.
  55 </P>
  56
  57 <P>
  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>
  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
  77 IN: <tt>const VertexListGraph&amp; 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
  85 IN: <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
  95 IN: <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
 109 IN: <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
 127 OUT: <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
 142 UTIL/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.sgi.com/tech/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
 169 IN: <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.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>
 177
 178   <b>Default:</b>
 179   <tt>std::less&lt;D&gt;</tt> with <tt>D=typename
 180   property_traits&lt;DistanceMap&gt;::value_type</tt><br>
 181
 182   <b>Python</b>: Unsupported parameter.
 183 </blockquote>
 184
 185 IN: <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.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>
 195
 196   <b>Default:</b> <tt>std::plus&lt;D&gt;</tt> with
 197    <tt>D=typename property_traits&lt;DistanceMap&gt;::value_type</tt><br>
 198
 199   <b>Python</b>: Unsupported parameter.
 200 </blockquote>
 201
 202 IN: <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&lt;D&gt;::max()</tt><br>
 208
 209   <b>Python</b>: Unsupported parameter.
 210 </blockquote>
 211
 212 IN: <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
 223 UTIL/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
 246 OUT: <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&lt;null_visitor&gt;</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>
 266 The 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>
 303 See <a href="../example/dag_shortest_paths.cpp">
 304 <TT>example/dag_shortest_paths.cpp</TT></a> for an example of using this
 305 algorithm.
 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 &copy; 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