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 >
min_with_compare(const T & x,const T & y,const BinaryPredicate & compare)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 >
floyd_warshall_dispatch(const VertexListGraph & g,DistanceMatrix & d,const BinaryPredicate & compare,const BinaryFunction & combine,const Infinity & inf,const Zero & 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 >
floyd_warshall_initialized_all_pairs_shortest_paths(const VertexListGraph & g,DistanceMatrix & d,const BinaryPredicate & compare,const BinaryFunction & combine,const Infinity & inf,const Zero & 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 >
floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph & g,DistanceMatrix & d,const WeightMap & w,const BinaryPredicate & compare,const BinaryFunction & combine,const Infinity & inf,const Zero & 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 >
floyd_warshall_init_dispatch(const VertexListGraph & g,DistanceMatrix & d,WeightMap,const bgl_named_params<P,T,R> & params)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 >
floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph & g,DistanceMatrix & d,WeightMap w,const bgl_named_params<P,T,R> & params)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 >
floyd_warshall_initialized_all_pairs_shortest_paths(const VertexListGraph & g,DistanceMatrix & d,const bgl_named_params<P,T,R> & params)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 >
floyd_warshall_initialized_all_pairs_shortest_paths(const VertexListGraph & g,DistanceMatrix & d)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 >
floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph & g,DistanceMatrix & d,const bgl_named_params<P,T,R> & params)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 >
floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph & g,DistanceMatrix & d)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