source: NonGTP/Boost/boost/graph/dijkstra_shortest_paths.hpp @ 857

Revision 857, 13.1 KB checked in by igarcia, 19 years ago (diff)
Line 
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
25namespace 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
Note: See TracBrowser for help on using the repository browser.