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