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