]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2004-2006 The Trustees of Indiana University. |
2 | ||
3 | // Use, modification and distribution is subject to the Boost Software | |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
9 | ||
10 | /************************************************************************** | |
11 | * This source file implements the variation on Dijkstra's algorithm * | |
12 | * presented by Crauser et al. in: * | |
13 | * * | |
14 | * Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter * | |
15 | * Sanders. A Parallelization of Dijkstra's Shortest Path * | |
16 | * Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska, * | |
17 | * editors, Mathematical Foundations of Computer Science (MFCS), * | |
18 | * volume 1450 of Lecture Notes in Computer Science, pages * | |
19 | * 722--731, 1998. Springer. * | |
20 | * * | |
21 | * This implementation is, however, restricted to the distributed-memory * | |
22 | * case, where the work is distributed by virtue of the vertices being * | |
23 | * distributed. In a shared-memory (single address space) context, we * | |
24 | * would want to add an explicit balancing step. * | |
25 | **************************************************************************/ | |
26 | #ifndef BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP | |
27 | #define BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP | |
28 | ||
29 | #ifndef BOOST_GRAPH_USE_MPI | |
30 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
31 | #endif | |
32 | ||
33 | #include <boost/assert.hpp> | |
34 | #include <boost/graph/distributed/detail/dijkstra_shortest_paths.hpp> | |
35 | #include <boost/graph/parallel/algorithm.hpp> | |
36 | #include <functional> | |
37 | #include <boost/graph/iteration_macros.hpp> | |
38 | #include <boost/property_map/property_map_iterator.hpp> | |
39 | #include <boost/type_traits/is_same.hpp> | |
40 | #include <algorithm> | |
41 | #include <boost/property_map/parallel/caching_property_map.hpp> | |
42 | #include <boost/pending/indirect_cmp.hpp> | |
43 | #include <boost/graph/distributed/detail/remote_update_set.hpp> | |
44 | #include <vector> | |
45 | #include <boost/graph/breadth_first_search.hpp> | |
46 | #include <boost/graph/dijkstra_shortest_paths.hpp> | |
47 | #include <boost/graph/parallel/container_traits.hpp> | |
48 | ||
49 | #ifdef PBGL_ACCOUNTING | |
50 | # include <boost/graph/accounting.hpp> | |
51 | # include <numeric> | |
52 | #endif // PBGL_ACCOUNTING | |
53 | ||
54 | #ifdef MUTABLE_QUEUE | |
55 | # include <boost/pending/mutable_queue.hpp> | |
56 | #endif | |
57 | ||
58 | namespace boost { namespace graph { namespace distributed { | |
59 | ||
60 | #ifdef PBGL_ACCOUNTING | |
61 | struct crauser_et_al_shortest_paths_stats_t | |
62 | { | |
63 | /* Total wall-clock time used by the algorithm.*/ | |
64 | accounting::time_type execution_time; | |
65 | ||
66 | /* The number of vertices deleted in each superstep. */ | |
67 | std::vector<std::size_t> deleted_vertices; | |
68 | ||
69 | template<typename OutputStream> | |
70 | void print(OutputStream& out) | |
71 | { | |
72 | double avg_deletions = std::accumulate(deleted_vertices.begin(), | |
73 | deleted_vertices.end(), | |
74 | 0.0); | |
75 | avg_deletions /= deleted_vertices.size(); | |
76 | ||
77 | out << "Problem = \"Single-Source Shortest Paths\"\n" | |
78 | << "Algorithm = \"Crauser et al\"\n" | |
79 | << "Function = crauser_et_al_shortest_paths\n" | |
80 | << "Wall clock time = " << accounting::print_time(execution_time) | |
81 | << "\nSupersteps = " << deleted_vertices.size() << "\n" | |
82 | << "Avg. deletions per superstep = " << avg_deletions << "\n"; | |
83 | } | |
84 | }; | |
85 | ||
86 | static crauser_et_al_shortest_paths_stats_t crauser_et_al_shortest_paths_stats; | |
87 | #endif | |
88 | ||
89 | namespace detail { | |
90 | ||
91 | /************************************************************************ | |
92 | * Function objects that perform distance comparisons modified by the * | |
93 | * minimum or maximum edge weights. * | |
94 | ************************************************************************/ | |
95 | template<typename Vertex, typename DistanceMap, typename MinInWeightMap, | |
96 | typename Combine, typename Compare> | |
97 | struct min_in_distance_compare | |
98 | : std::binary_function<Vertex, Vertex, bool> | |
99 | { | |
100 | min_in_distance_compare(DistanceMap d, MinInWeightMap m, | |
101 | Combine combine, Compare compare) | |
102 | : distance_map(d), min_in_weight(m), combine(combine), | |
103 | compare(compare) | |
104 | { | |
105 | } | |
106 | ||
107 | bool operator()(const Vertex& x, const Vertex& y) const | |
108 | { | |
109 | return compare(combine(get(distance_map, x), -get(min_in_weight, x)), | |
110 | combine(get(distance_map, y), -get(min_in_weight, y))); | |
111 | } | |
112 | ||
113 | private: | |
114 | DistanceMap distance_map; | |
115 | MinInWeightMap min_in_weight; | |
116 | Combine combine; | |
117 | Compare compare; | |
118 | }; | |
119 | ||
120 | template<typename Vertex, typename DistanceMap, typename MinOutWeightMap, | |
121 | typename Combine, typename Compare> | |
122 | struct min_out_distance_compare | |
123 | : std::binary_function<Vertex, Vertex, bool> | |
124 | { | |
125 | min_out_distance_compare(DistanceMap d, MinOutWeightMap m, | |
126 | Combine combine, Compare compare) | |
127 | : distance_map(d), min_out_weight(m), combine(combine), | |
128 | compare(compare) | |
129 | { | |
130 | } | |
131 | ||
132 | bool operator()(const Vertex& x, const Vertex& y) const | |
133 | { | |
134 | return compare(combine(get(distance_map, x), get(min_out_weight, x)), | |
135 | combine(get(distance_map, y), get(min_out_weight, y))); | |
136 | } | |
137 | ||
138 | private: | |
139 | DistanceMap distance_map; | |
140 | MinOutWeightMap min_out_weight; | |
141 | Combine combine; | |
142 | Compare compare; | |
143 | }; | |
144 | /************************************************************************/ | |
145 | ||
146 | /************************************************************************ | |
147 | * Dijkstra queue that implements Crauser et al.'s criteria. This queue * | |
148 | * actually stores three separate priority queues, to help expose all * | |
149 | * vertices that can be processed in a single phase. * | |
150 | ************************************************************************/ | |
151 | template<typename Graph, typename Combine, | |
152 | typename Compare, typename VertexIndexMap, typename DistanceMap, | |
153 | typename PredecessorMap, typename MinOutWeightMap, | |
154 | typename MinInWeightMap> | |
155 | class crauser_et_al_dijkstra_queue | |
156 | : public graph::detail::remote_update_set< | |
157 | crauser_et_al_dijkstra_queue< | |
158 | Graph, Combine, Compare, VertexIndexMap, DistanceMap, | |
159 | PredecessorMap, MinOutWeightMap, MinInWeightMap>, | |
160 | typename boost::graph::parallel::process_group_type<Graph>::type, | |
161 | typename dijkstra_msg_value<DistanceMap, PredecessorMap>::type, | |
162 | typename property_map<Graph, vertex_owner_t>::const_type> | |
163 | { | |
164 | typedef typename graph_traits<Graph>::vertex_descriptor | |
165 | vertex_descriptor; | |
166 | typedef crauser_et_al_dijkstra_queue self_type; | |
167 | typedef dijkstra_msg_value<DistanceMap, PredecessorMap> msg_value_creator; | |
168 | typedef typename msg_value_creator::type msg_value_type; | |
169 | typedef typename graph_traits<Graph>::vertices_size_type | |
170 | vertices_size_type; | |
171 | typedef typename property_map<Graph, vertex_owner_t>::const_type | |
172 | OwnerPropertyMap; | |
173 | typedef typename boost::graph::parallel::process_group_type<Graph>::type | |
174 | process_group_type; | |
175 | typedef graph::detail::remote_update_set<self_type, process_group_type, | |
176 | msg_value_type, OwnerPropertyMap> | |
177 | inherited; | |
178 | ||
179 | // Priority queue for tentative distances | |
180 | typedef indirect_cmp<DistanceMap, Compare> dist_queue_compare_type; | |
181 | ||
182 | typedef typename property_traits<DistanceMap>::value_type distance_type; | |
183 | ||
184 | #ifdef MUTABLE_QUEUE | |
185 | typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>, | |
186 | dist_queue_compare_type, VertexIndexMap> dist_queue_type; | |
187 | ||
188 | #else | |
189 | typedef relaxed_heap<vertex_descriptor, dist_queue_compare_type, | |
190 | VertexIndexMap> dist_queue_type; | |
191 | #endif // MUTABLE_QUEUE | |
192 | ||
193 | // Priority queue for OUT criteria | |
194 | typedef min_out_distance_compare<vertex_descriptor, DistanceMap, | |
195 | MinOutWeightMap, Combine, Compare> | |
196 | out_queue_compare_type; | |
197 | ||
198 | #ifdef MUTABLE_QUEUE | |
199 | typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>, | |
200 | out_queue_compare_type, VertexIndexMap> out_queue_type; | |
201 | ||
202 | #else | |
203 | typedef relaxed_heap<vertex_descriptor, out_queue_compare_type, | |
204 | VertexIndexMap> out_queue_type; | |
205 | #endif // MUTABLE_QUEUE | |
206 | ||
207 | // Priority queue for IN criteria | |
208 | typedef min_in_distance_compare<vertex_descriptor, DistanceMap, | |
209 | MinInWeightMap, Combine, Compare> | |
210 | in_queue_compare_type; | |
211 | ||
212 | #ifdef MUTABLE_QUEUE | |
213 | typedef mutable_queue<vertex_descriptor, std::vector<vertex_descriptor>, | |
214 | in_queue_compare_type, VertexIndexMap> in_queue_type; | |
215 | ||
216 | #else | |
217 | typedef relaxed_heap<vertex_descriptor, in_queue_compare_type, | |
218 | VertexIndexMap> in_queue_type; | |
219 | #endif // MUTABLE_QUEUE | |
220 | ||
221 | typedef typename process_group_type::process_id_type process_id_type; | |
222 | ||
223 | public: | |
224 | typedef typename dist_queue_type::size_type size_type; | |
225 | typedef typename dist_queue_type::value_type value_type; | |
226 | ||
227 | crauser_et_al_dijkstra_queue(const Graph& g, | |
228 | const Combine& combine, | |
229 | const Compare& compare, | |
230 | const VertexIndexMap& id, | |
231 | const DistanceMap& distance_map, | |
232 | const PredecessorMap& predecessor_map, | |
233 | const MinOutWeightMap& min_out_weight, | |
234 | const MinInWeightMap& min_in_weight) | |
235 | : inherited(boost::graph::parallel::process_group(g), get(vertex_owner, g)), | |
236 | dist_queue(num_vertices(g), | |
237 | dist_queue_compare_type(distance_map, compare), | |
238 | id), | |
239 | out_queue(num_vertices(g), | |
240 | out_queue_compare_type(distance_map, min_out_weight, | |
241 | combine, compare), | |
242 | id), | |
243 | in_queue(num_vertices(g), | |
244 | in_queue_compare_type(distance_map, min_in_weight, | |
245 | combine, compare), | |
246 | id), | |
247 | g(g), | |
248 | distance_map(distance_map), | |
249 | predecessor_map(predecessor_map), | |
250 | min_out_weight(min_out_weight), | |
251 | min_in_weight(min_in_weight), | |
252 | min_distance(0), | |
253 | min_out_distance(0) | |
254 | #ifdef PBGL_ACCOUNTING | |
255 | , local_deletions(0) | |
256 | #endif | |
257 | { } | |
258 | ||
259 | void push(const value_type& x) | |
260 | { | |
261 | msg_value_type msg_value = | |
262 | msg_value_creator::create(get(distance_map, x), | |
263 | predecessor_value(get(predecessor_map, x))); | |
264 | inherited::update(x, msg_value); | |
265 | } | |
266 | ||
267 | void update(const value_type& x) { push(x); } | |
268 | ||
269 | void pop() | |
270 | { | |
271 | // Remove from distance queue | |
272 | dist_queue.remove(top_vertex); | |
273 | ||
274 | // Remove from OUT queue | |
275 | out_queue.remove(top_vertex); | |
276 | ||
277 | // Remove from IN queue | |
278 | in_queue.remove(top_vertex); | |
279 | ||
280 | #ifdef PBGL_ACCOUNTING | |
281 | ++local_deletions; | |
282 | #endif | |
283 | } | |
284 | ||
285 | vertex_descriptor& top() { return top_vertex; } | |
286 | const vertex_descriptor& top() const { return top_vertex; } | |
287 | ||
288 | bool empty() | |
289 | { | |
290 | inherited::collect(); | |
291 | ||
292 | // If there are no suitable messages, wait until we get something | |
293 | while (!has_suitable_vertex()) { | |
294 | if (do_synchronize()) return true; | |
295 | } | |
296 | // Return true only if nobody has any messages; false if we | |
297 | // have suitable messages | |
298 | return false; | |
299 | } | |
300 | ||
301 | bool do_synchronize() | |
302 | { | |
303 | using boost::parallel::all_reduce; | |
304 | using boost::parallel::minimum; | |
305 | ||
306 | inherited::synchronize(); | |
307 | ||
308 | // TBD: could use combine here, but then we need to stop using | |
309 | // minimum<distance_type>() as the function object. | |
310 | distance_type local_distances[2]; | |
311 | local_distances[0] = | |
312 | dist_queue.empty()? (std::numeric_limits<distance_type>::max)() | |
313 | : get(distance_map, dist_queue.top()); | |
314 | ||
315 | local_distances[1] = | |
316 | out_queue.empty()? (std::numeric_limits<distance_type>::max)() | |
317 | : (get(distance_map, out_queue.top()) | |
318 | + get(min_out_weight, out_queue.top())); | |
319 | ||
320 | distance_type distances[2]; | |
321 | all_reduce(this->process_group, local_distances, local_distances + 2, | |
322 | distances, minimum<distance_type>()); | |
323 | min_distance = distances[0]; | |
324 | min_out_distance = distances[1]; | |
325 | ||
326 | #ifdef PBGL_ACCOUNTING | |
327 | std::size_t deletions = 0; | |
328 | all_reduce(this->process_group, &local_deletions, &local_deletions + 1, | |
329 | &deletions, std::plus<std::size_t>()); | |
330 | if (process_id(this->process_group) == 0) { | |
331 | crauser_et_al_shortest_paths_stats.deleted_vertices.push_back(deletions); | |
332 | } | |
333 | local_deletions = 0; | |
334 | BOOST_ASSERT(deletions > 0); | |
335 | #endif | |
336 | ||
337 | return min_distance == (std::numeric_limits<distance_type>::max)(); | |
338 | } | |
339 | ||
340 | private: | |
341 | vertex_descriptor predecessor_value(vertex_descriptor v) const | |
342 | { return v; } | |
343 | ||
344 | vertex_descriptor | |
345 | predecessor_value(property_traits<dummy_property_map>::reference) const | |
346 | { return graph_traits<Graph>::null_vertex(); } | |
347 | ||
348 | bool has_suitable_vertex() const | |
349 | { | |
350 | if (!dist_queue.empty()) { | |
351 | top_vertex = dist_queue.top(); | |
352 | if (get(distance_map, dist_queue.top()) <= min_out_distance) | |
353 | return true; | |
354 | } | |
355 | ||
356 | if (!in_queue.empty()) { | |
357 | top_vertex = in_queue.top(); | |
358 | return (get(distance_map, top_vertex) | |
359 | - get(min_in_weight, top_vertex)) <= min_distance; | |
360 | } | |
361 | return false; | |
362 | } | |
363 | ||
364 | public: | |
365 | void | |
366 | receive_update(process_id_type source, vertex_descriptor vertex, | |
367 | distance_type distance) | |
368 | { | |
369 | // Update the queue if the received distance is better than | |
370 | // the distance we know locally | |
371 | if (distance < get(distance_map, vertex) | |
372 | || (distance == get(distance_map, vertex) | |
373 | && source == process_id(this->process_group))) { | |
374 | // Update the local distance map | |
375 | put(distance_map, vertex, distance); | |
376 | ||
377 | bool is_in_queue = dist_queue.contains(vertex); | |
378 | ||
379 | if (!is_in_queue) { | |
380 | dist_queue.push(vertex); | |
381 | out_queue.push(vertex); | |
382 | in_queue.push(vertex); | |
383 | } | |
384 | else { | |
385 | dist_queue.update(vertex); | |
386 | out_queue.update(vertex); | |
387 | in_queue.update(vertex); | |
388 | } | |
389 | } | |
390 | } | |
391 | ||
392 | void | |
393 | receive_update(process_id_type source, vertex_descriptor vertex, | |
394 | std::pair<distance_type, vertex_descriptor> p) | |
395 | { | |
396 | if (p.first <= get(distance_map, vertex)) { | |
397 | put(predecessor_map, vertex, p.second); | |
398 | receive_update(source, vertex, p.first); | |
399 | } | |
400 | } | |
401 | ||
402 | private: | |
403 | dist_queue_type dist_queue; | |
404 | out_queue_type out_queue; | |
405 | in_queue_type in_queue; | |
406 | mutable value_type top_vertex; | |
407 | const Graph& g; | |
408 | DistanceMap distance_map; | |
409 | PredecessorMap predecessor_map; | |
410 | MinOutWeightMap min_out_weight; | |
411 | MinInWeightMap min_in_weight; | |
412 | distance_type min_distance; | |
413 | distance_type min_out_distance; | |
414 | #ifdef PBGL_ACCOUNTING | |
415 | std::size_t local_deletions; | |
416 | #endif | |
417 | }; | |
418 | /************************************************************************/ | |
419 | ||
420 | /************************************************************************ | |
421 | * Initialize the property map that contains the minimum incoming edge * | |
422 | * weight for each vertex. There are separate implementations for * | |
423 | * directed, bidirectional, and undirected graph. * | |
424 | ************************************************************************/ | |
425 | template<typename Graph, typename MinInWeightMap, typename WeightMap, | |
426 | typename Inf, typename Compare> | |
427 | void | |
428 | initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight, | |
429 | WeightMap weight, Inf inf, Compare compare, | |
430 | directed_tag, incidence_graph_tag) | |
431 | { | |
432 | // Send minimum weights off to the owners | |
433 | set_property_map_role(vertex_distance, min_in_weight); | |
434 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
435 | BGL_FORALL_OUTEDGES_T(v, e, g, Graph) { | |
436 | if (get(weight, e) < get(min_in_weight, target(e, g))) | |
437 | put(min_in_weight, target(e, g), get(weight, e)); | |
438 | } | |
439 | } | |
440 | ||
441 | using boost::graph::parallel::process_group; | |
442 | synchronize(process_group(g)); | |
443 | ||
444 | // Replace any infinities with zeros | |
445 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
446 | if (get(min_in_weight, v) == inf) put(min_in_weight, v, 0); | |
447 | } | |
448 | } | |
449 | ||
450 | template<typename Graph, typename MinInWeightMap, typename WeightMap, | |
451 | typename Inf, typename Compare> | |
452 | void | |
453 | initialize_min_in_weights(const Graph& g, MinInWeightMap min_in_weight, | |
454 | WeightMap weight, Inf inf, Compare compare, | |
455 | directed_tag, bidirectional_graph_tag) | |
456 | { | |
457 | #if 0 | |
458 | typename property_map<Graph, vertex_local_t>::const_type | |
459 | local = get(vertex_local, g); | |
460 | ||
461 | // This code assumes that the properties of the in-edges are | |
462 | // available locally. This is not necessarily the case, so don't | |
463 | // do this yet. | |
464 | set_property_map_role(vertex_distance, min_in_weight); | |
465 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
466 | if (in_edges(v, g).first != in_edges(v, g).second) { | |
467 | std::cerr << "weights(" << g.distribution().global(get(local, v)) | |
468 | << ") = "; | |
469 | BGL_FORALL_INEDGES_T(v, e, g, Graph) { | |
470 | std::cerr << get(weight, e) << ' '; | |
471 | } | |
472 | std::cerr << std::endl; | |
473 | put(min_in_weight, v, | |
474 | *std::min_element | |
475 | (make_property_map_iterator(weight, in_edges(v, g).first), | |
476 | make_property_map_iterator(weight, in_edges(v, g).second), | |
477 | compare)); | |
478 | } else { | |
479 | put(min_in_weight, v, 0); | |
480 | } | |
481 | std::cerr << "miw(" << g.distribution().global(get(local, v)) << ") = " | |
482 | << get(min_in_weight, v) << std::endl; | |
483 | } | |
484 | #else | |
485 | initialize_min_in_weights(g, min_in_weight, weight, inf, compare, | |
486 | directed_tag(), incidence_graph_tag()); | |
487 | #endif | |
488 | } | |
489 | ||
490 | template<typename Graph, typename MinInWeightMap, typename WeightMap, | |
491 | typename Inf, typename Compare> | |
492 | inline void | |
493 | initialize_min_in_weights(const Graph&, MinInWeightMap, WeightMap, Inf, | |
494 | Compare, undirected_tag, bidirectional_graph_tag) | |
495 | { | |
496 | // In weights are the same as out weights, so do nothing | |
497 | } | |
498 | /************************************************************************/ | |
499 | ||
500 | ||
501 | /************************************************************************ | |
502 | * Initialize the property map that contains the minimum outgoing edge * | |
503 | * weight for each vertex. * | |
504 | ************************************************************************/ | |
505 | template<typename Graph, typename MinOutWeightMap, typename WeightMap, | |
506 | typename Compare> | |
507 | void | |
508 | initialize_min_out_weights(const Graph& g, MinOutWeightMap min_out_weight, | |
509 | WeightMap weight, Compare compare) | |
510 | { | |
511 | typedef typename property_traits<WeightMap>::value_type weight_type; | |
512 | ||
513 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
514 | if (out_edges(v, g).first != out_edges(v, g).second) { | |
515 | put(min_out_weight, v, | |
516 | *std::min_element | |
517 | (make_property_map_iterator(weight, out_edges(v, g).first), | |
518 | make_property_map_iterator(weight, out_edges(v, g).second), | |
519 | compare)); | |
520 | if (get(min_out_weight, v) < weight_type(0)) | |
521 | boost::throw_exception(negative_edge()); | |
522 | } | |
523 | } | |
524 | } | |
525 | ||
526 | /************************************************************************/ | |
527 | ||
528 | } // end namespace detail | |
529 | ||
530 | template<typename DistributedGraph, typename DijkstraVisitor, | |
531 | typename PredecessorMap, typename DistanceMap, typename WeightMap, | |
532 | typename IndexMap, typename ColorMap, typename Compare, | |
533 | typename Combine, typename DistInf, typename DistZero> | |
534 | void | |
535 | crauser_et_al_shortest_paths | |
536 | (const DistributedGraph& g, | |
537 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
538 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, | |
539 | IndexMap index_map, ColorMap color_map, | |
540 | Compare compare, Combine combine, DistInf inf, DistZero zero, | |
541 | DijkstraVisitor vis) | |
542 | { | |
543 | ||
544 | #ifdef PBGL_ACCOUNTING | |
545 | crauser_et_al_shortest_paths_stats.deleted_vertices.clear(); | |
546 | crauser_et_al_shortest_paths_stats.execution_time = accounting::get_time(); | |
547 | #endif | |
548 | ||
549 | // Property map that stores the lowest edge weight outgoing from | |
550 | // each vertex. If a vertex has no out-edges, the stored weight | |
551 | // is zero. | |
552 | typedef typename property_traits<WeightMap>::value_type weight_type; | |
553 | typedef iterator_property_map<weight_type*, IndexMap> MinOutWeightMap; | |
554 | std::vector<weight_type> min_out_weights_vec(num_vertices(g), inf); | |
555 | MinOutWeightMap min_out_weight(&min_out_weights_vec.front(), index_map); | |
556 | detail::initialize_min_out_weights(g, min_out_weight, weight, compare); | |
557 | ||
558 | // Property map that stores the lowest edge weight incoming to | |
559 | // each vertex. For undirected graphs, this will just be a | |
560 | // shallow copy of the version for outgoing edges. | |
561 | typedef typename graph_traits<DistributedGraph>::directed_category | |
562 | directed_category; | |
563 | const bool is_undirected = | |
564 | is_same<directed_category, undirected_tag>::value; | |
565 | typedef MinOutWeightMap MinInWeightMap; | |
566 | std::vector<weight_type> | |
567 | min_in_weights_vec(is_undirected? 1 : num_vertices(g), inf); | |
568 | MinInWeightMap min_in_weight(&min_in_weights_vec.front(), index_map); | |
569 | typedef typename graph_traits<DistributedGraph>::traversal_category | |
570 | category; | |
571 | detail::initialize_min_in_weights(g, min_in_weight, weight, inf, compare, | |
572 | directed_category(), category()); | |
573 | ||
574 | // Initialize local portion of property maps | |
575 | typename graph_traits<DistributedGraph>::vertex_iterator ui, ui_end; | |
576 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { | |
577 | put(distance, *ui, inf); | |
578 | put(predecessor, *ui, *ui); | |
579 | } | |
580 | put(distance, s, zero); | |
581 | ||
582 | // Dijkstra Queue | |
583 | typedef detail::crauser_et_al_dijkstra_queue | |
584 | <DistributedGraph, Combine, Compare, IndexMap, DistanceMap, | |
585 | PredecessorMap, MinOutWeightMap, MinInWeightMap> | |
586 | Queue; | |
587 | ||
588 | Queue Q(g, combine, compare, index_map, distance, predecessor, | |
589 | min_out_weight, is_undirected? min_out_weight : min_in_weight); | |
590 | ||
591 | // Parallel Dijkstra visitor | |
592 | ::boost::detail::dijkstra_bfs_visitor< | |
593 | DijkstraVisitor, Queue, WeightMap, | |
594 | boost::parallel::caching_property_map<PredecessorMap>, | |
595 | boost::parallel::caching_property_map<DistanceMap>, Combine, Compare | |
596 | > bfs_vis(vis, Q, weight, | |
597 | boost::parallel::make_caching_property_map(predecessor), | |
598 | boost::parallel::make_caching_property_map(distance), | |
599 | combine, compare, zero); | |
600 | ||
601 | set_property_map_role(vertex_color, color_map); | |
602 | set_property_map_role(vertex_distance, distance); | |
603 | ||
604 | breadth_first_search(g, s, Q, bfs_vis, color_map); | |
605 | ||
606 | #ifdef PBGL_ACCOUNTING | |
607 | crauser_et_al_shortest_paths_stats.execution_time = | |
608 | accounting::get_time() - crauser_et_al_shortest_paths_stats.execution_time; | |
609 | #endif | |
610 | } | |
611 | ||
612 | template<typename DistributedGraph, typename PredecessorMap, | |
613 | typename DistanceMap, typename WeightMap> | |
614 | void | |
615 | crauser_et_al_shortest_paths | |
616 | (const DistributedGraph& g, | |
617 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
618 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight) | |
619 | { | |
620 | typedef typename property_traits<DistanceMap>::value_type distance_type; | |
621 | ||
622 | std::vector<default_color_type> colors(num_vertices(g), white_color); | |
623 | ||
624 | crauser_et_al_shortest_paths(g, s, predecessor, distance, weight, | |
625 | get(vertex_index, g), | |
626 | make_iterator_property_map(&colors[0], | |
627 | get(vertex_index, g)), | |
628 | std::less<distance_type>(), | |
629 | closed_plus<distance_type>(), | |
630 | (std::numeric_limits<distance_type>::max)(), | |
631 | distance_type(), | |
632 | dijkstra_visitor<>()); | |
633 | } | |
634 | ||
635 | template<typename DistributedGraph, typename PredecessorMap, | |
636 | typename DistanceMap> | |
637 | void | |
638 | crauser_et_al_shortest_paths | |
639 | (const DistributedGraph& g, | |
640 | typename graph_traits<DistributedGraph>::vertex_descriptor s, | |
641 | PredecessorMap predecessor, DistanceMap distance) | |
642 | { | |
643 | crauser_et_al_shortest_paths(g, s, predecessor, distance, | |
644 | get(edge_weight, g)); | |
645 | } | |
646 | ||
647 | } // end namespace distributed | |
648 | ||
649 | #ifdef PBGL_ACCOUNTING | |
650 | using distributed::crauser_et_al_shortest_paths_stats; | |
651 | #endif | |
652 | ||
653 | using distributed::crauser_et_al_shortest_paths; | |
654 | ||
655 | ||
656 | } } // end namespace boost::graph | |
657 | ||
658 | #endif // BOOST_GRAPH_CRAUSER_ET_AL_SHORTEST_PATHS_HPP |