Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / bellman_ford_shortest_paths.hpp
1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5 //
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
10 //
11
12 /*
13   This file implements the function
14
15   template <class EdgeListGraph, class Size, class P, class T, class R>
16   bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N, 
17      const bgl_named_params<P, T, R>& params)
18   
19  */
20
21
22 #ifndef BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
23 #define BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
24
25 #include <boost/config.hpp>
26 #include <boost/graph/graph_traits.hpp>
27 #include <boost/graph/graph_concepts.hpp>
28 #include <boost/graph/properties.hpp>
29 #include <boost/graph/relax.hpp>
30 #include <boost/graph/visitors.hpp>
31 #include <boost/graph/named_function_params.hpp>
32
33 namespace boost {
34
35   template <class Visitor, class Graph>
36   struct BellmanFordVisitorConcept {
37     void constraints() {
38       function_requires< CopyConstructibleConcept<Visitor> >();
39       vis.examine_edge(e, g);
40       vis.edge_relaxed(e, g);
41       vis.edge_not_relaxed(e, g);
42       vis.edge_minimized(e, g);
43       vis.edge_not_minimized(e, g);
44     }
45     Visitor vis;
46     Graph g;
47     typename graph_traits<Graph>::edge_descriptor e;
48   };
49
50   template <class Visitors = null_visitor>
51   class bellman_visitor {
52   public:
53     bellman_visitor() { }
54     bellman_visitor(Visitors vis) : m_vis(vis) { }
55
56     template <class Edge, class Graph>
57     void examine_edge(Edge u, Graph& g) {
58       invoke_visitors(m_vis, u, g, on_examine_edge());
59     }
60     template <class Edge, class Graph>
61     void edge_relaxed(Edge u, Graph& g) {
62       invoke_visitors(m_vis, u, g, on_edge_relaxed());      
63     }
64     template <class Edge, class Graph>
65     void edge_not_relaxed(Edge u, Graph& g) {
66       invoke_visitors(m_vis, u, g, on_edge_not_relaxed());
67     }
68     template <class Edge, class Graph>
69     void edge_minimized(Edge u, Graph& g) {
70       invoke_visitors(m_vis, u, g, on_edge_minimized());
71     }
72     template <class Edge, class Graph>
73     void edge_not_minimized(Edge u, Graph& g) {
74       invoke_visitors(m_vis, u, g, on_edge_not_minimized());
75     }
76   protected:
77     Visitors m_vis;
78   };
79   template <class Visitors>
80   bellman_visitor<Visitors>
81   make_bellman_visitor(Visitors vis) {
82     return bellman_visitor<Visitors>(vis);
83   }
84   typedef bellman_visitor<> default_bellman_visitor;
85
86   template <class EdgeListGraph, class Size, class WeightMap,
87             class PredecessorMap, class DistanceMap,
88             class BinaryFunction, class BinaryPredicate,
89             class BellmanFordVisitor>
90   bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N, 
91                          WeightMap weight, 
92                          PredecessorMap pred,
93                          DistanceMap distance, 
94                          BinaryFunction combine, 
95                          BinaryPredicate compare,
96                          BellmanFordVisitor v)
97   {
98     function_requires<EdgeListGraphConcept<EdgeListGraph> >();
99     typedef graph_traits<EdgeListGraph> GTraits;
100     typedef typename GTraits::edge_descriptor Edge;
101     typedef typename GTraits::vertex_descriptor Vertex;
102     function_requires<ReadWritePropertyMapConcept<DistanceMap, Vertex> >();
103     function_requires<ReadablePropertyMapConcept<WeightMap, Edge> >();
104     typedef typename property_traits<DistanceMap>::value_type D_value;
105     typedef typename property_traits<WeightMap>::value_type W_value;
106
107     typename GTraits::edge_iterator i, end;
108
109     for (Size k = 0; k < N; ++k) {
110       bool at_least_one_edge_relaxed = false;
111       for (tie(i, end) = edges(g); i != end; ++i) {
112         v.examine_edge(*i, g);
113         if (relax(*i, g, weight, pred, distance, combine, compare)) {
114           at_least_one_edge_relaxed = true;
115           v.edge_relaxed(*i, g);
116         } else
117           v.edge_not_relaxed(*i, g);
118       }
119       if (!at_least_one_edge_relaxed)
120         break;
121     }
122
123     for (tie(i, end) = edges(g); i != end; ++i)
124       if (compare(combine(get(distance, source(*i, g)), get(weight, *i)),
125                   get(distance, target(*i,g))))
126       {
127         v.edge_not_minimized(*i, g);
128         return false;
129       } else
130         v.edge_minimized(*i, g);
131
132     return true;
133   }
134
135   namespace detail {
136
137     template<typename VertexAndEdgeListGraph, typename Size, 
138              typename WeightMap, typename PredecessorMap, typename DistanceMap,
139              typename P, typename T, typename R>
140     bool 
141     bellman_dispatch2
142       (VertexAndEdgeListGraph& g, 
143        typename graph_traits<VertexAndEdgeListGraph>::vertex_descriptor s,
144        Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance,
145        const bgl_named_params<P, T, R>& params)
146     {
147       typedef typename property_traits<DistanceMap>::value_type D;
148       bellman_visitor<> null_vis;
149       typedef typename property_traits<WeightMap>::value_type weight_type;
150       typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator v, v_end;
151       for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
152         put(distance, *v, (std::numeric_limits<weight_type>::max)());
153         put(pred, *v, *v);
154       }
155       put(distance, s, weight_type(0));
156       return bellman_ford_shortest_paths
157                (g, N, weight, pred, distance,
158                 choose_param(get_param(params, distance_combine_t()),
159                              closed_plus<D>()),
160                 choose_param(get_param(params, distance_compare_t()),
161                              std::less<D>()),
162                 choose_param(get_param(params, graph_visitor),
163                              null_vis)
164                 );
165     }
166
167     template<typename VertexAndEdgeListGraph, typename Size, 
168              typename WeightMap, typename PredecessorMap, typename DistanceMap,
169              typename P, typename T, typename R>
170     bool 
171     bellman_dispatch2
172       (VertexAndEdgeListGraph& g, 
173        detail::error_property_not_found,
174        Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance,
175        const bgl_named_params<P, T, R>& params)
176     {
177       typedef typename property_traits<DistanceMap>::value_type D;
178       bellman_visitor<> null_vis;
179       return bellman_ford_shortest_paths
180                (g, N, weight, pred, distance,
181                 choose_param(get_param(params, distance_combine_t()),
182                              closed_plus<D>()),
183                 choose_param(get_param(params, distance_compare_t()),
184                              std::less<D>()),
185                 choose_param(get_param(params, graph_visitor),
186                              null_vis)
187                 );
188     }
189
190     template <class EdgeListGraph, class Size, class WeightMap,
191               class DistanceMap, class P, class T, class R>
192     bool bellman_dispatch(EdgeListGraph& g, Size N, 
193                           WeightMap weight, DistanceMap distance, 
194                           const bgl_named_params<P, T, R>& params)
195     {
196       dummy_property_map dummy_pred;
197       return 
198         detail::bellman_dispatch2
199           (g, 
200            get_param(params, root_vertex_t()),
201            N, weight,
202            choose_param(get_param(params, vertex_predecessor), dummy_pred),
203            distance,
204            params);
205     }
206   } // namespace detail
207
208   template <class EdgeListGraph, class Size, class P, class T, class R>
209   bool bellman_ford_shortest_paths
210     (EdgeListGraph& g, Size N, 
211      const bgl_named_params<P, T, R>& params)
212   {                                
213     return detail::bellman_dispatch
214       (g, N,
215        choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
216        choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
217        params);
218   }
219
220   template <class EdgeListGraph, class Size>
221   bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N)
222   {                                
223     bgl_named_params<int,int> params(0);
224     return bellman_ford_shortest_paths(g, N, params);
225   }
226
227   template <class VertexAndEdgeListGraph, class P, class T, class R>
228   bool bellman_ford_shortest_paths
229     (VertexAndEdgeListGraph& g, 
230      const bgl_named_params<P, T, R>& params)
231   {               
232     function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();
233     return detail::bellman_dispatch
234       (g, num_vertices(g),
235        choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
236        choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
237        params);
238   }
239 } // namespace boost
240
241 #endif // BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP