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