Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / floyd_warshall_shortest.hpp
1 // Copyright 2002 Rensselaer Polytechnic Institute
2
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 //  Authors: Lauren Foutz
8 //           Scott Hill
9
10 /*
11   This file implements the functions
12
13   template <class VertexListGraph, class DistanceMatrix, 
14     class P, class T, class R>
15   bool floyd_warshall_initialized_all_pairs_shortest_paths(
16     const VertexListGraph& g, DistanceMatrix& d, 
17     const bgl_named_params<P, T, R>& params)
18
19   AND
20
21   template <class VertexAndEdgeListGraph, class DistanceMatrix, 
22     class P, class T, class R>
23   bool floyd_warshall_all_pairs_shortest_paths(
24     const VertexAndEdgeListGraph& g, DistanceMatrix& d, 
25     const bgl_named_params<P, T, R>& params)
26 */
27
28
29 #ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP
30 #define BOOST_GRAPH_FLOYD_WARSHALL_HPP
31
32 #include <boost/property_map.hpp>
33 #include <boost/graph/graph_traits.hpp>
34 #include <boost/graph/named_function_params.hpp>
35 #include <boost/graph/graph_concepts.hpp>
36 #include <boost/graph/relax.hpp>
37 #include <algorithm> // for std::min and std::max
38
39 namespace boost
40 {
41   namespace detail {
42     template<typename VertexListGraph, typename DistanceMatrix, 
43       typename BinaryPredicate, typename BinaryFunction,
44       typename Infinity, typename Zero>
45     bool floyd_warshall_dispatch(const VertexListGraph& g, 
46       DistanceMatrix& d, const BinaryPredicate &compare, 
47       const BinaryFunction &combine, const Infinity& inf, 
48       const Zero& zero)
49     {
50       BOOST_USING_STD_MIN();
51
52       typename graph_traits<VertexListGraph>::vertex_iterator 
53         i, lasti, j, lastj, k, lastk;
54     
55       
56       for (tie(k, lastk) = vertices(g); k != lastk; k++)
57         for (tie(i, lasti) = vertices(g); i != lasti; i++)
58           for (tie(j, lastj) = vertices(g); j != lastj; j++)
59           {
60             d[*i][*j] = min BOOST_PREVENT_MACRO_SUBSTITUTION
61                          (d[*i][*j], combine(d[*i][*k], d[*k][*j]));
62           }
63       
64     
65       for (tie(i, lasti) = vertices(g); i != lasti; i++)
66         if (compare(d[*i][*i], zero))
67           return false;
68       return true;
69     }
70   }
71
72   template <typename VertexListGraph, typename DistanceMatrix, 
73     typename BinaryPredicate, typename BinaryFunction,
74     typename Infinity, typename Zero>
75   bool floyd_warshall_initialized_all_pairs_shortest_paths(
76     const VertexListGraph& g, DistanceMatrix& d, 
77     const BinaryPredicate& compare, 
78     const BinaryFunction& combine, const Infinity& inf, 
79     const Zero& zero)
80   {
81     function_requires<VertexListGraphConcept<VertexListGraph> >();
82   
83     return detail::floyd_warshall_dispatch(g, d, compare, combine, 
84     inf, zero);
85   }
86   
87
88   
89   template <typename VertexAndEdgeListGraph, typename DistanceMatrix, 
90     typename WeightMap, typename BinaryPredicate, 
91     typename BinaryFunction, typename Infinity, typename Zero>
92   bool floyd_warshall_all_pairs_shortest_paths(
93     const VertexAndEdgeListGraph& g, 
94     DistanceMatrix& d, const WeightMap& w, 
95     const BinaryPredicate& compare, const BinaryFunction& combine, 
96     const Infinity& inf, const Zero& zero)
97   {
98     BOOST_USING_STD_MIN();
99
100     function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();
101     function_requires<EdgeListGraphConcept<VertexAndEdgeListGraph> >();
102     function_requires<IncidenceGraphConcept<VertexAndEdgeListGraph> >();
103   
104     typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator 
105       firstv, lastv, firstv2, lastv2;
106     typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last;
107   
108     
109     for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
110       for(tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++)
111         d[*firstv][*firstv2] = inf;
112     
113     
114     for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
115       d[*firstv][*firstv] = 0;
116     
117     
118     for(tie(first, last) = edges(g); first != last; first++)
119     {
120       if (d[source(*first, g)][target(*first, g)] != inf)
121         d[source(*first, g)][target(*first, g)] = 
122           min BOOST_PREVENT_MACRO_SUBSTITUTION(get(w, *first), 
123             d[source(*first, g)][target(*first, g)]);
124       else 
125         d[source(*first, g)][target(*first, g)] = get(w, *first);
126     }
127     
128     bool is_undirected = is_same<typename 
129       graph_traits<VertexAndEdgeListGraph>::directed_category, 
130       undirected_tag>::value;
131     if (is_undirected)
132     {
133       for(tie(first, last) = edges(g); first != last; first++)
134       {
135         if (d[target(*first, g)][source(*first, g)] != inf)
136           d[target(*first, g)][source(*first, g)] = 
137             min BOOST_PREVENT_MACRO_SUBSTITUTION(get(w, *first), 
138             d[target(*first, g)][source(*first, g)]);
139         else 
140           d[target(*first, g)][source(*first, g)] = get(w, *first);
141       }
142     }
143     
144   
145     return detail::floyd_warshall_dispatch(g, d, compare, combine, 
146       inf, zero);
147   }
148   
149
150   namespace detail {        
151     template <class VertexListGraph, class DistanceMatrix, 
152       class WeightMap, class P, class T, class R>
153     bool floyd_warshall_init_dispatch(const VertexListGraph& g, 
154       DistanceMatrix& d, WeightMap w, 
155       const bgl_named_params<P, T, R>& params)
156     {
157       typedef typename property_traits<WeightMap>::value_type WM;
158     
159       return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,
160         choose_param(get_param(params, distance_compare_t()), 
161           std::less<WM>()),
162         choose_param(get_param(params, distance_combine_t()), 
163           closed_plus<WM>()),
164         choose_param(get_param(params, distance_inf_t()), 
165           std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
166         choose_param(get_param(params, distance_zero_t()), 
167           WM()));
168     }
169     
170
171     
172     template <class VertexAndEdgeListGraph, class DistanceMatrix, 
173       class WeightMap, class P, class T, class R>
174     bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g, 
175       DistanceMatrix& d, WeightMap w, 
176       const bgl_named_params<P, T, R>& params)
177     {
178       typedef typename property_traits<WeightMap>::value_type WM;
179     
180       return floyd_warshall_all_pairs_shortest_paths(g, d, w,
181         choose_param(get_param(params, distance_compare_t()), 
182           std::less<WM>()),
183         choose_param(get_param(params, distance_combine_t()), 
184           closed_plus<WM>()),
185         choose_param(get_param(params, distance_inf_t()), 
186           std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
187         choose_param(get_param(params, distance_zero_t()), 
188           WM()));
189     }
190     
191
192   }   // namespace detail
193
194   
195   
196   template <class VertexListGraph, class DistanceMatrix, class P, 
197     class T, class R>
198   bool floyd_warshall_initialized_all_pairs_shortest_paths(
199     const VertexListGraph& g, DistanceMatrix& d, 
200     const bgl_named_params<P, T, R>& params)
201   {
202     return detail::floyd_warshall_init_dispatch(g, d, 
203       choose_const_pmap(get_param(params, edge_weight), g, edge_weight), 
204       params);
205   }
206   
207   template <class VertexListGraph, class DistanceMatrix>
208   bool floyd_warshall_initialized_all_pairs_shortest_paths(
209     const VertexListGraph& g, DistanceMatrix& d)
210   {
211     bgl_named_params<int,int> params(0);
212     return detail::floyd_warshall_init_dispatch(g, d,
213       get(edge_weight, g), params);
214   }
215   
216
217   
218   
219   template <class VertexAndEdgeListGraph, class DistanceMatrix, 
220     class P, class T, class R>
221   bool floyd_warshall_all_pairs_shortest_paths(
222     const VertexAndEdgeListGraph& g, DistanceMatrix& d, 
223     const bgl_named_params<P, T, R>& params)
224   {
225     return detail::floyd_warshall_noninit_dispatch(g, d, 
226       choose_const_pmap(get_param(params, edge_weight), g, edge_weight), 
227       params);
228   }
229   
230   template <class VertexAndEdgeListGraph, class DistanceMatrix>
231   bool floyd_warshall_all_pairs_shortest_paths(
232     const VertexAndEdgeListGraph& g, DistanceMatrix& d)
233   {
234     bgl_named_params<int,int> params(0);
235     return detail::floyd_warshall_noninit_dispatch(g, d,
236       get(edge_weight, g), params);
237   }
238   
239
240 } // namespace boost
241
242 #endif
243