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