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
39namespace 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
257

source code of boost/boost/graph/floyd_warshall_shortest.hpp