| // 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 | |