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 | #ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP |
29 | #define BOOST_GRAPH_FLOYD_WARSHALL_HPP |
30 | |
31 | #include <boost/property_map/property_map.hpp> |
32 | #include <boost/graph/graph_traits.hpp> |
33 | #include <boost/graph/named_function_params.hpp> |
34 | #include <boost/graph/graph_concepts.hpp> |
35 | #include <boost/graph/relax.hpp> |
36 | #include <boost/concept/assert.hpp> |
37 | |
38 | namespace boost |
39 | { |
40 | namespace detail |
41 | { |
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)) |
46 | return x; |
47 | else |
48 | return y; |
49 | } |
50 | |
51 | template < typename VertexListGraph, typename DistanceMatrix, |
52 | typename BinaryPredicate, typename BinaryFunction, typename Infinity, |
53 | typename Zero > |
54 | bool floyd_warshall_dispatch(const VertexListGraph& g, DistanceMatrix& d, |
55 | const BinaryPredicate& compare, const BinaryFunction& combine, |
56 | const Infinity& inf, const Zero& zero) |
57 | { |
58 | typename graph_traits< VertexListGraph >::vertex_iterator i, lasti, j, |
59 | lastj, k, lastk; |
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] = detail::min_with_compare(d[*i][*j], |
67 | combine(d[*i][*k], d[*k][*j]), compare); |
68 | |
69 | for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) |
70 | if (compare(d[*i][*i], zero)) |
71 | return false; |
72 | return true; |
73 | } |
74 | } |
75 | |
76 | template < typename VertexListGraph, typename DistanceMatrix, |
77 | typename BinaryPredicate, typename BinaryFunction, typename Infinity, |
78 | typename Zero > |
79 | bool floyd_warshall_initialized_all_pairs_shortest_paths( |
80 | const VertexListGraph& g, DistanceMatrix& d, const BinaryPredicate& compare, |
81 | const BinaryFunction& combine, const Infinity& inf, const Zero& zero) |
82 | { |
83 | BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexListGraph >)); |
84 | |
85 | return detail::floyd_warshall_dispatch(g, d, compare, combine, inf, zero); |
86 | } |
87 | |
88 | template < typename VertexAndEdgeListGraph, typename DistanceMatrix, |
89 | typename WeightMap, typename BinaryPredicate, typename BinaryFunction, |
90 | typename Infinity, typename Zero > |
91 | bool floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph& g, |
92 | DistanceMatrix& d, const WeightMap& w, const BinaryPredicate& compare, |
93 | const BinaryFunction& combine, const Infinity& inf, const Zero& zero) |
94 | { |
95 | BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexAndEdgeListGraph >)); |
96 | BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< VertexAndEdgeListGraph >)); |
97 | BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< VertexAndEdgeListGraph >)); |
98 | |
99 | typename graph_traits< VertexAndEdgeListGraph >::vertex_iterator firstv, |
100 | lastv, firstv2, lastv2; |
101 | typename graph_traits< VertexAndEdgeListGraph >::edge_iterator first, last; |
102 | |
103 | for (boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) |
104 | for (boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; |
105 | firstv2++) |
106 | d[*firstv][*firstv2] = inf; |
107 | |
108 | for (boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) |
109 | d[*firstv][*firstv] = zero; |
110 | |
111 | for (boost::tie(first, last) = edges(g); first != last; first++) |
112 | { |
113 | if (d[source(*first, g)][target(*first, g)] != inf) |
114 | { |
115 | d[source(*first, g)][target(*first, g)] |
116 | = detail::min_with_compare(get(w, *first), |
117 | d[source(*first, g)][target(*first, g)], compare); |
118 | } |
119 | else |
120 | d[source(*first, g)][target(*first, g)] = get(w, *first); |
121 | } |
122 | |
123 | bool is_undirected = is_same< |
124 | typename graph_traits< VertexAndEdgeListGraph >::directed_category, |
125 | undirected_tag >::value; |
126 | if (is_undirected) |
127 | { |
128 | for (boost::tie(first, last) = edges(g); first != last; first++) |
129 | { |
130 | if (d[target(*first, g)][source(*first, g)] != inf) |
131 | d[target(*first, g)][source(*first, g)] |
132 | = detail::min_with_compare(get(w, *first), |
133 | d[target(*first, g)][source(*first, g)], compare); |
134 | else |
135 | d[target(*first, g)][source(*first, g)] = get(w, *first); |
136 | } |
137 | } |
138 | |
139 | return detail::floyd_warshall_dispatch(g, d, compare, combine, inf, zero); |
140 | } |
141 | |
142 | namespace detail |
143 | { |
144 | template < class VertexListGraph, class DistanceMatrix, class WeightMap, |
145 | class P, class T, class R > |
146 | bool floyd_warshall_init_dispatch(const VertexListGraph& g, |
147 | DistanceMatrix& d, WeightMap /*w*/, |
148 | const bgl_named_params< P, T, R >& params) |
149 | { |
150 | typedef typename property_traits< WeightMap >::value_type WM; |
151 | WM inf = choose_param(get_param(params, distance_inf_t()), |
152 | std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION()); |
153 | |
154 | return floyd_warshall_initialized_all_pairs_shortest_paths(g, d, |
155 | choose_param( |
156 | get_param(params, distance_compare_t()), std::less< WM >()), |
157 | choose_param(get_param(params, distance_combine_t()), |
158 | closed_plus< WM >(inf)), |
159 | inf, choose_param(get_param(params, distance_zero_t()), WM())); |
160 | } |
161 | |
162 | template < class VertexAndEdgeListGraph, class DistanceMatrix, |
163 | class WeightMap, class P, class T, class R > |
164 | bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g, |
165 | DistanceMatrix& d, WeightMap w, |
166 | const bgl_named_params< P, T, R >& params) |
167 | { |
168 | typedef typename property_traits< WeightMap >::value_type WM; |
169 | |
170 | WM inf = choose_param(get_param(params, distance_inf_t()), |
171 | std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION()); |
172 | return floyd_warshall_all_pairs_shortest_paths(g, d, w, |
173 | choose_param( |
174 | get_param(params, distance_compare_t()), std::less< WM >()), |
175 | choose_param(get_param(params, distance_combine_t()), |
176 | closed_plus< WM >(inf)), |
177 | inf, choose_param(get_param(params, distance_zero_t()), WM())); |
178 | } |
179 | |
180 | } // namespace detail |
181 | |
182 | template < class VertexListGraph, class DistanceMatrix, class P, class T, |
183 | class R > |
184 | bool floyd_warshall_initialized_all_pairs_shortest_paths( |
185 | const VertexListGraph& g, DistanceMatrix& d, |
186 | const bgl_named_params< P, T, R >& params) |
187 | { |
188 | return detail::floyd_warshall_init_dispatch(g, d, |
189 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
190 | params); |
191 | } |
192 | |
193 | template < class VertexListGraph, class DistanceMatrix > |
194 | bool floyd_warshall_initialized_all_pairs_shortest_paths( |
195 | const VertexListGraph& g, DistanceMatrix& d) |
196 | { |
197 | bgl_named_params< int, int > params(0); |
198 | return detail::floyd_warshall_init_dispatch( |
199 | g, d, get(edge_weight, g), params); |
200 | } |
201 | |
202 | template < class VertexAndEdgeListGraph, class DistanceMatrix, class P, class T, |
203 | class R > |
204 | bool floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph& g, |
205 | DistanceMatrix& d, const bgl_named_params< P, T, R >& params) |
206 | { |
207 | return detail::floyd_warshall_noninit_dispatch(g, d, |
208 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
209 | params); |
210 | } |
211 | |
212 | template < class VertexAndEdgeListGraph, class DistanceMatrix > |
213 | bool floyd_warshall_all_pairs_shortest_paths( |
214 | const VertexAndEdgeListGraph& g, DistanceMatrix& d) |
215 | { |
216 | bgl_named_params< int, int > params(0); |
217 | return detail::floyd_warshall_noninit_dispatch( |
218 | g, d, get(edge_weight, g), params); |
219 | } |
220 | |
221 | } // namespace boost |
222 | |
223 | #endif |
224 | |