[857] | 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 | #ifndef BOOST_GRAPH_DIJKSTRA_HPP
|
---|
| 10 | #define BOOST_GRAPH_DIJKSTRA_HPP
|
---|
| 11 |
|
---|
| 12 | #include <functional>
|
---|
| 13 | #include <boost/limits.hpp>
|
---|
| 14 | #include <boost/graph/named_function_params.hpp>
|
---|
| 15 | #include <boost/graph/breadth_first_search.hpp>
|
---|
| 16 | #include <boost/graph/relax.hpp>
|
---|
| 17 | #include <boost/pending/indirect_cmp.hpp>
|
---|
| 18 | #include <boost/graph/exception.hpp>
|
---|
| 19 | #include <boost/pending/relaxed_heap.hpp>
|
---|
| 20 |
|
---|
| 21 | #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
|
---|
| 22 | # include <boost/pending/mutable_queue.hpp>
|
---|
| 23 | #endif // BOOST_GRAPH_DIJKSTRA_TESTING
|
---|
| 24 |
|
---|
| 25 | namespace boost {
|
---|
| 26 |
|
---|
| 27 | #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
|
---|
| 28 | static bool dijkstra_relaxed_heap = true;
|
---|
| 29 | #endif
|
---|
| 30 |
|
---|
| 31 | template <class Visitor, class Graph>
|
---|
| 32 | struct DijkstraVisitorConcept {
|
---|
| 33 | void constraints() {
|
---|
| 34 | function_requires< CopyConstructibleConcept<Visitor> >();
|
---|
| 35 | vis.discover_vertex(u, g);
|
---|
| 36 | vis.examine_vertex(u, g);
|
---|
| 37 | vis.examine_edge(e, g);
|
---|
| 38 | vis.edge_relaxed(e, g);
|
---|
| 39 | vis.edge_not_relaxed(e, g);
|
---|
| 40 | vis.finish_vertex(u, g);
|
---|
| 41 | }
|
---|
| 42 | Visitor vis;
|
---|
| 43 | Graph g;
|
---|
| 44 | typename graph_traits<Graph>::vertex_descriptor u;
|
---|
| 45 | typename graph_traits<Graph>::edge_descriptor e;
|
---|
| 46 | };
|
---|
| 47 |
|
---|
| 48 | template <class Visitors = null_visitor>
|
---|
| 49 | class dijkstra_visitor : public bfs_visitor<Visitors> {
|
---|
| 50 | public:
|
---|
| 51 | dijkstra_visitor() { }
|
---|
| 52 | dijkstra_visitor(Visitors vis)
|
---|
| 53 | : bfs_visitor<Visitors>(vis) { }
|
---|
| 54 |
|
---|
| 55 | template <class Edge, class Graph>
|
---|
| 56 | void edge_relaxed(Edge e, Graph& g) {
|
---|
| 57 | invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
|
---|
| 58 | }
|
---|
| 59 | template <class Edge, class Graph>
|
---|
| 60 | void edge_not_relaxed(Edge e, Graph& g) {
|
---|
| 61 | invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
|
---|
| 62 | }
|
---|
| 63 | private:
|
---|
| 64 | template <class Edge, class Graph>
|
---|
| 65 | void tree_edge(Edge u, Graph& g) { }
|
---|
| 66 | };
|
---|
| 67 | template <class Visitors>
|
---|
| 68 | dijkstra_visitor<Visitors>
|
---|
| 69 | make_dijkstra_visitor(Visitors vis) {
|
---|
| 70 | return dijkstra_visitor<Visitors>(vis);
|
---|
| 71 | }
|
---|
| 72 | typedef dijkstra_visitor<> default_dijkstra_visitor;
|
---|
| 73 |
|
---|
| 74 | namespace detail {
|
---|
| 75 |
|
---|
| 76 | template <class UniformCostVisitor, class UpdatableQueue,
|
---|
| 77 | class WeightMap, class PredecessorMap, class DistanceMap,
|
---|
| 78 | class BinaryFunction, class BinaryPredicate>
|
---|
| 79 | struct dijkstra_bfs_visitor
|
---|
| 80 | {
|
---|
| 81 | typedef typename property_traits<DistanceMap>::value_type D;
|
---|
| 82 |
|
---|
| 83 | dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,
|
---|
| 84 | WeightMap w, PredecessorMap p, DistanceMap d,
|
---|
| 85 | BinaryFunction combine, BinaryPredicate compare,
|
---|
| 86 | D zero)
|
---|
| 87 | : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d),
|
---|
| 88 | m_combine(combine), m_compare(compare), m_zero(zero) { }
|
---|
| 89 |
|
---|
| 90 | template <class Edge, class Graph>
|
---|
| 91 | void tree_edge(Edge e, Graph& g) {
|
---|
| 92 | m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
|
---|
| 93 | m_combine, m_compare);
|
---|
| 94 | if (m_decreased)
|
---|
| 95 | m_vis.edge_relaxed(e, g);
|
---|
| 96 | else
|
---|
| 97 | m_vis.edge_not_relaxed(e, g);
|
---|
| 98 | }
|
---|
| 99 | template <class Edge, class Graph>
|
---|
| 100 | void gray_target(Edge e, Graph& g) {
|
---|
| 101 | m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
|
---|
| 102 | m_combine, m_compare);
|
---|
| 103 | if (m_decreased) {
|
---|
| 104 | m_Q.update(target(e, g));
|
---|
| 105 | m_vis.edge_relaxed(e, g);
|
---|
| 106 | } else
|
---|
| 107 | m_vis.edge_not_relaxed(e, g);
|
---|
| 108 | }
|
---|
| 109 |
|
---|
| 110 | template <class Vertex, class Graph>
|
---|
| 111 | void initialize_vertex(Vertex u, Graph& g)
|
---|
| 112 | { m_vis.initialize_vertex(u, g); }
|
---|
| 113 | template <class Edge, class Graph>
|
---|
| 114 | void non_tree_edge(Edge, Graph&) { }
|
---|
| 115 | template <class Vertex, class Graph>
|
---|
| 116 | void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); }
|
---|
| 117 | template <class Vertex, class Graph>
|
---|
| 118 | void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
|
---|
| 119 | template <class Edge, class Graph>
|
---|
| 120 | void examine_edge(Edge e, Graph& g) {
|
---|
| 121 | if (m_compare(get(m_weight, e), m_zero))
|
---|
| 122 | throw negative_edge();
|
---|
| 123 | m_vis.examine_edge(e, g);
|
---|
| 124 | }
|
---|
| 125 | template <class Edge, class Graph>
|
---|
| 126 | void black_target(Edge, Graph&) { }
|
---|
| 127 | template <class Vertex, class Graph>
|
---|
| 128 | void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); }
|
---|
| 129 |
|
---|
| 130 | UniformCostVisitor m_vis;
|
---|
| 131 | UpdatableQueue& m_Q;
|
---|
| 132 | WeightMap m_weight;
|
---|
| 133 | PredecessorMap m_predecessor;
|
---|
| 134 | DistanceMap m_distance;
|
---|
| 135 | BinaryFunction m_combine;
|
---|
| 136 | BinaryPredicate m_compare;
|
---|
| 137 | bool m_decreased;
|
---|
| 138 | D m_zero;
|
---|
| 139 | };
|
---|
| 140 |
|
---|
| 141 | } // namespace detail
|
---|
| 142 |
|
---|
| 143 | // Call breadth first search with default color map.
|
---|
| 144 | template <class VertexListGraph, class DijkstraVisitor,
|
---|
| 145 | class PredecessorMap, class DistanceMap,
|
---|
| 146 | class WeightMap, class IndexMap, class Compare, class Combine,
|
---|
| 147 | class DistZero>
|
---|
| 148 | inline void
|
---|
| 149 | dijkstra_shortest_paths_no_init
|
---|
| 150 | (const VertexListGraph& g,
|
---|
| 151 | typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
---|
| 152 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
|
---|
| 153 | IndexMap index_map,
|
---|
| 154 | Compare compare, Combine combine, DistZero zero,
|
---|
| 155 | DijkstraVisitor vis)
|
---|
| 156 | {
|
---|
| 157 | std::vector<default_color_type> color(num_vertices(g));
|
---|
| 158 | default_color_type c = white_color;
|
---|
| 159 | dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight,
|
---|
| 160 | index_map, compare, combine, zero, vis,
|
---|
| 161 | make_iterator_property_map(&color[0], index_map, c));
|
---|
| 162 | }
|
---|
| 163 |
|
---|
| 164 | // Call breadth first search
|
---|
| 165 | template <class VertexListGraph, class DijkstraVisitor,
|
---|
| 166 | class PredecessorMap, class DistanceMap,
|
---|
| 167 | class WeightMap, class IndexMap, class Compare, class Combine,
|
---|
| 168 | class DistZero, class ColorMap>
|
---|
| 169 | inline void
|
---|
| 170 | dijkstra_shortest_paths_no_init
|
---|
| 171 | (const VertexListGraph& g,
|
---|
| 172 | typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
---|
| 173 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
|
---|
| 174 | IndexMap index_map,
|
---|
| 175 | Compare compare, Combine combine, DistZero zero,
|
---|
| 176 | DijkstraVisitor vis, ColorMap color)
|
---|
| 177 | {
|
---|
| 178 | typedef indirect_cmp<DistanceMap, Compare> IndirectCmp;
|
---|
| 179 | IndirectCmp icmp(distance, compare);
|
---|
| 180 |
|
---|
| 181 | typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
|
---|
| 182 |
|
---|
| 183 | #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
|
---|
| 184 | if (!dijkstra_relaxed_heap) {
|
---|
| 185 | typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap>
|
---|
| 186 | MutableQueue;
|
---|
| 187 |
|
---|
| 188 | MutableQueue Q(num_vertices(g), icmp, index_map);
|
---|
| 189 |
|
---|
| 190 | detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
|
---|
| 191 | PredecessorMap, DistanceMap, Combine, Compare>
|
---|
| 192 | bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
|
---|
| 193 |
|
---|
| 194 | breadth_first_visit(g, s, Q, bfs_vis, color);
|
---|
| 195 | return;
|
---|
| 196 | }
|
---|
| 197 | #endif // BOOST_GRAPH_DIJKSTRA_TESTING
|
---|
| 198 |
|
---|
| 199 | typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue;
|
---|
| 200 |
|
---|
| 201 | MutableQueue Q(num_vertices(g), icmp, index_map);
|
---|
| 202 |
|
---|
| 203 | detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
|
---|
| 204 | PredecessorMap, DistanceMap, Combine, Compare>
|
---|
| 205 | bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
|
---|
| 206 |
|
---|
| 207 | breadth_first_visit(g, s, Q, bfs_vis, color);
|
---|
| 208 | }
|
---|
| 209 |
|
---|
| 210 | // Initialize distances and call breadth first search with default color map
|
---|
| 211 | template <class VertexListGraph, class DijkstraVisitor,
|
---|
| 212 | class PredecessorMap, class DistanceMap,
|
---|
| 213 | class WeightMap, class IndexMap, class Compare, class Combine,
|
---|
| 214 | class DistInf, class DistZero>
|
---|
| 215 | inline void
|
---|
| 216 | dijkstra_shortest_paths
|
---|
| 217 | (const VertexListGraph& g,
|
---|
| 218 | typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
---|
| 219 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
|
---|
| 220 | IndexMap index_map,
|
---|
| 221 | Compare compare, Combine combine, DistInf inf, DistZero zero,
|
---|
| 222 | DijkstraVisitor vis)
|
---|
| 223 | {
|
---|
| 224 | std::vector<default_color_type> color(num_vertices(g));
|
---|
| 225 | default_color_type c = white_color;
|
---|
| 226 | dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
|
---|
| 227 | compare, combine, inf, zero, vis,
|
---|
| 228 | make_iterator_property_map(&color[0], index_map,
|
---|
| 229 | c));
|
---|
| 230 | }
|
---|
| 231 |
|
---|
| 232 | // Initialize distances and call breadth first search
|
---|
| 233 | template <class VertexListGraph, class DijkstraVisitor,
|
---|
| 234 | class PredecessorMap, class DistanceMap,
|
---|
| 235 | class WeightMap, class IndexMap, class Compare, class Combine,
|
---|
| 236 | class DistInf, class DistZero, class ColorMap>
|
---|
| 237 | inline void
|
---|
| 238 | dijkstra_shortest_paths
|
---|
| 239 | (const VertexListGraph& g,
|
---|
| 240 | typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
---|
| 241 | PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
|
---|
| 242 | IndexMap index_map,
|
---|
| 243 | Compare compare, Combine combine, DistInf inf, DistZero zero,
|
---|
| 244 | DijkstraVisitor vis, ColorMap color)
|
---|
| 245 | {
|
---|
| 246 | typedef typename property_traits<ColorMap>::value_type ColorValue;
|
---|
| 247 | typedef color_traits<ColorValue> Color;
|
---|
| 248 | typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
|
---|
| 249 | for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
|
---|
| 250 | put(distance, *ui, inf);
|
---|
| 251 | put(predecessor, *ui, *ui);
|
---|
| 252 | put(color, *ui, Color::white());
|
---|
| 253 | }
|
---|
| 254 | put(distance, s, zero);
|
---|
| 255 |
|
---|
| 256 | dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight,
|
---|
| 257 | index_map, compare, combine, zero, vis, color);
|
---|
| 258 | }
|
---|
| 259 |
|
---|
| 260 | namespace detail {
|
---|
| 261 |
|
---|
| 262 | // Handle defaults for PredecessorMap and
|
---|
| 263 | // Distance Compare, Combine, Inf and Zero
|
---|
| 264 | template <class VertexListGraph, class DistanceMap, class WeightMap,
|
---|
| 265 | class IndexMap, class Params, class ColorMap>
|
---|
| 266 | inline void
|
---|
| 267 | dijkstra_dispatch2
|
---|
| 268 | (const VertexListGraph& g,
|
---|
| 269 | typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
---|
| 270 | DistanceMap distance, WeightMap weight, IndexMap index_map,
|
---|
| 271 | const Params& params, ColorMap color)
|
---|
| 272 | {
|
---|
| 273 | // Default for predecessor map
|
---|
| 274 | dummy_property_map p_map;
|
---|
| 275 |
|
---|
| 276 | typedef typename property_traits<DistanceMap>::value_type D;
|
---|
| 277 | dijkstra_shortest_paths
|
---|
| 278 | (g, s,
|
---|
| 279 | choose_param(get_param(params, vertex_predecessor), p_map),
|
---|
| 280 | distance, weight, index_map,
|
---|
| 281 | choose_param(get_param(params, distance_compare_t()),
|
---|
| 282 | std::less<D>()),
|
---|
| 283 | choose_param(get_param(params, distance_combine_t()),
|
---|
| 284 | closed_plus<D>()),
|
---|
| 285 | choose_param(get_param(params, distance_inf_t()),
|
---|
| 286 | (std::numeric_limits<D>::max)()),
|
---|
| 287 | choose_param(get_param(params, distance_zero_t()),
|
---|
| 288 | D()),
|
---|
| 289 | choose_param(get_param(params, graph_visitor),
|
---|
| 290 | make_dijkstra_visitor(null_visitor())),
|
---|
| 291 | color);
|
---|
| 292 | }
|
---|
| 293 |
|
---|
| 294 | template <class VertexListGraph, class DistanceMap, class WeightMap,
|
---|
| 295 | class IndexMap, class Params, class ColorMap>
|
---|
| 296 | inline void
|
---|
| 297 | dijkstra_dispatch1
|
---|
| 298 | (const VertexListGraph& g,
|
---|
| 299 | typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
---|
| 300 | DistanceMap distance, WeightMap weight, IndexMap index_map,
|
---|
| 301 | const Params& params, ColorMap color)
|
---|
| 302 | {
|
---|
| 303 | // Default for distance map
|
---|
| 304 | typedef typename property_traits<WeightMap>::value_type D;
|
---|
| 305 | typename std::vector<D>::size_type
|
---|
| 306 | n = is_default_param(distance) ? num_vertices(g) : 1;
|
---|
| 307 | std::vector<D> distance_map(n);
|
---|
| 308 |
|
---|
| 309 | // Default for color map
|
---|
| 310 | typename std::vector<default_color_type>::size_type
|
---|
| 311 | m = is_default_param(color) ? num_vertices(g) : 1;
|
---|
| 312 | std::vector<default_color_type> color_map(m);
|
---|
| 313 |
|
---|
| 314 | detail::dijkstra_dispatch2
|
---|
| 315 | (g, s, choose_param(distance, make_iterator_property_map
|
---|
| 316 | (distance_map.begin(), index_map,
|
---|
| 317 | distance_map[0])),
|
---|
| 318 | weight, index_map, params,
|
---|
| 319 | choose_param(color, make_iterator_property_map
|
---|
| 320 | (color_map.begin(), index_map,
|
---|
| 321 | color_map[0])));
|
---|
| 322 | }
|
---|
| 323 | } // namespace detail
|
---|
| 324 |
|
---|
| 325 | // Named Parameter Variant
|
---|
| 326 | template <class VertexListGraph, class Param, class Tag, class Rest>
|
---|
| 327 | inline void
|
---|
| 328 | dijkstra_shortest_paths
|
---|
| 329 | (const VertexListGraph& g,
|
---|
| 330 | typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
---|
| 331 | const bgl_named_params<Param,Tag,Rest>& params)
|
---|
| 332 | {
|
---|
| 333 | // Default for edge weight and vertex index map is to ask for them
|
---|
| 334 | // from the graph. Default for the visitor is null_visitor.
|
---|
| 335 | detail::dijkstra_dispatch1
|
---|
| 336 | (g, s,
|
---|
| 337 | get_param(params, vertex_distance),
|
---|
| 338 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
|
---|
| 339 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
|
---|
| 340 | params,
|
---|
| 341 | get_param(params, vertex_color));
|
---|
| 342 | }
|
---|
| 343 |
|
---|
| 344 | } // namespace boost
|
---|
| 345 |
|
---|
| 346 | #endif // BOOST_GRAPH_DIJKSTRA_HPP
|
---|