Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: #ifndef BOOST_GRAPH_RELAX_HPP
Chris@16: #define BOOST_GRAPH_RELAX_HPP
Chris@16: 
Chris@16: #include <functional>
Chris@16: #include <boost/limits.hpp> // for numeric limits
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:     // The following version of the plus functor prevents
Chris@16:     // problems due to overflow at positive infinity.
Chris@16: 
Chris@16:     template <class T>
Chris@16:     struct closed_plus
Chris@16:     {
Chris@16:       const T inf;
Chris@16: 
Chris@16:       closed_plus() : inf((std::numeric_limits<T>::max)()) { }
Chris@16:       closed_plus(T inf) : inf(inf) { }
Chris@16: 
Chris@16:       T operator()(const T& a, const T& b) const {
Chris@16:         using namespace std;
Chris@16:        if (a == inf) return inf;
Chris@16:        if (b == inf) return inf;
Chris@16:        return a + b;
Chris@16:       }
Chris@16:     };
Chris@16:     
Chris@16:     template <class Graph, class WeightMap, 
Chris@16:             class PredecessorMap, class DistanceMap, 
Chris@16:             class BinaryFunction, class BinaryPredicate>
Chris@16:     bool relax(typename graph_traits<Graph>::edge_descriptor e, 
Chris@16:                const Graph& g, const WeightMap& w, 
Chris@16:                PredecessorMap& p, DistanceMap& d, 
Chris@16:                const BinaryFunction& combine, const BinaryPredicate& compare)
Chris@16:     {
Chris@16:       typedef typename graph_traits<Graph>::directed_category DirCat;
Chris@16:       bool is_undirected = is_same<DirCat, undirected_tag>::value;
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:       Vertex u = source(e, g), v = target(e, g);
Chris@16:       typedef typename property_traits<DistanceMap>::value_type D;
Chris@16:       typedef typename property_traits<WeightMap>::value_type W;
Chris@16:       const D d_u = get(d, u);
Chris@16:       const D d_v = get(d, v);
Chris@16:       const W& w_e = get(w, e);
Chris@16:       
Chris@16:       // The seemingly redundant comparisons after the distance puts are to
Chris@16:       // ensure that extra floating-point precision in x87 registers does not
Chris@16:       // lead to relax() returning true when the distance did not actually
Chris@16:       // change.
Chris@16:       if ( compare(combine(d_u, w_e), d_v) ) {
Chris@16:         put(d, v, combine(d_u, w_e));
Chris@16:         if (compare(get(d, v), d_v)) {
Chris@16:           put(p, v, u);
Chris@16:           return true;
Chris@16:         } else {
Chris@16:           return false;
Chris@16:         }
Chris@16:       } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
Chris@16:         put(d, u, combine(d_v, w_e));
Chris@16:         if (compare(get(d, u), d_u)) {
Chris@16:           put(p, u, v);
Chris@16:           return true;
Chris@16:         } else {
Chris@16:           return false;
Chris@16:         }
Chris@16:       } else
Chris@16:         return false;
Chris@16:     }
Chris@16:     
Chris@16:     template <class Graph, class WeightMap, 
Chris@16:       class PredecessorMap, class DistanceMap>
Chris@16:     bool relax(typename graph_traits<Graph>::edge_descriptor e,
Chris@16:                const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
Chris@16:     {
Chris@16:       typedef typename property_traits<DistanceMap>::value_type D;
Chris@16:       typedef closed_plus<D> Combine;
Chris@16:       typedef std::less<D> Compare;
Chris@16:       return relax(e, g, w, p, d, Combine(), Compare());
Chris@16:     }
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif /* BOOST_GRAPH_RELAX_HPP */