]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |