]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |