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/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> |
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 | * @brief Updates a particular value in a queue used by Dijkstra's |
43 | * algorithm. |
44 | * |
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. |
50 | * |
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 |
54 | */ |
55 | template<typename Buffer, typename Vertex, typename DistanceType> |
56 | inline void |
57 | dijkstra_queue_update(Buffer& Q, Vertex vertex, DistanceType old_distance) |
58 | { |
59 | (void)old_distance; |
60 | Q.update(vertex); |
61 | } |
62 | |
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; |
67 | #endif |
68 | |
69 | template <class Visitor, class Graph> |
70 | struct DijkstraVisitorConcept { |
71 | void constraints() { |
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); |
80 | } |
81 | Visitor vis; |
82 | Graph g; |
83 | typename graph_traits<Graph>::vertex_descriptor u; |
84 | typename graph_traits<Graph>::edge_descriptor e; |
85 | }; |
86 | |
87 | template <class Visitors = null_visitor> |
88 | class dijkstra_visitor : public bfs_visitor<Visitors> { |
89 | public: |
90 | dijkstra_visitor() { } |
91 | dijkstra_visitor(Visitors vis) |
92 | : bfs_visitor<Visitors>(vis) { } |
93 | |
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()); |
97 | } |
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()); |
101 | } |
102 | private: |
103 | template <class Edge, class Graph> |
104 | void tree_edge(Edge u, Graph& g) { } |
105 | }; |
106 | template <class Visitors> |
107 | dijkstra_visitor<Visitors> |
108 | make_dijkstra_visitor(Visitors vis) { |
109 | return dijkstra_visitor<Visitors>(vis); |
110 | } |
111 | typedef dijkstra_visitor<> default_dijkstra_visitor; |
112 | |
113 | namespace detail { |
114 | |
115 | template <class UniformCostVisitor, class UpdatableQueue, |
116 | class WeightMap, class PredecessorMap, class DistanceMap, |
117 | class BinaryFunction, class BinaryPredicate> |
118 | struct dijkstra_bfs_visitor |
119 | { |
120 | typedef typename property_traits<DistanceMap>::value_type D; |
121 | typedef typename property_traits<WeightMap>::value_type W; |
122 | |
123 | dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q, |
124 | WeightMap w, PredecessorMap p, DistanceMap d, |
125 | BinaryFunction combine, BinaryPredicate compare, |
126 | D zero) |
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) { } |
129 | |
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); |
134 | if (decreased) |
135 | m_vis.edge_relaxed(e, g); |
136 | else |
137 | m_vis.edge_not_relaxed(e, g); |
138 | } |
139 | template <class Edge, class Graph> |
140 | void gray_target(Edge e, Graph& g) { |
141 | D old_distance = get(m_distance, target(e, g)); |
142 | |
143 | bool decreased = relax(e, g, m_weight, m_predecessor, m_distance, |
144 | m_combine, m_compare); |
145 | if (decreased) { |
146 | dijkstra_queue_update(m_Q, target(e, g), old_distance); |
147 | m_vis.edge_relaxed(e, g); |
148 | } else |
149 | m_vis.edge_not_relaxed(e, g); |
150 | } |
151 | |
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: |
164 | // |
165 | // Reasons that other comparisons do not work: |
166 | // |
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. |
181 | |
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(e: negative_edge()); |
192 | // End of test for negative-weight edges. |
193 | |
194 | m_vis.examine_edge(e, g); |
195 | |
196 | } |
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); } |
201 | |
202 | UniformCostVisitor m_vis; |
203 | UpdatableQueue& m_Q; |
204 | WeightMap m_weight; |
205 | PredecessorMap m_predecessor; |
206 | DistanceMap m_distance; |
207 | BinaryFunction m_combine; |
208 | BinaryPredicate m_compare; |
209 | D m_zero; |
210 | }; |
211 | |
212 | } // namespace detail |
213 | |
214 | namespace detail { |
215 | template <class Graph, class IndexMap, class Value, bool KnownNumVertices> |
216 | struct vertex_property_map_generator_helper {}; |
217 | |
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); |
225 | } |
226 | }; |
227 | |
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); |
233 | } |
234 | }; |
235 | |
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> |
241 | known_num_vertices; |
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); |
246 | } |
247 | }; |
248 | } |
249 | |
250 | namespace detail { |
251 | template <class Graph, class IndexMap, bool KnownNumVertices> |
252 | struct default_color_map_generator_helper {}; |
253 | |
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); |
260 | } |
261 | }; |
262 | |
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); |
268 | } |
269 | }; |
270 | |
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> |
276 | known_num_vertices; |
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); |
281 | } |
282 | }; |
283 | } |
284 | |
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, |
289 | class DistZero> |
290 | inline void |
291 | dijkstra_shortest_paths_no_init |
292 | (const Graph& g, |
293 | SourceInputIter s_begin, SourceInputIter s_end, |
294 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
295 | IndexMap index_map, |
296 | Compare compare, Combine combine, DistZero zero, |
297 | DijkstraVisitor vis) |
298 | { |
299 | typedef |
300 | detail::default_color_map_generator<Graph, IndexMap> |
301 | ColorMapHelper; |
302 | typedef typename ColorMapHelper::type ColorMap; |
303 | ColorMap color = |
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, |
307 | color); |
308 | } |
309 | |
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, |
314 | class DistZero> |
315 | inline void |
316 | dijkstra_shortest_paths_no_init |
317 | (const Graph& g, |
318 | typename graph_traits<Graph>::vertex_descriptor s, |
319 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
320 | IndexMap index_map, |
321 | Compare compare, Combine combine, DistZero zero, |
322 | DijkstraVisitor vis) |
323 | { |
324 | dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance, |
325 | weight, index_map, compare, combine, zero, |
326 | vis); |
327 | } |
328 | |
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> |
334 | inline void |
335 | dijkstra_shortest_paths_no_init |
336 | (const Graph& g, |
337 | SourceInputIter s_begin, SourceInputIter s_end, |
338 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
339 | IndexMap index_map, |
340 | Compare compare, Combine combine, DistZero zero, |
341 | DijkstraVisitor vis, ColorMap color) |
342 | { |
343 | typedef indirect_cmp<DistanceMap, Compare> IndirectCmp; |
344 | IndirectCmp icmp(distance, compare); |
345 | |
346 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
347 | |
348 | #ifdef BOOST_GRAPH_DIJKSTRA_TESTING |
349 | if (!dijkstra_relaxed_heap) { |
350 | typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap> |
351 | MutableQueue; |
352 | |
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); |
357 | |
358 | breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color); |
359 | return; |
360 | } |
361 | #endif // BOOST_GRAPH_DIJKSTRA_TESTING |
362 | |
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; |
368 | typedef |
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> |
375 | MutableQueue; |
376 | MutableQueue Q(distance, index_in_heap, compare); |
377 | #endif // Relaxed heap |
378 | |
379 | detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, |
380 | PredecessorMap, DistanceMap, Combine, Compare> |
381 | bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero); |
382 | |
383 | breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color); |
384 | } |
385 | |
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> |
391 | inline void |
392 | dijkstra_shortest_paths_no_init |
393 | (const Graph& g, |
394 | typename graph_traits<Graph>::vertex_descriptor s, |
395 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
396 | IndexMap index_map, |
397 | 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, |
402 | zero, vis, color); |
403 | } |
404 | |
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, |
410 | typename Base> |
411 | inline void |
412 | dijkstra_shortest_paths |
413 | (const VertexListGraph& g, |
414 | SourceInputIter s_begin, SourceInputIter s_end, |
415 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
416 | IndexMap index_map, |
417 | Compare compare, Combine combine, DistInf inf, DistZero zero, |
418 | DijkstraVisitor vis, |
419 | const bgl_named_params<T, Tag, Base>& |
420 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag)) |
421 | { |
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, |
425 | color); |
426 | } |
427 | |
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, |
433 | typename Base> |
434 | inline void |
435 | dijkstra_shortest_paths |
436 | (const VertexListGraph& g, |
437 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
438 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
439 | IndexMap index_map, |
440 | Compare compare, Combine combine, DistInf inf, DistZero zero, |
441 | DijkstraVisitor vis, |
442 | const bgl_named_params<T, Tag, Base>& |
443 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag)) |
444 | { |
445 | dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight, |
446 | index_map, compare, combine, inf, zero, vis); |
447 | } |
448 | |
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> |
454 | inline void |
455 | dijkstra_shortest_paths |
456 | (const VertexListGraph& g, |
457 | SourceInputIter s_begin, SourceInputIter s_end, |
458 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
459 | IndexMap index_map, |
460 | Compare compare, Combine combine, DistInf inf, DistZero zero, |
461 | DijkstraVisitor vis, ColorMap color) |
462 | { |
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()); |
471 | } |
472 | for (SourceInputIter it = s_begin; it != s_end; ++it) { |
473 | put(distance, *it, zero); |
474 | } |
475 | |
476 | dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance, |
477 | weight, index_map, compare, combine, zero, vis, |
478 | color); |
479 | } |
480 | |
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> |
486 | inline void |
487 | dijkstra_shortest_paths |
488 | (const VertexListGraph& g, |
489 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
490 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
491 | IndexMap index_map, |
492 | Compare compare, Combine combine, DistInf inf, DistZero zero, |
493 | DijkstraVisitor vis, ColorMap color) |
494 | { |
495 | dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight, |
496 | index_map, compare, combine, inf, zero, |
497 | vis, color); |
498 | } |
499 | |
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> |
506 | inline void |
507 | dijkstra_shortest_paths |
508 | (const VertexListGraph& g, |
509 | SourceInputIter s_begin, SourceInputIter s_end, |
510 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
511 | IndexMap index_map, |
512 | Compare compare, Combine combine, DistInf inf, DistZero zero, |
513 | DijkstraVisitor vis) |
514 | { |
515 | dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, |
516 | weight, index_map, |
517 | compare, combine, inf, zero, vis, |
518 | no_named_parameters()); |
519 | } |
520 | |
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> |
526 | inline void |
527 | dijkstra_shortest_paths |
528 | (const VertexListGraph& g, |
529 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
530 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight, |
531 | IndexMap index_map, |
532 | Compare compare, Combine combine, DistInf inf, DistZero zero, |
533 | DijkstraVisitor vis) |
534 | { |
535 | dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, |
536 | weight, index_map, |
537 | compare, combine, inf, zero, vis); |
538 | } |
539 | |
540 | namespace detail { |
541 | |
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> |
546 | inline void |
547 | dijkstra_dispatch2 |
548 | (const VertexListGraph& g, |
549 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
550 | DistanceMap distance, WeightMap weight, IndexMap index_map, |
551 | const Params& params) |
552 | { |
553 | // Default for predecessor map |
554 | dummy_property_map p_map; |
555 | |
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)()); |
559 | |
560 | dijkstra_shortest_paths |
561 | (g, s, |
562 | choose_param(get_param(params, vertex_predecessor), p_map), |
563 | distance, weight, index_map, |
564 | choose_param(get_param(params, distance_compare_t()), |
565 | std::less<D>()), |
566 | choose_param(get_param(params, distance_combine_t()), |
567 | closed_plus<D>(inf)), |
568 | inf, |
569 | choose_param(get_param(params, distance_zero_t()), |
570 | D()), |
571 | choose_param(get_param(params, graph_visitor), |
572 | make_dijkstra_visitor(vis: null_visitor())), |
573 | params); |
574 | } |
575 | |
576 | template <class VertexListGraph, class DistanceMap, class WeightMap, |
577 | class IndexMap, class Params> |
578 | inline void |
579 | dijkstra_dispatch1 |
580 | (const VertexListGraph& g, |
581 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
582 | DistanceMap distance, WeightMap weight, IndexMap index_map, |
583 | const Params& params) |
584 | { |
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); |
590 | |
591 | detail::dijkstra_dispatch2 |
592 | (g, s, choose_param(distance, make_iterator_property_map |
593 | (distance_map.begin(), index_map, |
594 | distance_map[0])), |
595 | weight, index_map, params); |
596 | } |
597 | } // namespace detail |
598 | |
599 | // Named Parameter Variant |
600 | template <class VertexListGraph, class Param, class Tag, class Rest> |
601 | inline void |
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) |
606 | { |
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 |
610 | (g, s, |
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), |
614 | params); |
615 | } |
616 | |
617 | } // namespace boost |
618 | |
619 | #ifdef BOOST_GRAPH_USE_MPI |
620 | # include <boost/graph/distributed/dijkstra_shortest_paths.hpp> |
621 | #endif |
622 | |
623 | #endif // BOOST_GRAPH_DIJKSTRA_HPP |
624 | |