ceph/src/boost/libs/graph_parallel/doc/dijkstra_shortest_paths.rst

   1 .. Copyright (C) 2004-2008 The Trustees of Indiana University.
   2    Use, modification and distribution is subject to the Boost Software
   3    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   4    http://www.boost.org/LICENSE_1_0.txt)
   5
   6 ==============================================
   7 |Logo| Dijkstra's Single-Source Shortest Paths
   8 ==============================================
   9
  10 ::
  11
  12   // named parameter version
  13   template <typename Graph, typename P, typename T, typename R>
  14   void
  15   dijkstra_shortest_paths(Graph& g,
  16     typename graph_traits<Graph>::vertex_descriptor s,
  17     const bgl_named_params<P, T, R>& params);
  18
  19   // non-named parameter version
  20   template <typename Graph, typename DijkstraVisitor,
  21             typename PredecessorMap, typename DistanceMap,
  22             typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename CombineFunction,
  23             typename DistInf, typename DistZero>
  24   void dijkstra_shortest_paths
  25     (const Graph& g,
  26      typename graph_traits<Graph>::vertex_descriptor s,
  27      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
  28      VertexIndexMap index_map,
  29      CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
  30      DijkstraVisitor vis);
  31
  32 The ``dijkstra_shortest_paths()`` function solves the single-source
  33 shortest paths problem on a weighted, undirected or directed
  34 distributed graph. There are two implementations of distributed
  35 Dijkstra's algorithm, which offer different performance
  36 tradeoffs. Both are accessible via the ``dijkstra_shortest_paths()``
  37 function (for compatibility with sequential BGL programs). The
  38 distributed Dijkstra algorithms are very similar to their sequential
  39 counterparts. Only the differences are highlighted here; please refer
  40 to the `sequential Dijkstra implementation`_ for additional
  41 details. The best-performing implementation for most cases is the
  42 `Delta-Stepping algorithm`_; however, one can also employ the more
  43 conservative `Crauser et al.'s algorithm`_ or the simlistic  `Eager
  44 Dijkstra's algorithm`_.
  45
  46 .. contents::
  47
  48 Where Defined
  49 -------------
  50 <``boost/graph/dijkstra_shortest_paths.hpp``>
  51
  52 Parameters
  53 ----------
  54
  55 All parameters of the `sequential Dijkstra implementation`_ are
  56 supported and have essentially the same meaning. The distributed
  57 Dijkstra implementations introduce a new parameter that allows one to
  58 select `Eager Dijkstra's algorithm`_ and control the amount of work it
  59 performs. Only differences and new parameters are documented here.
  60
  61 IN: ``Graph& g``
  62   The graph type must be a model of `Distributed Graph`_.
  63
  64
  65 IN: ``vertex_descriptor s``
  66   The start vertex must be the same in every process.
  67
  68
  69 OUT: ``predecessor_map(PredecessorMap p_map)``
  70   The predecessor map must be a `Distributed Property Map`_ or
  71   ``dummy_property_map``, although only the local portions of the map
  72   will be written.
  73
  74   **Default:** ``dummy_property_map``
  75
  76
  77 UTIL/OUT: ``distance_map(DistanceMap d_map)``
  78   The distance map must be either a `Distributed Property Map`_ or
  79   ``dummy_property_map``. It will be given the ``vertex_distance``
  80   role.
  81
  82
  83 IN: ``visitor(DijkstraVisitor vis)``
  84   The visitor must be a distributed Dijkstra visitor. The suble differences
  85   between sequential and distributed Dijkstra visitors are discussed in the
  86   section `Visitor Event Points`_.
  87
  88
  89 UTIL/OUT: ``color_map(ColorMap color)``
  90   The color map must be a `Distributed Property Map`_ with the same
  91   process group as the graph ``g`` whose colors must monotonically
  92   darken (white -> gray -> black). The default value is a distributed
  93   ``iterator_property_map`` created from a ``std::vector`` of
  94   ``default_color_type``.
  95
  96
  97 IN: ``lookahead(distance_type look)``
  98
  99   When this parameter is supplied, the implementation will use the
 100   `Eager Dijkstra's algorithm`_ with the given lookahead value.
 101   Lookahead permits distributed Dijkstra's algorithm to speculatively
 102   process vertices whose shortest distance from the source may not
 103   have been found yet. When the distance found is the shortest
 104   distance, parallelism is improved and the algorithm may terminate
 105   more quickly. However, if the distance is not the shortest distance,
 106   the vertex will need to be reprocessed later, resulting in more
 107   work.
 108
 109   The type ``distance_type`` is the value type of the ``DistanceMap``
 110   property map. It is a nonnegative value specifying how far ahead
 111   Dijkstra's algorithm may process values.
 112
 113   **Default:** no value (lookahead is not employed; uses `Crauser et
 114   al.'s algorithm`_).
 115
 116 Visitor Event Points
 117 --------------------
 118 The `Dijkstra Visitor`_ concept defines 7 event points that will be
 119 triggered by the `sequential Dijkstra implementation`_. The distributed
 120 Dijkstra retains these event points, but the sequence of events
 121 triggered and the process in which each event occurs will change
 122 depending on the distribution of the graph, lookahead, and edge
 123 weights.
 124
 125 ``initialize_vertex(s, g)``
 126   This will be invoked by every process for each local vertex.
 127
 128
 129 ``discover_vertex(u, g)``
 130   This will be invoked each type a process discovers a new vertex
 131   ``u``. Due to incomplete information in distributed property maps,
 132   this event may be triggered many times for the same vertex ``u``.
 133
 134
 135 ``examine_vertex(u, g)``
 136   This will be invoked by the process owning the vertex ``u``. This
 137   event may be invoked multiple times for the same vertex when the
 138   graph contains negative edges or lookahead is employed.
 139
 140
 141 ``examine_edge(e, g)``
 142   This will be invoked by the process owning the source vertex of
 143   ``e``. As with ``examine_vertex``, this event may be invoked
 144   multiple times for the same edge.
 145
 146
 147 ``edge_relaxed(e, g)``
 148   Similar to ``examine_edge``, this will be invoked by the process
 149   owning the source vertex and may be invoked multiple times (even
 150   without lookahead or negative edges).
 151
 152
 153 ``edge_not_relaxed(e, g)``
 154   Similar to ``edge_relaxed``. Some ``edge_not_relaxed`` events that
 155   would be triggered by sequential Dijkstra's will become
 156   ``edge_relaxed`` events in distributed Dijkstra's algorithm.
 157
 158
 159 ``finish_vertex(e, g)``
 160   See documentation for ``examine_vertex``. Note that a "finished"
 161   vertex is not necessarily finished if lookahead is permitted or
 162   negative edges exist in the graph.
 163
 164
 165 Crauser et al.'s algorithm
 166 --------------------------
 167
 168 ::
 169
 170   namespace graph {
 171     template<typename DistributedGraph, typename DijkstraVisitor,
 172              typename PredecessorMap, typename DistanceMap, typename WeightMap,
 173              typename IndexMap, typename ColorMap, typename Compare,
 174              typename Combine, typename DistInf, typename DistZero>
 175     void
 176     crauser_et_al_shortest_paths
 177       (const DistributedGraph& g,
 178        typename graph_traits<DistributedGraph>::vertex_descriptor s,
 179        PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 180        IndexMap index_map, ColorMap color_map,
 181        Compare compare, Combine combine, DistInf inf, DistZero zero,
 182        DijkstraVisitor vis);
 183
 184     template<typename DistributedGraph, typename DijkstraVisitor,
 185              typename PredecessorMap, typename DistanceMap, typename WeightMap>
 186     void
 187     crauser_et_al_shortest_paths
 188       (const DistributedGraph& g,
 189        typename graph_traits<DistributedGraph>::vertex_descriptor s,
 190        PredecessorMap predecessor, DistanceMap distance, WeightMap weight);
 191
 192     template<typename DistributedGraph, typename DijkstraVisitor,
 193              typename PredecessorMap, typename DistanceMap>
 194     void
 195     crauser_et_al_shortest_paths
 196       (const DistributedGraph& g,
 197        typename graph_traits<DistributedGraph>::vertex_descriptor s,
 198        PredecessorMap predecessor, DistanceMap distance);
 199   }
 200
 201 The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
 202 and Sanders [CMMS98a]_ improves the scalability of parallel Dijkstra's
 203 algorithm by increasing the number of vertices that can be processed
 204 in a given superstep. This algorithm adapts well to various graph
 205 types, and is a simple algorithm to use, requiring no additional user
 206 input to achieve reasonable performance. The disadvantage of this
 207 algorithm is that the implementation is required to manage three
 208 priority queues, which creates a large amount of work at each node.
 209
 210 This algorithm is used by default in distributed
 211 ``dijkstra_shortest_paths()``.
 212
 213 Where Defined
 214 ~~~~~~~~~~~~~
 215 <``boost/graph/distributed/crauser_et_al_shortest_paths.hpp``>
 216
 217 Complexity
 218 ~~~~~~~~~~
 219 This algorithm performs *O(V log V)* work in *d + 1* BSP supersteps,
 220 where *d* is at most *O(V)* but is generally much smaller. On directed
 221 Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
 222 supersteps *d* is *O(n^(1/3))* with high probability.
 223
 224 Performance
 225 ~~~~~~~~~~~
 226 The following charts illustrate the performance of the Parallel BGL implementation of Crauser et al.'s
 227 algorithm on graphs with edge weights uniformly selected from the
 228 range *[0, 1)*.
 229
 230 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4
 231   :align: left
 232 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1
 233
 234 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4
 235   :align: left
 236 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1
 237
 238
 239 Eager Dijkstra's algorithm
 240 --------------------------
 241
 242 ::
 243
 244   namespace graph {
 245     template<typename DistributedGraph, typename DijkstraVisitor,
 246              typename PredecessorMap, typename DistanceMap, typename WeightMap,
 247              typename IndexMap, typename ColorMap, typename Compare,
 248              typename Combine, typename DistInf, typename DistZero>
 249     void
 250     eager_dijkstra_shortest_paths
 251       (const DistributedGraph& g,
 252        typename graph_traits<DistributedGraph>::vertex_descriptor s,
 253        PredecessorMap predecessor, DistanceMap distance,
 254        typename property_traits<DistanceMap>::value_type lookahead,
 255        WeightMap weight, IndexMap index_map, ColorMap color_map,
 256        Compare compare, Combine combine, DistInf inf, DistZero zero,
 257        DijkstraVisitor vis);
 258
 259     template<typename DistributedGraph, typename DijkstraVisitor,
 260              typename PredecessorMap, typename DistanceMap, typename WeightMap>
 261     void
 262     eager_dijkstra_shortest_paths
 263       (const DistributedGraph& g,
 264        typename graph_traits<DistributedGraph>::vertex_descriptor s,
 265        PredecessorMap predecessor, DistanceMap distance,
 266        typename property_traits<DistanceMap>::value_type lookahead,
 267        WeightMap weight);
 268
 269     template<typename DistributedGraph, typename DijkstraVisitor,
 270              typename PredecessorMap, typename DistanceMap>
 271     void
 272     eager_dijkstra_shortest_paths
 273       (const DistributedGraph& g,
 274        typename graph_traits<DistributedGraph>::vertex_descriptor s,
 275        PredecessorMap predecessor, DistanceMap distance,
 276        typename property_traits<DistanceMap>::value_type lookahead);
 277   }
 278
 279 In each superstep, parallel Dijkstra's algorithm typically only
 280 processes nodes whose distances equivalent to the global minimum
 281 distance, because these distances are guaranteed to be correct. This
 282 variation on the algorithm allows the algorithm to process all
 283 vertices whose distances are within some constant value of the
 284 minimum distance. The value is called the "lookahead" value and is
 285 provided by the user as the fifth parameter to the function. Small
 286 values of the lookahead parameter will likely result in limited
 287 parallelization opportunities, whereas large values will expose more
 288 parallelism but may introduce (non-infinite) looping and result in
 289 extra work. The optimal value for the lookahead parameter depends on
 290 the input graph; see [CMMS98b]_ and [MS98]_.
 291
 292 This algorithm will be used by ``dijkstra_shortest_paths()`` when it
 293 is provided with a lookahead value.
 294
 295 Where Defined
 296 ~~~~~~~~~~~~~
 297 <``boost/graph/distributed/eager_dijkstra_shortest_paths.hpp``>
 298
 299 Complexity
 300 ~~~~~~~~~~
 301 This algorithm performs *O(V log V)* work in *d
 302 + 1* BSP supersteps, where *d* is at most *O(V)* but may be smaller
 303 depending on the lookahead value. the algorithm may perform more work
 304 when a large lookahead is provided, because vertices will be
 305 reprocessed.
 306
 307 Performance
 308 ~~~~~~~~~~~
 309 The performance of the eager Dijkstra's algorithm varies greatly
 310 depending on the lookahead value. The following charts illustrate the
 311 performance of the Parallel BGL on graphs with edge weights uniformly
 312 selected from the range *[0, 1)* and a constant lookahead of 0.1.
 313
 314 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5
 315   :align: left
 316 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1
 317
 318 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5
 319   :align: left
 320 .. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1
 321
 322 Delta-Stepping algorithm
 323 --------------------------
 324
 325 ::
 326
 327   namespace boost { namespace graph { namespace distributed {
 328
 329     template <typename Graph, typename PredecessorMap,
 330               typename DistanceMap, typename WeightMap>
 331     void delta_stepping_shortest_paths
 332       (const Graph& g,
 333        typename graph_traits<Graph>::vertex_descriptor s,
 334        PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
 335        typename property_traits<WeightMap>::value_type delta)
 336
 337
 338     template <typename Graph, typename PredecessorMap,
 339               typename DistanceMap, typename WeightMap>
 340     void delta_stepping_shortest_paths
 341       (const Graph& g,
 342        typename graph_traits<Graph>::vertex_descriptor s,
 343        PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
 344     }
 345
 346   } } }
 347
 348
 349 The delta-stepping algorithm [MS98]_ is another variant of the parallel
 350 Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
 351 lookahead (``delta``) value that allows processors to process vertices
 352 before we are guaranteed to find their minimum distances, permitting
 353 more parallelism than a conservative strategy. Delta-stepping also
 354 introduces a multi-level bucket data structure that provides more
 355 relaxed ordering constraints than the priority queues employed by the
 356 other Dijkstra variants, reducing the complexity of insertions,
 357 relaxations, and removals from the central data structure. The
 358 delta-stepping algorithm is the best-performing of the Dijkstra
 359 variants.
 360
 361 The lookahead value ``delta`` determines how large each of the
 362 "buckets" within the delta-stepping queue will be, where the ith
 363 bucket contains edges within tentative distances between ``delta``*i
 364 and ``delta``*(i+1). ``delta`` must be a positive value. When omitted,
 365 ``delta`` will be set to the maximum edge weight divided by the
 366 maximum degree.
 367
 368 Where Defined
 369 ~~~~~~~~~~~~~
 370 <``boost/graph/distributed/delta_stepping_shortest_paths.hpp``>
 371
 372 Example
 373 -------
 374 See the separate `Dijkstra example`_.
 375
 376
 377 Bibliography
 378 ------------
 379
 380 .. [CMMS98a] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
 381   Parallelization of Dijkstra's Shortest Path Algorithm. In
 382   *Mathematical Foundations of Computer Science (MFCS)*, volume 1450 of
 383   Lecture Notes in Computer Science, pages 722--731, 1998. Springer.
 384
 385 .. [CMMS98b] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
 386   Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
 387   report, MPI-Informatik, 1998.
 388
 389 .. [MS98] Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel
 390   shortest path algorithm. In *6th ESA*, LNCS. Springer, 1998.
 391
 392 -----------------------------------------------------------------------------
 393
 394 Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University.
 395
 396 Authors: Douglas Gregor and Andrew Lumsdaine
 397
 398 .. |Logo| image:: pbgl-logo.png
 399             :align: middle
 400             :alt: Parallel BGL
 401             :target: http://www.osl.iu.edu/research/pbgl
 402
 403 .. _sequential Dijkstra implementation: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
 404 .. _distributed breadth-first search: breadth_first_search.html
 405 .. _Distributed Graph: DistributedGraph.html
 406 .. _Distributed Property Map: distributed_property_map.html
 407 .. _Dijkstra Visitor: http://www.boost.org/libs/graph/doc/DijkstraVisitor.html
 408 .. _Dijkstra example: dijkstra_example.html