williamr@2: //=======================================================================
williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: #ifndef BOOST_GRAPH_RELAX_HPP
williamr@2: #define BOOST_GRAPH_RELAX_HPP
williamr@2: 
williamr@2: #include <functional>
williamr@2: #include <boost/limits.hpp> // for numeric limits
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/property_map.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:     // The following version of the plus functor prevents
williamr@2:     // problems due to overflow at positive infinity.
williamr@2: 
williamr@2:     template <class T>
williamr@2:     struct closed_plus
williamr@2:     {
williamr@2:       // std::abs just isn't portable :(
williamr@2:       template <class X>
williamr@2:       inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
williamr@2: 
williamr@2:       T operator()(const T& a, const T& b) const {
williamr@2:         using namespace std;
williamr@2:         T inf = (numeric_limits<T>::max)();
williamr@2:         if (b > 0 && my_abs(inf - a) < b)
williamr@2:           return inf;
williamr@2:         return a + b;
williamr@2:       }
williamr@2:     };
williamr@2:     
williamr@2:     template <class Graph, class WeightMap, 
williamr@2:             class PredecessorMap, class DistanceMap, 
williamr@2:             class BinaryFunction, class BinaryPredicate>
williamr@2:     bool relax(typename graph_traits<Graph>::edge_descriptor e, 
williamr@2:                const Graph& g, const WeightMap& w, 
williamr@2:                PredecessorMap& p, DistanceMap& d, 
williamr@2:                const BinaryFunction& combine, const BinaryPredicate& compare)
williamr@2:     {
williamr@2:       typedef typename graph_traits<Graph>::directed_category DirCat;
williamr@2:       bool is_undirected = is_same<DirCat, undirected_tag>::value;
williamr@2:       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2:       Vertex u = source(e, g), v = target(e, g);
williamr@2:       typedef typename property_traits<DistanceMap>::value_type D;
williamr@2:       typedef typename property_traits<WeightMap>::value_type W;
williamr@2:       D d_u = get(d, u), d_v = get(d, v);
williamr@2:       W w_e = get(w, e);
williamr@2:       
williamr@2:       if ( compare(combine(d_u, w_e), d_v) ) {
williamr@2:         put(d, v, combine(d_u, w_e));
williamr@2:         put(p, v, u);
williamr@2:         return true;
williamr@2:       } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
williamr@2:         put(d, u, combine(d_v, w_e));
williamr@2:         put(p, u, v);
williamr@2:         return true;
williamr@2:       } else
williamr@2:         return false;
williamr@2:     }
williamr@2:     
williamr@2:     template <class Graph, class WeightMap, 
williamr@2:       class PredecessorMap, class DistanceMap>
williamr@2:     bool relax(typename graph_traits<Graph>::edge_descriptor e,
williamr@2:                const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
williamr@2:     {
williamr@2:       typedef typename property_traits<DistanceMap>::value_type D;
williamr@2:       typedef closed_plus<D> Combine;
williamr@2:       typedef std::less<D> Compare;
williamr@2:       return relax(e, g, w, p, d, Combine(), Compare());
williamr@2:     }
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif /* BOOST_GRAPH_RELAX_HPP */