]>
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 | ||
f67539c2 | 13 | template <class VertexListGraph, class DistanceMatrix, |
7c673cae FG |
14 | class P, class T, class R> |
15 | bool floyd_warshall_initialized_all_pairs_shortest_paths( | |
f67539c2 | 16 | const VertexListGraph& g, DistanceMatrix& d, |
7c673cae FG |
17 | const bgl_named_params<P, T, R>& params) |
18 | ||
19 | AND | |
20 | ||
f67539c2 | 21 | template <class VertexAndEdgeListGraph, class DistanceMatrix, |
7c673cae FG |
22 | class P, class T, class R> |
23 | bool floyd_warshall_all_pairs_shortest_paths( | |
f67539c2 | 24 | const VertexAndEdgeListGraph& g, DistanceMatrix& d, |
7c673cae FG |
25 | const bgl_named_params<P, T, R>& params) |
26 | */ | |
27 | ||
7c673cae FG |
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 | { | |
f67539c2 TL |
40 | namespace detail |
41 | { | |
42 | template < typename T, typename BinaryPredicate > | |
7c673cae FG |
43 | T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare) |
44 | { | |
f67539c2 TL |
45 | if (compare(x, y)) |
46 | return x; | |
47 | else | |
48 | return y; | |
7c673cae FG |
49 | } |
50 | ||
f67539c2 TL |
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) | |
7c673cae | 57 | { |
f67539c2 TL |
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 | ||
7c673cae | 69 | for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) |
f67539c2 TL |
70 | if (compare(d[*i][*i], zero)) |
71 | return false; | |
72 | return true; | |
7c673cae | 73 | } |
f67539c2 TL |
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 >)); | |
7c673cae | 84 | |
f67539c2 TL |
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++) | |
7c673cae | 112 | { |
f67539c2 TL |
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); | |
7c673cae | 121 | } |
f67539c2 TL |
122 | |
123 | bool is_undirected = is_same< | |
124 | typename graph_traits< VertexAndEdgeListGraph >::directed_category, | |
125 | undirected_tag >::value; | |
7c673cae FG |
126 | if (is_undirected) |
127 | { | |
f67539c2 TL |
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 | } | |
7c673cae | 137 | } |
f67539c2 TL |
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) | |
7c673cae | 149 | { |
f67539c2 TL |
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())); | |
7c673cae | 160 | } |
f67539c2 TL |
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) | |
7c673cae | 167 | { |
f67539c2 TL |
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())); | |
7c673cae | 178 | } |
7c673cae | 179 | |
f67539c2 | 180 | } // namespace detail |
7c673cae | 181 | |
f67539c2 TL |
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 | { | |
7c673cae | 188 | return detail::floyd_warshall_init_dispatch(g, d, |
f67539c2 TL |
189 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
190 | params); | |
191 | } | |
7c673cae | 192 | |
f67539c2 TL |
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 | { | |
7c673cae | 207 | return detail::floyd_warshall_noninit_dispatch(g, d, |
f67539c2 TL |
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 | } | |
7c673cae FG |
220 | |
221 | } // namespace boost | |
222 | ||
223 | #endif |