| // Copyright 2002 Rensselaer Polytechnic Institute |
| |
| // Distributed under the Boost Software License, Version 1.0. |
| // (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Authors: Lauren Foutz |
| // Scott Hill |
| |
| /* |
| This file implements the functions |
| |
| template <class VertexListGraph, class DistanceMatrix, |
| class P, class T, class R> |
| bool floyd_warshall_initialized_all_pairs_shortest_paths( |
| const VertexListGraph& g, DistanceMatrix& d, |
| const bgl_named_params<P, T, R>& params) |
| |
| AND |
| |
| template <class VertexAndEdgeListGraph, class DistanceMatrix, |
| class P, class T, class R> |
| bool floyd_warshall_all_pairs_shortest_paths( |
| const VertexAndEdgeListGraph& g, DistanceMatrix& d, |
| const bgl_named_params<P, T, R>& params) |
| */ |
| |
| |
| #ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP |
| #define BOOST_GRAPH_FLOYD_WARSHALL_HPP |
| |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/graph/named_function_params.hpp> |
| #include <boost/graph/graph_concepts.hpp> |
| #include <boost/graph/relax.hpp> |
| |
| namespace boost |
| { |
| namespace detail { |
| template<typename T, typename BinaryPredicate> |
| T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare) |
| { |
| if (compare(x, y)) return x; |
| else return y; |
| } |
| |
| template<typename VertexListGraph, typename DistanceMatrix, |
| typename BinaryPredicate, typename BinaryFunction, |
| typename Infinity, typename Zero> |
| bool floyd_warshall_dispatch(const VertexListGraph& g, |
| DistanceMatrix& d, const BinaryPredicate &compare, |
| const BinaryFunction &combine, const Infinity& inf, |
| const Zero& zero) |
| { |
| typename graph_traits<VertexListGraph>::vertex_iterator |
| i, lasti, j, lastj, k, lastk; |
| |
| |
| for (boost::tie(k, lastk) = vertices(g); k != lastk; k++) |
| for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) |
| if(d[*i][*k] != inf) |
| for (boost::tie(j, lastj) = vertices(g); j != lastj; j++) |
| if(d[*k][*j] != inf) |
| d[*i][*j] = |
| detail::min_with_compare(d[*i][*j], |
| combine(d[*i][*k], d[*k][*j]), |
| compare); |
| |
| |
| for (boost::tie(i, lasti) = vertices(g); i != lasti; i++) |
| if (compare(d[*i][*i], zero)) |
| return false; |
| return true; |
| } |
| } |
| |
| template <typename VertexListGraph, typename DistanceMatrix, |
| typename BinaryPredicate, typename BinaryFunction, |
| typename Infinity, typename Zero> |
| bool floyd_warshall_initialized_all_pairs_shortest_paths( |
| const VertexListGraph& g, DistanceMatrix& d, |
| const BinaryPredicate& compare, |
| const BinaryFunction& combine, const Infinity& inf, |
| const Zero& zero) |
| { |
| function_requires<VertexListGraphConcept<VertexListGraph> >(); |
| |
| return detail::floyd_warshall_dispatch(g, d, compare, combine, |
| inf, zero); |
| } |
| |
| |
| |
| template <typename VertexAndEdgeListGraph, typename DistanceMatrix, |
| typename WeightMap, typename BinaryPredicate, |
| typename BinaryFunction, typename Infinity, typename Zero> |
| bool 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) |
| { |
| function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >(); |
| function_requires<EdgeListGraphConcept<VertexAndEdgeListGraph> >(); |
| function_requires<IncidenceGraphConcept<VertexAndEdgeListGraph> >(); |
| |
| typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator |
| firstv, lastv, firstv2, lastv2; |
| typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last; |
| |
| |
| for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) |
| for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++) |
| d[*firstv][*firstv2] = inf; |
| |
| |
| for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) |
| d[*firstv][*firstv] = zero; |
| |
| |
| for(boost::tie(first, last) = edges(g); first != last; first++) |
| { |
| if (d[source(*first, g)][target(*first, g)] != inf) { |
| d[source(*first, g)][target(*first, g)] = |
| detail::min_with_compare( |
| get(w, *first), |
| d[source(*first, g)][target(*first, g)], |
| compare); |
| } else |
| d[source(*first, g)][target(*first, g)] = get(w, *first); |
| } |
| |
| bool is_undirected = is_same<typename |
| graph_traits<VertexAndEdgeListGraph>::directed_category, |
| undirected_tag>::value; |
| if (is_undirected) |
| { |
| for(boost::tie(first, last) = edges(g); first != last; first++) |
| { |
| if (d[target(*first, g)][source(*first, g)] != inf) |
| d[target(*first, g)][source(*first, g)] = |
| detail::min_with_compare( |
| get(w, *first), |
| d[target(*first, g)][source(*first, g)], |
| compare); |
| else |
| d[target(*first, g)][source(*first, g)] = get(w, *first); |
| } |
| } |
| |
| |
| return detail::floyd_warshall_dispatch(g, d, compare, combine, |
| inf, zero); |
| } |
| |
| |
| namespace detail { |
| template <class VertexListGraph, class DistanceMatrix, |
| class WeightMap, class P, class T, class R> |
| bool floyd_warshall_init_dispatch(const VertexListGraph& g, |
| DistanceMatrix& d, WeightMap /*w*/, |
| const bgl_named_params<P, T, R>& params) |
| { |
| typedef typename property_traits<WeightMap>::value_type WM; |
| |
| return floyd_warshall_initialized_all_pairs_shortest_paths(g, d, |
| choose_param(get_param(params, distance_compare_t()), |
| std::less<WM>()), |
| choose_param(get_param(params, distance_combine_t()), |
| closed_plus<WM>()), |
| choose_param(get_param(params, distance_inf_t()), |
| std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()), |
| choose_param(get_param(params, distance_zero_t()), |
| WM())); |
| } |
| |
| |
| |
| template <class VertexAndEdgeListGraph, class DistanceMatrix, |
| class WeightMap, class P, class T, class R> |
| bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g, |
| DistanceMatrix& d, WeightMap w, |
| const bgl_named_params<P, T, R>& params) |
| { |
| typedef typename property_traits<WeightMap>::value_type WM; |
| |
| return floyd_warshall_all_pairs_shortest_paths(g, d, w, |
| choose_param(get_param(params, distance_compare_t()), |
| std::less<WM>()), |
| choose_param(get_param(params, distance_combine_t()), |
| closed_plus<WM>()), |
| choose_param(get_param(params, distance_inf_t()), |
| std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()), |
| choose_param(get_param(params, distance_zero_t()), |
| WM())); |
| } |
| |
| |
| } // namespace detail |
| |
| |
| |
| template <class VertexListGraph, class DistanceMatrix, class P, |
| class T, class R> |
| bool floyd_warshall_initialized_all_pairs_shortest_paths( |
| const VertexListGraph& g, DistanceMatrix& d, |
| const bgl_named_params<P, T, R>& params) |
| { |
| return detail::floyd_warshall_init_dispatch(g, d, |
| choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
| params); |
| } |
| |
| template <class VertexListGraph, class DistanceMatrix> |
| bool floyd_warshall_initialized_all_pairs_shortest_paths( |
| const VertexListGraph& g, DistanceMatrix& d) |
| { |
| bgl_named_params<int,int> params(0); |
| return detail::floyd_warshall_init_dispatch(g, d, |
| get(edge_weight, g), params); |
| } |
| |
| |
| |
| |
| template <class VertexAndEdgeListGraph, class DistanceMatrix, |
| class P, class T, class R> |
| bool floyd_warshall_all_pairs_shortest_paths( |
| const VertexAndEdgeListGraph& g, DistanceMatrix& d, |
| const bgl_named_params<P, T, R>& params) |
| { |
| return detail::floyd_warshall_noninit_dispatch(g, d, |
| choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
| params); |
| } |
| |
| template <class VertexAndEdgeListGraph, class DistanceMatrix> |
| bool floyd_warshall_all_pairs_shortest_paths( |
| const VertexAndEdgeListGraph& g, DistanceMatrix& d) |
| { |
| bgl_named_params<int,int> params(0); |
| return detail::floyd_warshall_noninit_dispatch(g, d, |
| get(edge_weight, g), params); |
| } |
| |
| |
| } // namespace boost |
| |
| #endif |
| |