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