1 | // Copyright 2002 Rensselaer Polytechnic Institute |
2 | |
3 | // Distributed under the Boost Software License, Version 1.0. |
4 | // (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/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 <boost/concept/assert.hpp> |
38 | |
39 | namespace boost |
40 | { |
41 | namespace detail { |
42 | template<typename T, typename BinaryPredicate> |
43 | T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare) |
44 | { |
45 | if (compare(x, y)) return x; |
46 | else return y; |
47 | } |
48 | |
49 | template<typename VertexListGraph, typename DistanceMatrix, |
50 | typename BinaryPredicate, typename BinaryFunction, |
51 | typename Infinity, typename Zero> |
52 | bool floyd_warshall_dispatch(const VertexListGraph& g, |
53 | DistanceMatrix& d, const BinaryPredicate &compare, |
54 | const BinaryFunction &combine, const Infinity& inf, |
55 | const Zero& zero) |
56 | { |
57 | typename graph_traits<VertexListGraph>::vertex_iterator |
58 | i, lasti, j, lastj, k, lastk; |
59 | |
60 | |
61 | for (boost::tie(k, lastk) = vertices(g); k != lastk; k++) |
62 | for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) |
63 | if(d[*i][*k] != inf) |
64 | for (boost::tie(j, lastj) = vertices(g); j != lastj; j++) |
65 | if(d[*k][*j] != inf) |
66 | d[*i][*j] = |
67 | detail::min_with_compare(d[*i][*j], |
68 | combine(d[*i][*k], d[*k][*j]), |
69 | compare); |
70 | |
71 | |
72 | for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) |
73 | if (compare(d[*i][*i], zero)) |
74 | return false; |
75 | return true; |
76 | } |
77 | } |
78 | |
79 | template <typename VertexListGraph, typename DistanceMatrix, |
80 | typename BinaryPredicate, typename BinaryFunction, |
81 | typename Infinity, typename Zero> |
82 | bool floyd_warshall_initialized_all_pairs_shortest_paths( |
83 | const VertexListGraph& g, DistanceMatrix& d, |
84 | const BinaryPredicate& compare, |
85 | const BinaryFunction& combine, const Infinity& inf, |
86 | const Zero& zero) |
87 | { |
88 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<VertexListGraph> )); |
89 | |
90 | return detail::floyd_warshall_dispatch(g, d, compare, combine, |
91 | inf, zero); |
92 | } |
93 | |
94 | |
95 | |
96 | template <typename VertexAndEdgeListGraph, typename DistanceMatrix, |
97 | typename WeightMap, typename BinaryPredicate, |
98 | typename BinaryFunction, typename Infinity, typename Zero> |
99 | bool floyd_warshall_all_pairs_shortest_paths( |
100 | const VertexAndEdgeListGraph& g, |
101 | DistanceMatrix& d, const WeightMap& w, |
102 | const BinaryPredicate& compare, const BinaryFunction& combine, |
103 | const Infinity& inf, const Zero& zero) |
104 | { |
105 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<VertexAndEdgeListGraph> )); |
106 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<VertexAndEdgeListGraph> )); |
107 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<VertexAndEdgeListGraph> )); |
108 | |
109 | typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator |
110 | firstv, lastv, firstv2, lastv2; |
111 | typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last; |
112 | |
113 | |
114 | for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) |
115 | for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++) |
116 | d[*firstv][*firstv2] = inf; |
117 | |
118 | |
119 | for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) |
120 | d[*firstv][*firstv] = zero; |
121 | |
122 | |
123 | for(boost::tie(first, last) = edges(g); first != last; first++) |
124 | { |
125 | if (d[source(*first, g)][target(*first, g)] != inf) { |
126 | d[source(*first, g)][target(*first, g)] = |
127 | detail::min_with_compare( |
128 | get(w, *first), |
129 | d[source(*first, g)][target(*first, g)], |
130 | compare); |
131 | } else |
132 | d[source(*first, g)][target(*first, g)] = get(w, *first); |
133 | } |
134 | |
135 | bool is_undirected = is_same<typename |
136 | graph_traits<VertexAndEdgeListGraph>::directed_category, |
137 | undirected_tag>::value; |
138 | if (is_undirected) |
139 | { |
140 | for(boost::tie(first, last) = edges(g); first != last; first++) |
141 | { |
142 | if (d[target(*first, g)][source(*first, g)] != inf) |
143 | d[target(*first, g)][source(*first, g)] = |
144 | detail::min_with_compare( |
145 | get(w, *first), |
146 | d[target(*first, g)][source(*first, g)], |
147 | compare); |
148 | else |
149 | d[target(*first, g)][source(*first, g)] = get(w, *first); |
150 | } |
151 | } |
152 | |
153 | |
154 | return detail::floyd_warshall_dispatch(g, d, compare, combine, |
155 | inf, zero); |
156 | } |
157 | |
158 | |
159 | namespace detail { |
160 | template <class VertexListGraph, class DistanceMatrix, |
161 | class WeightMap, class P, class T, class R> |
162 | bool floyd_warshall_init_dispatch(const VertexListGraph& g, |
163 | DistanceMatrix& d, WeightMap /*w*/, |
164 | const bgl_named_params<P, T, R>& params) |
165 | { |
166 | typedef typename property_traits<WeightMap>::value_type WM; |
167 | WM inf = |
168 | choose_param(get_param(params, distance_inf_t()), |
169 | std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()); |
170 | |
171 | return floyd_warshall_initialized_all_pairs_shortest_paths(g, d, |
172 | choose_param(get_param(params, distance_compare_t()), |
173 | std::less<WM>()), |
174 | choose_param(get_param(params, distance_combine_t()), |
175 | closed_plus<WM>(inf)), |
176 | inf, |
177 | choose_param(get_param(params, distance_zero_t()), |
178 | WM())); |
179 | } |
180 | |
181 | |
182 | |
183 | template <class VertexAndEdgeListGraph, class DistanceMatrix, |
184 | class WeightMap, class P, class T, class R> |
185 | bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g, |
186 | DistanceMatrix& d, WeightMap w, |
187 | const bgl_named_params<P, T, R>& params) |
188 | { |
189 | typedef typename property_traits<WeightMap>::value_type WM; |
190 | |
191 | WM inf = |
192 | choose_param(get_param(params, distance_inf_t()), |
193 | std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()); |
194 | return floyd_warshall_all_pairs_shortest_paths(g, d, w, |
195 | choose_param(get_param(params, distance_compare_t()), |
196 | std::less<WM>()), |
197 | choose_param(get_param(params, distance_combine_t()), |
198 | closed_plus<WM>(inf)), |
199 | inf, |
200 | choose_param(get_param(params, distance_zero_t()), |
201 | WM())); |
202 | } |
203 | |
204 | |
205 | } // namespace detail |
206 | |
207 | |
208 | |
209 | template <class VertexListGraph, class DistanceMatrix, class P, |
210 | class T, class R> |
211 | bool floyd_warshall_initialized_all_pairs_shortest_paths( |
212 | const VertexListGraph& g, DistanceMatrix& d, |
213 | const bgl_named_params<P, T, R>& params) |
214 | { |
215 | return detail::floyd_warshall_init_dispatch(g, d, |
216 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
217 | params); |
218 | } |
219 | |
220 | template <class VertexListGraph, class DistanceMatrix> |
221 | bool floyd_warshall_initialized_all_pairs_shortest_paths( |
222 | const VertexListGraph& g, DistanceMatrix& d) |
223 | { |
224 | bgl_named_params<int,int> params(0); |
225 | return detail::floyd_warshall_init_dispatch(g, d, |
226 | get(edge_weight, g), params); |
227 | } |
228 | |
229 | |
230 | |
231 | |
232 | template <class VertexAndEdgeListGraph, class DistanceMatrix, |
233 | class P, class T, class R> |
234 | bool floyd_warshall_all_pairs_shortest_paths( |
235 | const VertexAndEdgeListGraph& g, DistanceMatrix& d, |
236 | const bgl_named_params<P, T, R>& params) |
237 | { |
238 | return detail::floyd_warshall_noninit_dispatch(g, d, |
239 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
240 | params); |
241 | } |
242 | |
243 | template <class VertexAndEdgeListGraph, class DistanceMatrix> |
244 | bool floyd_warshall_all_pairs_shortest_paths( |
245 | const VertexAndEdgeListGraph& g, DistanceMatrix& d) |
246 | { |
247 | bgl_named_params<int,int> params(0); |
248 | return detail::floyd_warshall_noninit_dispatch(g, d, |
249 | get(edge_weight, g), params); |
250 | } |
251 | |
252 | |
253 | } // namespace boost |
254 | |
255 | #endif |
256 | |
257 | |