Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / dijkstra_shortest_paths.hpp
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