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/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> #include <boost/concept/assert.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) { BOOST_CONCEPT_ASSERT((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) { BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexAndEdgeListGraph >)); BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< VertexAndEdgeListGraph >)); BOOST_CONCEPT_ASSERT((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; WM inf = choose_param(get_param(params, distance_inf_t()), std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION()); 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 >(inf)), inf, 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; WM inf = choose_param(get_param(params, distance_inf_t()), std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION()); 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 >(inf)), inf, 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