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 32The ``dijkstra_shortest_paths()`` function solves the single-source 33shortest paths problem on a weighted, undirected or directed 34distributed graph. There are two implementations of distributed 35Dijkstra's algorithm, which offer different performance 36tradeoffs. Both are accessible via the ``dijkstra_shortest_paths()`` 37function (for compatibility with sequential BGL programs). The 38distributed Dijkstra algorithms are very similar to their sequential 39counterparts. Only the differences are highlighted here; please refer 40to the `sequential Dijkstra implementation`_ for additional 41details. The best-performing implementation for most cases is the 42`Delta-Stepping algorithm`_; however, one can also employ the more 43conservative `Crauser et al.'s algorithm`_ or the simlistic `Eager 44Dijkstra's algorithm`_. 45 46.. contents:: 47 48Where Defined 49------------- 50<``boost/graph/dijkstra_shortest_paths.hpp``> 51 52Parameters 53---------- 54 55All parameters of the `sequential Dijkstra implementation`_ are 56supported and have essentially the same meaning. The distributed 57Dijkstra implementations introduce a new parameter that allows one to 58select `Eager Dijkstra's algorithm`_ and control the amount of work it 59performs. Only differences and new parameters are documented here. 60 61IN: ``Graph& g`` 62 The graph type must be a model of `Distributed Graph`_. 63 64 65IN: ``vertex_descriptor s`` 66 The start vertex must be the same in every process. 67 68 69OUT: ``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 77UTIL/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 83IN: ``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 89UTIL/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 97IN: ``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 116Visitor Event Points 117-------------------- 118The `Dijkstra Visitor`_ concept defines 7 event points that will be 119triggered by the `sequential Dijkstra implementation`_. The distributed 120Dijkstra retains these event points, but the sequence of events 121triggered and the process in which each event occurs will change 122depending on the distribution of the graph, lookahead, and edge 123weights. 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 165Crauser 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 201The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer, 202and Sanders [CMMS98a]_ improves the scalability of parallel Dijkstra's 203algorithm by increasing the number of vertices that can be processed 204in a given superstep. This algorithm adapts well to various graph 205types, and is a simple algorithm to use, requiring no additional user 206input to achieve reasonable performance. The disadvantage of this 207algorithm is that the implementation is required to manage three 208priority queues, which creates a large amount of work at each node. 209 210This algorithm is used by default in distributed 211``dijkstra_shortest_paths()``. 212 213Where Defined 214~~~~~~~~~~~~~ 215<``boost/graph/distributed/crauser_et_al_shortest_paths.hpp``> 216 217Complexity 218~~~~~~~~~~ 219This algorithm performs *O(V log V)* work in *d + 1* BSP supersteps, 220where *d* is at most *O(V)* but is generally much smaller. On directed 221Erdos-Renyi graphs with edge weights in [0, 1), the expected number of 222supersteps *d* is *O(n^(1/3))* with high probability. 223 224Performance 225~~~~~~~~~~~ 226The following charts illustrate the performance of the Parallel BGL implementation of Crauser et al.'s 227algorithm on graphs with edge weights uniformly selected from the 228range *[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 239Eager 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 279In each superstep, parallel Dijkstra's algorithm typically only 280processes nodes whose distances equivalent to the global minimum 281distance, because these distances are guaranteed to be correct. This 282variation on the algorithm allows the algorithm to process all 283vertices whose distances are within some constant value of the 284minimum distance. The value is called the "lookahead" value and is 285provided by the user as the fifth parameter to the function. Small 286values of the lookahead parameter will likely result in limited 287parallelization opportunities, whereas large values will expose more 288parallelism but may introduce (non-infinite) looping and result in 289extra work. The optimal value for the lookahead parameter depends on 290the input graph; see [CMMS98b]_ and [MS98]_. 291 292This algorithm will be used by ``dijkstra_shortest_paths()`` when it 293is provided with a lookahead value. 294 295Where Defined 296~~~~~~~~~~~~~ 297<``boost/graph/distributed/eager_dijkstra_shortest_paths.hpp``> 298 299Complexity 300~~~~~~~~~~ 301This algorithm performs *O(V log V)* work in *d 302+ 1* BSP supersteps, where *d* is at most *O(V)* but may be smaller 303depending on the lookahead value. the algorithm may perform more work 304when a large lookahead is provided, because vertices will be 305reprocessed. 306 307Performance 308~~~~~~~~~~~ 309The performance of the eager Dijkstra's algorithm varies greatly 310depending on the lookahead value. The following charts illustrate the 311performance of the Parallel BGL on graphs with edge weights uniformly 312selected 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 322Delta-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 349The delta-stepping algorithm [MS98]_ is another variant of the parallel 350Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a 351lookahead (``delta``) value that allows processors to process vertices 352before we are guaranteed to find their minimum distances, permitting 353more parallelism than a conservative strategy. Delta-stepping also 354introduces a multi-level bucket data structure that provides more 355relaxed ordering constraints than the priority queues employed by the 356other Dijkstra variants, reducing the complexity of insertions, 357relaxations, and removals from the central data structure. The 358delta-stepping algorithm is the best-performing of the Dijkstra 359variants. 360 361The lookahead value ``delta`` determines how large each of the 362"buckets" within the delta-stepping queue will be, where the ith 363bucket contains edges within tentative distances between ``delta``*i 364and ``delta``*(i+1). ``delta`` must be a positive value. When omitted, 365``delta`` will be set to the maximum edge weight divided by the 366maximum degree. 367 368Where Defined 369~~~~~~~~~~~~~ 370<``boost/graph/distributed/delta_stepping_shortest_paths.hpp``> 371 372Example 373------- 374See the separate `Dijkstra example`_. 375 376 377Bibliography 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 394Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University. 395 396Authors: 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 409
