boost/graph/floyd_warshall_shortest.hpp
// 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.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 (tie(k, lastk) = vertices(g); k != lastk; k++) for (tie(i, lasti) = vertices(g); i != lasti; i++) if(d[*i][*k] != inf) for (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 (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(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) for(tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++) d[*firstv][*firstv2] = inf; for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++) d[*firstv][*firstv] = zero; for(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(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