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
38namespace boost
39{
40namespace 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
76template < typename VertexListGraph, typename DistanceMatrix,
77 typename BinaryPredicate, typename BinaryFunction, typename Infinity,
78 typename Zero >
79bool 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
88template < typename VertexAndEdgeListGraph, typename DistanceMatrix,
89 typename WeightMap, typename BinaryPredicate, typename BinaryFunction,
90 typename Infinity, typename Zero >
91bool 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
142namespace 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
182template < class VertexListGraph, class DistanceMatrix, class P, class T,
183 class R >
184bool 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
193template < class VertexListGraph, class DistanceMatrix >
194bool 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
202template < class VertexAndEdgeListGraph, class DistanceMatrix, class P, class T,
203 class R >
204bool 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
212template < class VertexAndEdgeListGraph, class DistanceMatrix >
213bool 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

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