1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
12 // 04 April 2001: Added named parameter variant. (Jeremy Siek)
13 // 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
15 #ifndef BOOST_GRAPH_DIJKSTRA_HPP
16 #define BOOST_GRAPH_DIJKSTRA_HPP
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/pending/relaxed_heap.hpp>
26 #include <boost/graph/overloading.hpp>
27 #include <boost/smart_ptr.hpp>
28 #include <boost/graph/detail/d_ary_heap.hpp>
29 #include <boost/graph/two_bit_color_map.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>
35 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
36 # include <boost/pending/mutable_queue.hpp>
37 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
42 * @brief Updates a particular value in a queue used by Dijkstra's
45 * This routine is called by Dijkstra's algorithm after it has
46 * decreased the distance from the source vertex to the given @p
47 * vertex. By default, this routine will just call @c
48 * Q.update(vertex). However, other queues may provide more
49 * specialized versions of this routine.
51 * @param Q the queue that will be updated.
52 * @param vertex the vertex whose distance has been updated
53 * @param old_distance the previous distance to @p vertex
55 template<typename Buffer, typename Vertex, typename DistanceType>
57 dijkstra_queue_update(Buffer& Q, Vertex vertex, DistanceType old_distance)
63 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
64 // This is a misnomer now: it now just refers to the "default heap", which is
65 // currently d-ary (d=4) but can be changed by a #define.
66 static bool dijkstra_relaxed_heap = true;
69 template <class Visitor, class Graph>
70 struct DijkstraVisitorConcept {
72 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
73 vis.initialize_vertex(u, g);
74 vis.discover_vertex(u, g);
75 vis.examine_vertex(u, g);
76 vis.examine_edge(e, g);
77 vis.edge_relaxed(e, g);
78 vis.edge_not_relaxed(e, g);
79 vis.finish_vertex(u, g);
83 typename graph_traits<Graph>::vertex_descriptor u;
84 typename graph_traits<Graph>::edge_descriptor e;
87 template <class Visitors = null_visitor>
88 class dijkstra_visitor : public bfs_visitor<Visitors> {
90 dijkstra_visitor() { }
91 dijkstra_visitor(Visitors vis)
92 : bfs_visitor<Visitors>(vis) { }
94 template <class Edge, class Graph>
95 void edge_relaxed(Edge e, Graph& g) {
96 invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
98 template <class Edge, class Graph>
99 void edge_not_relaxed(Edge e, Graph& g) {
100 invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
103 template <class Edge, class Graph>
104 void tree_edge(Edge u, Graph& g) { }
106 template <class Visitors>
107 dijkstra_visitor<Visitors>
108 make_dijkstra_visitor(Visitors vis) {
109 return dijkstra_visitor<Visitors>(vis);
111 typedef dijkstra_visitor<> default_dijkstra_visitor;
115 template <class UniformCostVisitor, class UpdatableQueue,
116 class WeightMap, class PredecessorMap, class DistanceMap,
117 class BinaryFunction, class BinaryPredicate>
118 struct dijkstra_bfs_visitor
120 typedef typename property_traits<DistanceMap>::value_type D;
121 typedef typename property_traits<WeightMap>::value_type W;
123 dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,
124 WeightMap w, PredecessorMap p, DistanceMap d,
125 BinaryFunction combine, BinaryPredicate compare,
127 : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d),
128 m_combine(combine), m_compare(compare), m_zero(zero) { }
130 template <class Edge, class Graph>
131 void tree_edge(Edge e, Graph& g) {
132 bool decreased = relax(e, g, m_weight, m_predecessor, m_distance,
133 m_combine, m_compare);
135 m_vis.edge_relaxed(e, g);
137 m_vis.edge_not_relaxed(e, g);
139 template <class Edge, class Graph>
140 void gray_target(Edge e, Graph& g) {
141 D old_distance = get(m_distance, target(e, g));
143 bool decreased = relax(e, g, m_weight, m_predecessor, m_distance,
144 m_combine, m_compare);
146 dijkstra_queue_update(m_Q, target(e, g), old_distance);
147 m_vis.edge_relaxed(e, g);
149 m_vis.edge_not_relaxed(e, g);
152 template <class Vertex, class Graph>
153 void initialize_vertex(Vertex u, Graph& g)
154 { m_vis.initialize_vertex(u, g); }
155 template <class Edge, class Graph>
156 void non_tree_edge(Edge, Graph&) { }
157 template <class Vertex, class Graph>
158 void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); }
159 template <class Vertex, class Graph>
160 void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
161 template <class Edge, class Graph>
162 void examine_edge(Edge e, Graph& g) {
163 // Test for negative-weight edges:
165 // Reasons that other comparisons do not work:
167 // m_compare(e_weight, D(0)):
168 // m_compare only needs to work on distances, not weights, and those
169 // types do not need to be the same (bug 8398,
170 // https://svn.boost.org/trac/boost/ticket/8398).
171 // m_compare(m_combine(source_dist, e_weight), source_dist):
172 // if m_combine is project2nd (as in prim_minimum_spanning_tree),
173 // this test will claim that the edge weight is negative whenever
174 // the edge weight is less than source_dist, even if both of those
175 // are positive (bug 9012,
176 // https://svn.boost.org/trac/boost/ticket/9012).
177 // m_compare(m_combine(e_weight, source_dist), source_dist):
178 // would fix project2nd issue, but documentation only requires that
179 // m_combine be able to take a distance and a weight (in that order)
180 // and return a distance.
182 // W e_weight = get(m_weight, e);
183 // sd_plus_ew = source_dist + e_weight.
184 // D sd_plus_ew = m_combine(source_dist, e_weight);
185 // sd_plus_2ew = source_dist + 2 * e_weight.
186 // D sd_plus_2ew = m_combine(sd_plus_ew, e_weight);
187 // The test here is equivalent to e_weight < 0 if m_combine has a
188 // cancellation law, but always returns false when m_combine is a
189 // projection operator.
190 if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero))
191 boost::throw_exception(negative_edge());
192 // End of test for negative-weight edges.
194 m_vis.examine_edge(e, g);
197 template <class Edge, class Graph>
198 void black_target(Edge, Graph&) { }
199 template <class Vertex, class Graph>
200 void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); }
202 UniformCostVisitor m_vis;
205 PredecessorMap m_predecessor;
206 DistanceMap m_distance;
207 BinaryFunction m_combine;
208 BinaryPredicate m_compare;
212 } // namespace detail
215 template <class Graph, class IndexMap, class Value, bool KnownNumVertices>
216 struct vertex_property_map_generator_helper {};
218 template <class Graph, class IndexMap, class Value>
219 struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> {
220 typedef boost::iterator_property_map<Value*, IndexMap> type;
221 static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
222 array_holder.reset(new Value[num_vertices(g)]);
223 std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value());
224 return make_iterator_property_map(array_holder.get(), index);
228 template <class Graph, class IndexMap, class Value>
229 struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> {
230 typedef boost::vector_property_map<Value, IndexMap> type;
231 static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
232 return boost::make_vector_property_map<Value>(index);
236 template <class Graph, class IndexMap, class Value>
237 struct vertex_property_map_generator {
238 typedef boost::is_base_and_derived<
239 boost::vertex_list_graph_tag,
240 typename boost::graph_traits<Graph>::traversal_category>
242 typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper;
243 typedef typename helper::type type;
244 static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
245 return helper::build(g, index, array_holder);
251 template <class Graph, class IndexMap, bool KnownNumVertices>
252 struct default_color_map_generator_helper {};
254 template <class Graph, class IndexMap>
255 struct default_color_map_generator_helper<Graph, IndexMap, true> {
256 typedef boost::two_bit_color_map<IndexMap> type;
257 static type build(const Graph& g, const IndexMap& index) {
258 size_t nv = num_vertices(g);
259 return boost::two_bit_color_map<IndexMap>(nv, index);
263 template <class Graph, class IndexMap>
264 struct default_color_map_generator_helper<Graph, IndexMap, false> {
265 typedef boost::vector_property_map<boost::two_bit_color_type, IndexMap> type;
266 static type build(const Graph& g, const IndexMap& index) {
267 return boost::make_vector_property_map<boost::two_bit_color_type>(index);
271 template <class Graph, class IndexMap>
272 struct default_color_map_generator {
273 typedef boost::is_base_and_derived<
274 boost::vertex_list_graph_tag,
275 typename boost::graph_traits<Graph>::traversal_category>
277 typedef default_color_map_generator_helper<Graph, IndexMap, known_num_vertices::value> helper;
278 typedef typename helper::type type;
279 static type build(const Graph& g, const IndexMap& index) {
280 return helper::build(g, index);
285 // Call breadth first search with default color map.
286 template <class Graph, class SourceInputIter, class DijkstraVisitor,
287 class PredecessorMap, class DistanceMap,
288 class WeightMap, class IndexMap, class Compare, class Combine,
291 dijkstra_shortest_paths_no_init
293 SourceInputIter s_begin, SourceInputIter s_end,
294 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
296 Compare compare, Combine combine, DistZero zero,
300 detail::default_color_map_generator<Graph, IndexMap>
302 typedef typename ColorMapHelper::type ColorMap;
304 ColorMapHelper::build(g, index_map);
305 dijkstra_shortest_paths_no_init( g, s_begin, s_end, predecessor, distance, weight,
306 index_map, compare, combine, zero, vis,
310 // Call breadth first search with default color map.
311 template <class Graph, class DijkstraVisitor,
312 class PredecessorMap, class DistanceMap,
313 class WeightMap, class IndexMap, class Compare, class Combine,
316 dijkstra_shortest_paths_no_init
318 typename graph_traits<Graph>::vertex_descriptor s,
319 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
321 Compare compare, Combine combine, DistZero zero,
324 dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
325 weight, index_map, compare, combine, zero,
329 // Call breadth first search
330 template <class Graph, class SourceInputIter, class DijkstraVisitor,
331 class PredecessorMap, class DistanceMap,
332 class WeightMap, class IndexMap, class Compare, class Combine,
333 class DistZero, class ColorMap>
335 dijkstra_shortest_paths_no_init
337 SourceInputIter s_begin, SourceInputIter s_end,
338 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
340 Compare compare, Combine combine, DistZero zero,
341 DijkstraVisitor vis, ColorMap color)
343 typedef indirect_cmp<DistanceMap, Compare> IndirectCmp;
344 IndirectCmp icmp(distance, compare);
346 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
348 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
349 if (!dijkstra_relaxed_heap) {
350 typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap>
353 MutableQueue Q(num_vertices(g), icmp, index_map);
354 detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
355 PredecessorMap, DistanceMap, Combine, Compare>
356 bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
358 breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
361 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
363 #ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
364 typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue;
365 MutableQueue Q(num_vertices(g), icmp, index_map);
366 #else // Now the default: use a d-ary heap
367 boost::scoped_array<std::size_t> index_in_heap_map_holder;
369 detail::vertex_property_map_generator<Graph, IndexMap, std::size_t>
370 IndexInHeapMapHelper;
371 typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
372 IndexInHeapMap index_in_heap =
373 IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder);
374 typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>
376 MutableQueue Q(distance, index_in_heap, compare);
377 #endif // Relaxed heap
379 detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
380 PredecessorMap, DistanceMap, Combine, Compare>
381 bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
383 breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
386 // Call breadth first search
387 template <class Graph, class DijkstraVisitor,
388 class PredecessorMap, class DistanceMap,
389 class WeightMap, class IndexMap, class Compare, class Combine,
390 class DistZero, class ColorMap>
392 dijkstra_shortest_paths_no_init
394 typename graph_traits<Graph>::vertex_descriptor s,
395 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
397 Compare compare, Combine combine, DistZero zero,
398 DijkstraVisitor vis, ColorMap color)
400 dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
401 weight, index_map, compare, combine,
405 // Initialize distances and call breadth first search with default color map
406 template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
407 class PredecessorMap, class DistanceMap,
408 class WeightMap, class IndexMap, class Compare, class Combine,
409 class DistInf, class DistZero, typename T, typename Tag,
412 dijkstra_shortest_paths
413 (const VertexListGraph& g,
414 SourceInputIter s_begin, SourceInputIter s_end,
415 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
417 Compare compare, Combine combine, DistInf inf, DistZero zero,
419 const bgl_named_params<T, Tag, Base>&
420 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
422 boost::two_bit_color_map<IndexMap> color(num_vertices(g), index_map);
423 dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight,
424 index_map, compare, combine, inf, zero, vis,
428 // Initialize distances and call breadth first search with default color map
429 template <class VertexListGraph, class DijkstraVisitor,
430 class PredecessorMap, class DistanceMap,
431 class WeightMap, class IndexMap, class Compare, class Combine,
432 class DistInf, class DistZero, typename T, typename Tag,
435 dijkstra_shortest_paths
436 (const VertexListGraph& g,
437 typename graph_traits<VertexListGraph>::vertex_descriptor s,
438 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
440 Compare compare, Combine combine, DistInf inf, DistZero zero,
442 const bgl_named_params<T, Tag, Base>&
443 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
445 dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
446 index_map, compare, combine, inf, zero, vis);
449 // Initialize distances and call breadth first search
450 template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
451 class PredecessorMap, class DistanceMap,
452 class WeightMap, class IndexMap, class Compare, class Combine,
453 class DistInf, class DistZero, class ColorMap>
455 dijkstra_shortest_paths
456 (const VertexListGraph& g,
457 SourceInputIter s_begin, SourceInputIter s_end,
458 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
460 Compare compare, Combine combine, DistInf inf, DistZero zero,
461 DijkstraVisitor vis, ColorMap color)
463 typedef typename property_traits<ColorMap>::value_type ColorValue;
464 typedef color_traits<ColorValue> Color;
465 typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
466 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
467 vis.initialize_vertex(*ui, g);
468 put(distance, *ui, inf);
469 put(predecessor, *ui, *ui);
470 put(color, *ui, Color::white());
472 for (SourceInputIter it = s_begin; it != s_end; ++it) {
473 put(distance, *it, zero);
476 dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance,
477 weight, index_map, compare, combine, zero, vis,
481 // Initialize distances and call breadth first search
482 template <class VertexListGraph, class DijkstraVisitor,
483 class PredecessorMap, class DistanceMap,
484 class WeightMap, class IndexMap, class Compare, class Combine,
485 class DistInf, class DistZero, class ColorMap>
487 dijkstra_shortest_paths
488 (const VertexListGraph& g,
489 typename graph_traits<VertexListGraph>::vertex_descriptor s,
490 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
492 Compare compare, Combine combine, DistInf inf, DistZero zero,
493 DijkstraVisitor vis, ColorMap color)
495 dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
496 index_map, compare, combine, inf, zero,
500 // Initialize distances and call breadth first search
501 template <class VertexListGraph, class SourceInputIter,
502 class DijkstraVisitor,
503 class PredecessorMap, class DistanceMap,
504 class WeightMap, class IndexMap, class Compare, class Combine,
505 class DistInf, class DistZero>
507 dijkstra_shortest_paths
508 (const VertexListGraph& g,
509 SourceInputIter s_begin, SourceInputIter s_end,
510 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
512 Compare compare, Combine combine, DistInf inf, DistZero zero,
515 dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance,
517 compare, combine, inf, zero, vis,
518 no_named_parameters());
521 // Initialize distances and call breadth first search
522 template <class VertexListGraph, class DijkstraVisitor,
523 class PredecessorMap, class DistanceMap,
524 class WeightMap, class IndexMap, class Compare, class Combine,
525 class DistInf, class DistZero>
527 dijkstra_shortest_paths
528 (const VertexListGraph& g,
529 typename graph_traits<VertexListGraph>::vertex_descriptor s,
530 PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
532 Compare compare, Combine combine, DistInf inf, DistZero zero,
535 dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance,
537 compare, combine, inf, zero, vis);
542 // Handle defaults for PredecessorMap and
543 // Distance Compare, Combine, Inf and Zero
544 template <class VertexListGraph, class DistanceMap, class WeightMap,
545 class IndexMap, class Params>
548 (const VertexListGraph& g,
549 typename graph_traits<VertexListGraph>::vertex_descriptor s,
550 DistanceMap distance, WeightMap weight, IndexMap index_map,
551 const Params& params)
553 // Default for predecessor map
554 dummy_property_map p_map;
556 typedef typename property_traits<DistanceMap>::value_type D;
557 D inf = choose_param(get_param(params, distance_inf_t()),
558 (std::numeric_limits<D>::max)());
560 dijkstra_shortest_paths
562 choose_param(get_param(params, vertex_predecessor), p_map),
563 distance, weight, index_map,
564 choose_param(get_param(params, distance_compare_t()),
566 choose_param(get_param(params, distance_combine_t()),
567 closed_plus<D>(inf)),
569 choose_param(get_param(params, distance_zero_t()),
571 choose_param(get_param(params, graph_visitor),
572 make_dijkstra_visitor(null_visitor())),
576 template <class VertexListGraph, class DistanceMap, class WeightMap,
577 class IndexMap, class Params>
580 (const VertexListGraph& g,
581 typename graph_traits<VertexListGraph>::vertex_descriptor s,
582 DistanceMap distance, WeightMap weight, IndexMap index_map,
583 const Params& params)
585 // Default for distance map
586 typedef typename property_traits<WeightMap>::value_type D;
587 typename std::vector<D>::size_type
588 n = is_default_param(distance) ? num_vertices(g) : 1;
589 std::vector<D> distance_map(n);
591 detail::dijkstra_dispatch2
592 (g, s, choose_param(distance, make_iterator_property_map
593 (distance_map.begin(), index_map,
595 weight, index_map, params);
597 } // namespace detail
599 // Named Parameter Variant
600 template <class VertexListGraph, class Param, class Tag, class Rest>
602 dijkstra_shortest_paths
603 (const VertexListGraph& g,
604 typename graph_traits<VertexListGraph>::vertex_descriptor s,
605 const bgl_named_params<Param,Tag,Rest>& params)
607 // Default for edge weight and vertex index map is to ask for them
608 // from the graph. Default for the visitor is null_visitor.
609 detail::dijkstra_dispatch1
611 get_param(params, vertex_distance),
612 choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
613 choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
619 #ifdef BOOST_GRAPH_USE_MPI
620 # include <boost/graph/distributed/dijkstra_shortest_paths.hpp>
623 #endif // BOOST_GRAPH_DIJKSTRA_HPP