]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(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(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 |