1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | // |
10 | // |
11 | // Revision History: |
12 | // 04 April 2001: Added named parameter variant. (Jeremy Siek) |
13 | // 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock) |
14 | // |
15 | #ifndef BOOST_GRAPH_DIJKSTRA_HPP |
16 | #define BOOST_GRAPH_DIJKSTRA_HPP |
17 | |
18 | #include <functional> |
19 | #include <boost/limits.hpp> |
20 | #include <boost/graph/named_function_params.hpp> |
21 | #include <boost/graph/breadth_first_search.hpp> |
22 | #include <boost/graph/relax.hpp> |
23 | #include <boost/pending/indirect_cmp.hpp> |
24 | #include <boost/graph/exception.hpp> |
25 | #include <boost/graph/overloading.hpp> |
26 | #include <boost/smart_ptr.hpp> |
27 | #include <boost/graph/detail/d_ary_heap.hpp> |
28 | #include <boost/graph/two_bit_color_map.hpp> |
29 | #include <boost/graph/detail/mpi_include.hpp> |
30 | #include <boost/property_map/property_map.hpp> |
31 | #include <boost/property_map/vector_property_map.hpp> |
32 | #include <boost/type_traits.hpp> |
33 | #include <boost/concept/assert.hpp> |
34 | |
35 | #ifdef BOOST_GRAPH_DIJKSTRA_TESTING |
36 | #include <boost/pending/mutable_queue.hpp> |
37 | #endif // BOOST_GRAPH_DIJKSTRA_TESTING |
38 | |
39 | namespace boost |
40 | { |
41 | |
42 | /** |
43 | * @brief Updates a particular value in a queue used by Dijkstra's |
44 | * algorithm. |
45 | * |
46 | * This routine is called by Dijkstra's algorithm after it has |
47 | * decreased the distance from the source vertex to the given @p |
48 | * vertex. By default, this routine will just call @c |
49 | * Q.update(vertex). However, other queues may provide more |
50 | * specialized versions of this routine. |
51 | * |
52 | * @param Q the queue that will be updated. |
53 | * @param vertex the vertex whose distance has been updated |
54 | * @param old_distance the previous distance to @p vertex |
55 | */ |
56 | template < typename Buffer, typename Vertex, typename DistanceType > |
57 | inline void dijkstra_queue_update( |
58 | Buffer& Q, Vertex vertex, DistanceType old_distance) |
59 | { |
60 | (void)old_distance; |
61 | Q.update(vertex); |
62 | } |
63 | |
64 | template < class Visitor, class Graph > struct DijkstraVisitorConcept |
65 | { |
66 | void constraints() |
67 | { |
68 | BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >)); |
69 | vis.initialize_vertex(u, g); |
70 | vis.discover_vertex(u, g); |
71 | vis.examine_vertex(u, g); |
72 | vis.examine_edge(e, g); |
73 | vis.edge_relaxed(e, g); |
74 | vis.edge_not_relaxed(e, g); |
75 | vis.finish_vertex(u, g); |
76 | } |
77 | Visitor vis; |
78 | Graph g; |
79 | typename graph_traits< Graph >::vertex_descriptor u; |
80 | typename graph_traits< Graph >::edge_descriptor e; |
81 | }; |
82 | |
83 | template < class Visitors = null_visitor > |
84 | class dijkstra_visitor : public bfs_visitor< Visitors > |
85 | { |
86 | public: |
87 | dijkstra_visitor() {} |
88 | dijkstra_visitor(Visitors vis) : bfs_visitor< Visitors >(vis) {} |
89 | |
90 | template < class Edge, class Graph > void edge_relaxed(Edge e, Graph& g) |
91 | { |
92 | invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); |
93 | } |
94 | template < class Edge, class Graph > void edge_not_relaxed(Edge e, Graph& g) |
95 | { |
96 | invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); |
97 | } |
98 | |
99 | private: |
100 | template < class Edge, class Graph > void tree_edge(Edge u, Graph& g) {} |
101 | }; |
102 | template < class Visitors > |
103 | dijkstra_visitor< Visitors > make_dijkstra_visitor(Visitors vis) |
104 | { |
105 | return dijkstra_visitor< Visitors >(vis); |
106 | } |
107 | typedef dijkstra_visitor<> default_dijkstra_visitor; |
108 | |
109 | namespace detail |
110 | { |
111 | |
112 | template < class UniformCostVisitor, class UpdatableQueue, class WeightMap, |
113 | class PredecessorMap, class DistanceMap, class BinaryFunction, |
114 | class BinaryPredicate > |
115 | struct dijkstra_bfs_visitor |
116 | { |
117 | typedef typename property_traits< DistanceMap >::value_type D; |
118 | typedef typename property_traits< WeightMap >::value_type W; |
119 | |
120 | dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q, |
121 | WeightMap w, PredecessorMap p, DistanceMap d, |
122 | BinaryFunction combine, BinaryPredicate compare, D zero) |
123 | : m_vis(vis) |
124 | , m_Q(Q) |
125 | , m_weight(w) |
126 | , m_predecessor(p) |
127 | , m_distance(d) |
128 | , m_combine(combine) |
129 | , m_compare(compare) |
130 | , m_zero(zero) |
131 | { |
132 | } |
133 | |
134 | template < class Edge, class Graph > void tree_edge(Edge e, Graph& g) |
135 | { |
136 | bool decreased = relax_target(e, g, m_weight, m_predecessor, |
137 | m_distance, m_combine, m_compare); |
138 | if (decreased) |
139 | m_vis.edge_relaxed(e, g); |
140 | else |
141 | m_vis.edge_not_relaxed(e, g); |
142 | } |
143 | template < class Edge, class Graph > void gray_target(Edge e, Graph& g) |
144 | { |
145 | D old_distance = get(m_distance, target(e, g)); |
146 | |
147 | bool decreased = relax_target(e, g, m_weight, m_predecessor, |
148 | m_distance, m_combine, m_compare); |
149 | if (decreased) |
150 | { |
151 | dijkstra_queue_update(m_Q, target(e, g), old_distance); |
152 | m_vis.edge_relaxed(e, g); |
153 | } |
154 | else |
155 | m_vis.edge_not_relaxed(e, g); |
156 | } |
157 | |
158 | template < class Vertex, class Graph > |
159 | void initialize_vertex(Vertex u, Graph& g) |
160 | { |
161 | m_vis.initialize_vertex(u, g); |
162 | } |
163 | template < class Edge, class Graph > void non_tree_edge(Edge, Graph&) {} |
164 | template < class Vertex, class Graph > |
165 | void discover_vertex(Vertex u, Graph& g) |
166 | { |
167 | m_vis.discover_vertex(u, g); |
168 | } |
169 | template < class Vertex, class Graph > |
170 | void examine_vertex(Vertex u, Graph& g) |
171 | { |
172 | m_vis.examine_vertex(u, g); |
173 | } |
174 | template < class Edge, class Graph > void examine_edge(Edge e, Graph& g) |
175 | { |
176 | // Test for negative-weight edges: |
177 | // |
178 | // Reasons that other comparisons do not work: |
179 | // |
180 | // m_compare(e_weight, D(0)): |
181 | // m_compare only needs to work on distances, not weights, and |
182 | // those types do not need to be the same (bug 8398, |
183 | // https://svn.boost.org/trac/boost/ticket/8398). |
184 | // m_compare(m_combine(source_dist, e_weight), source_dist): |
185 | // if m_combine is project2nd (as in prim_minimum_spanning_tree), |
186 | // this test will claim that the edge weight is negative whenever |
187 | // the edge weight is less than source_dist, even if both of |
188 | // those are positive (bug 9012, |
189 | // https://svn.boost.org/trac/boost/ticket/9012). |
190 | // m_compare(m_combine(e_weight, source_dist), source_dist): |
191 | // would fix project2nd issue, but documentation only requires |
192 | // that m_combine be able to take a distance and a weight (in |
193 | // that order) and return a distance. |
194 | |
195 | // W e_weight = get(m_weight, e); |
196 | // sd_plus_ew = source_dist + e_weight. |
197 | // D sd_plus_ew = m_combine(source_dist, e_weight); |
198 | // sd_plus_2ew = source_dist + 2 * e_weight. |
199 | // D sd_plus_2ew = m_combine(sd_plus_ew, e_weight); |
200 | // The test here is equivalent to e_weight < 0 if m_combine has a |
201 | // cancellation law, but always returns false when m_combine is a |
202 | // projection operator. |
203 | if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero)) |
204 | boost::throw_exception(e: negative_edge()); |
205 | // End of test for negative-weight edges. |
206 | |
207 | m_vis.examine_edge(e, g); |
208 | } |
209 | template < class Edge, class Graph > void black_target(Edge, Graph&) {} |
210 | template < class Vertex, class Graph > |
211 | void finish_vertex(Vertex u, Graph& g) |
212 | { |
213 | m_vis.finish_vertex(u, g); |
214 | } |
215 | |
216 | UniformCostVisitor m_vis; |
217 | UpdatableQueue& m_Q; |
218 | WeightMap m_weight; |
219 | PredecessorMap m_predecessor; |
220 | DistanceMap m_distance; |
221 | BinaryFunction m_combine; |
222 | BinaryPredicate m_compare; |
223 | D m_zero; |
224 | }; |
225 | |
226 | } // namespace detail |
227 | |
228 | namespace detail |
229 | { |
230 | template < class Graph, class IndexMap, class Value, bool KnownNumVertices > |
231 | struct vertex_property_map_generator_helper |
232 | { |
233 | }; |
234 | |
235 | template < class Graph, class IndexMap, class Value > |
236 | struct vertex_property_map_generator_helper< Graph, IndexMap, Value, true > |
237 | { |
238 | typedef boost::iterator_property_map< Value*, IndexMap > type; |
239 | static type build(const Graph& g, const IndexMap& index, |
240 | boost::scoped_array< Value >& array_holder) |
241 | { |
242 | array_holder.reset(new Value[num_vertices(g)]); |
243 | std::fill(array_holder.get(), array_holder.get() + num_vertices(g), |
244 | Value()); |
245 | return make_iterator_property_map(array_holder.get(), index); |
246 | } |
247 | }; |
248 | |
249 | template < class Graph, class IndexMap, class Value > |
250 | struct vertex_property_map_generator_helper< Graph, IndexMap, Value, false > |
251 | { |
252 | typedef boost::vector_property_map< Value, IndexMap > type; |
253 | static type build(const Graph& g, const IndexMap& index, |
254 | boost::scoped_array< Value >& array_holder) |
255 | { |
256 | return boost::make_vector_property_map< Value >(index); |
257 | } |
258 | }; |
259 | |
260 | template < class Graph, class IndexMap, class Value > |
261 | struct vertex_property_map_generator |
262 | { |
263 | typedef boost::is_base_and_derived< boost::vertex_list_graph_tag, |
264 | typename boost::graph_traits< Graph >::traversal_category > |
265 | known_num_vertices; |
266 | typedef vertex_property_map_generator_helper< Graph, IndexMap, Value, |
267 | known_num_vertices::value > |
268 | helper; |
269 | typedef typename helper::type type; |
270 | static type build(const Graph& g, const IndexMap& index, |
271 | boost::scoped_array< Value >& array_holder) |
272 | { |
273 | return helper::build(g, index, array_holder); |
274 | } |
275 | }; |
276 | } |
277 | |
278 | namespace detail |
279 | { |
280 | template < class Graph, class IndexMap, bool KnownNumVertices > |
281 | struct default_color_map_generator_helper |
282 | { |
283 | }; |
284 | |
285 | template < class Graph, class IndexMap > |
286 | struct default_color_map_generator_helper< Graph, IndexMap, true > |
287 | { |
288 | typedef boost::two_bit_color_map< IndexMap > type; |
289 | static type build(const Graph& g, const IndexMap& index) |
290 | { |
291 | size_t nv = num_vertices(g); |
292 | return boost::two_bit_color_map< IndexMap >(nv, index); |
293 | } |
294 | }; |
295 | |
296 | template < class Graph, class IndexMap > |
297 | struct default_color_map_generator_helper< Graph, IndexMap, false > |
298 | { |
299 | typedef boost::vector_property_map< boost::two_bit_color_type, |
300 | IndexMap > |
301 | type; |
302 | static type build(const Graph& g, const IndexMap& index) |
303 | { |
304 | return boost::make_vector_property_map< boost::two_bit_color_type >( |
305 | index); |
306 | } |
307 | }; |
308 | |
309 | template < class Graph, class IndexMap > struct default_color_map_generator |
310 | { |
311 | typedef boost::is_base_and_derived< boost::vertex_list_graph_tag, |
312 | typename boost::graph_traits< Graph >::traversal_category > |
313 | known_num_vertices; |
314 | typedef default_color_map_generator_helper< Graph, IndexMap, |
315 | known_num_vertices::value > |
316 | helper; |
317 | typedef typename helper::type type; |
318 | static type build(const Graph& g, const IndexMap& index) |
319 | { |
320 | return helper::build(g, index); |
321 | } |
322 | }; |
323 | } |
324 | |
325 | // Call breadth first search with default color map. |
326 | template < class Graph, class SourceInputIter, class DijkstraVisitor, |
327 | class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, |
328 | class Compare, class Combine, class DistZero > |
329 | inline void dijkstra_shortest_paths_no_init(const Graph& g, |
330 | SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, |
331 | DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, |
332 | Combine combine, DistZero zero, DijkstraVisitor vis) |
333 | { |
334 | typedef detail::default_color_map_generator< Graph, IndexMap > |
335 | ColorMapHelper; |
336 | typedef typename ColorMapHelper::type ColorMap; |
337 | ColorMap color = ColorMapHelper::build(g, index_map); |
338 | dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance, |
339 | weight, index_map, compare, combine, zero, vis, color); |
340 | } |
341 | |
342 | // Call breadth first search with default color map. |
343 | template < class Graph, class DijkstraVisitor, class PredecessorMap, |
344 | class DistanceMap, class WeightMap, class IndexMap, class Compare, |
345 | class Combine, class DistZero > |
346 | inline void dijkstra_shortest_paths_no_init(const Graph& g, |
347 | typename graph_traits< Graph >::vertex_descriptor s, |
348 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
349 | IndexMap index_map, Compare compare, Combine combine, DistZero zero, |
350 | DijkstraVisitor vis) |
351 | { |
352 | dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance, |
353 | weight, index_map, compare, combine, zero, vis); |
354 | } |
355 | |
356 | // Call breadth first search |
357 | template < class Graph, class SourceInputIter, class DijkstraVisitor, |
358 | class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, |
359 | class Compare, class Combine, class DistZero, class ColorMap > |
360 | inline void dijkstra_shortest_paths_no_init(const Graph& g, |
361 | SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, |
362 | DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, |
363 | Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color) |
364 | { |
365 | typedef indirect_cmp< DistanceMap, Compare > IndirectCmp; |
366 | IndirectCmp icmp(distance, compare); |
367 | |
368 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; |
369 | |
370 | // Now the default: use a d-ary heap |
371 | boost::scoped_array< std::size_t > index_in_heap_map_holder; |
372 | typedef detail::vertex_property_map_generator< Graph, IndexMap, |
373 | std::size_t > |
374 | IndexInHeapMapHelper; |
375 | typedef typename IndexInHeapMapHelper::type IndexInHeapMap; |
376 | IndexInHeapMap index_in_heap |
377 | = IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder); |
378 | typedef d_ary_heap_indirect< Vertex, 4, IndexInHeapMap, DistanceMap, |
379 | Compare > |
380 | MutableQueue; |
381 | MutableQueue Q(distance, index_in_heap, compare); |
382 | |
383 | detail::dijkstra_bfs_visitor< DijkstraVisitor, MutableQueue, WeightMap, |
384 | PredecessorMap, DistanceMap, Combine, Compare > |
385 | bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); |
386 | |
387 | breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color); |
388 | } |
389 | |
390 | // Call breadth first search |
391 | template < class Graph, class DijkstraVisitor, class PredecessorMap, |
392 | class DistanceMap, class WeightMap, class IndexMap, class Compare, |
393 | class Combine, class DistZero, class ColorMap > |
394 | inline void dijkstra_shortest_paths_no_init(const Graph& g, |
395 | typename graph_traits< Graph >::vertex_descriptor s, |
396 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
397 | IndexMap index_map, Compare compare, Combine combine, DistZero zero, |
398 | DijkstraVisitor vis, ColorMap color) |
399 | { |
400 | dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance, |
401 | weight, index_map, compare, combine, zero, vis, color); |
402 | } |
403 | |
404 | // Initialize distances and call breadth first search with default color map |
405 | template < class VertexListGraph, class SourceInputIter, class DijkstraVisitor, |
406 | class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, |
407 | class Compare, class Combine, class DistInf, class DistZero, typename T, |
408 | typename Tag, typename Base > |
409 | inline void dijkstra_shortest_paths(const VertexListGraph& g, |
410 | SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, |
411 | DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, |
412 | Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis, |
413 | const bgl_named_params< T, Tag, Base >& BOOST_GRAPH_ENABLE_IF_MODELS_PARM( |
414 | VertexListGraph, vertex_list_graph_tag)) |
415 | { |
416 | boost::two_bit_color_map< IndexMap > color(num_vertices(g), index_map); |
417 | dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight, |
418 | index_map, compare, combine, inf, zero, vis, color); |
419 | } |
420 | |
421 | // Initialize distances and call breadth first search with default color map |
422 | template < class VertexListGraph, class DijkstraVisitor, class PredecessorMap, |
423 | class DistanceMap, class WeightMap, class IndexMap, class Compare, |
424 | class Combine, class DistInf, class DistZero, typename T, typename Tag, |
425 | typename Base > |
426 | inline void dijkstra_shortest_paths(const VertexListGraph& g, |
427 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
428 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
429 | IndexMap index_map, Compare compare, Combine combine, DistInf inf, |
430 | DistZero zero, DijkstraVisitor vis, |
431 | const bgl_named_params< T, Tag, Base >& BOOST_GRAPH_ENABLE_IF_MODELS_PARM( |
432 | VertexListGraph, vertex_list_graph_tag)) |
433 | { |
434 | dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight, |
435 | index_map, compare, combine, inf, zero, vis); |
436 | } |
437 | |
438 | // Initialize distances and call breadth first search |
439 | template < class VertexListGraph, class SourceInputIter, class DijkstraVisitor, |
440 | class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, |
441 | class Compare, class Combine, class DistInf, class DistZero, |
442 | class ColorMap > |
443 | inline void dijkstra_shortest_paths(const VertexListGraph& g, |
444 | SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, |
445 | DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, |
446 | Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis, |
447 | ColorMap color) |
448 | { |
449 | typedef typename property_traits< ColorMap >::value_type ColorValue; |
450 | typedef color_traits< ColorValue > Color; |
451 | typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end; |
452 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
453 | { |
454 | vis.initialize_vertex(*ui, g); |
455 | put(distance, *ui, inf); |
456 | put(predecessor, *ui, *ui); |
457 | put(color, *ui, Color::white()); |
458 | } |
459 | for (SourceInputIter it = s_begin; it != s_end; ++it) |
460 | { |
461 | put(distance, *it, zero); |
462 | } |
463 | |
464 | dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance, |
465 | weight, index_map, compare, combine, zero, vis, color); |
466 | } |
467 | |
468 | // Initialize distances and call breadth first search |
469 | template < class VertexListGraph, class DijkstraVisitor, class PredecessorMap, |
470 | class DistanceMap, class WeightMap, class IndexMap, class Compare, |
471 | class Combine, class DistInf, class DistZero, class ColorMap > |
472 | inline void dijkstra_shortest_paths(const VertexListGraph& g, |
473 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
474 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
475 | IndexMap index_map, Compare compare, Combine combine, DistInf inf, |
476 | DistZero zero, DijkstraVisitor vis, ColorMap color) |
477 | { |
478 | dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight, |
479 | index_map, compare, combine, inf, zero, vis, color); |
480 | } |
481 | |
482 | // Initialize distances and call breadth first search |
483 | template < class VertexListGraph, class SourceInputIter, class DijkstraVisitor, |
484 | class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, |
485 | class Compare, class Combine, class DistInf, class DistZero > |
486 | inline void dijkstra_shortest_paths(const VertexListGraph& g, |
487 | SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, |
488 | DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, |
489 | Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) |
490 | { |
491 | dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight, |
492 | index_map, compare, combine, inf, zero, vis, no_named_parameters()); |
493 | } |
494 | |
495 | // Initialize distances and call breadth first search |
496 | template < class VertexListGraph, class DijkstraVisitor, class PredecessorMap, |
497 | class DistanceMap, class WeightMap, class IndexMap, class Compare, |
498 | class Combine, class DistInf, class DistZero > |
499 | inline void dijkstra_shortest_paths(const VertexListGraph& g, |
500 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
501 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
502 | IndexMap index_map, Compare compare, Combine combine, DistInf inf, |
503 | DistZero zero, DijkstraVisitor vis) |
504 | { |
505 | dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight, |
506 | index_map, compare, combine, inf, zero, vis); |
507 | } |
508 | |
509 | namespace detail |
510 | { |
511 | |
512 | // Handle defaults for PredecessorMap and |
513 | // Distance Compare, Combine, Inf and Zero |
514 | template < class VertexListGraph, class DistanceMap, class WeightMap, |
515 | class IndexMap, class Params > |
516 | inline void dijkstra_dispatch2(const VertexListGraph& g, |
517 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
518 | DistanceMap distance, WeightMap weight, IndexMap index_map, |
519 | const Params& params) |
520 | { |
521 | // Default for predecessor map |
522 | dummy_property_map p_map; |
523 | |
524 | typedef typename property_traits< DistanceMap >::value_type D; |
525 | D inf = choose_param(get_param(params, distance_inf_t()), |
526 | (std::numeric_limits< D >::max)()); |
527 | |
528 | dijkstra_shortest_paths(g, s, |
529 | choose_param(get_param(params, vertex_predecessor), p_map), |
530 | distance, weight, index_map, |
531 | choose_param( |
532 | get_param(params, distance_compare_t()), std::less< D >()), |
533 | choose_param( |
534 | get_param(params, distance_combine_t()), std::plus< D >()), |
535 | inf, choose_param(get_param(params, distance_zero_t()), D()), |
536 | choose_param(get_param(params, graph_visitor), |
537 | make_dijkstra_visitor(vis: null_visitor())), |
538 | params); |
539 | } |
540 | |
541 | template < class VertexListGraph, class DistanceMap, class WeightMap, |
542 | class IndexMap, class Params > |
543 | inline void dijkstra_dispatch1(const VertexListGraph& g, |
544 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
545 | DistanceMap distance, WeightMap weight, IndexMap index_map, |
546 | const Params& params) |
547 | { |
548 | // Default for distance map |
549 | typedef typename property_traits< WeightMap >::value_type D; |
550 | typename std::vector< D >::size_type n |
551 | = is_default_param(distance) ? num_vertices(g) : 1; |
552 | std::vector< D > distance_map(n); |
553 | |
554 | detail::dijkstra_dispatch2(g, s, |
555 | choose_param(distance, |
556 | make_iterator_property_map( |
557 | distance_map.begin(), index_map, distance_map[0])), |
558 | weight, index_map, params); |
559 | } |
560 | } // namespace detail |
561 | |
562 | // Named Parameter Variant |
563 | template < class VertexListGraph, class Param, class Tag, class Rest > |
564 | inline void dijkstra_shortest_paths(const VertexListGraph& g, |
565 | typename graph_traits< VertexListGraph >::vertex_descriptor s, |
566 | const bgl_named_params< Param, Tag, Rest >& params) |
567 | { |
568 | // Default for edge weight and vertex index map is to ask for them |
569 | // from the graph. Default for the visitor is null_visitor. |
570 | detail::dijkstra_dispatch1(g, s, get_param(params, vertex_distance), |
571 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
572 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
573 | params); |
574 | } |
575 | |
576 | } // namespace boost |
577 | |
578 | #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/dijkstra_shortest_paths.hpp>) |
579 | |
580 | #endif // BOOST_GRAPH_DIJKSTRA_HPP |
581 | |