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