//=======================================================================

// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,

//

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

//=======================================================================

#ifndef BOOST_GRAPH_RELAX_HPP

#define BOOST_GRAPH_RELAX_HPP

#include <functional>

#include <boost/limits.hpp> // for numeric limits

#include <boost/graph/graph_traits.hpp>

#include <boost/property_map.hpp>

namespace boost {

    // The following version of the plus functor prevents

    // problems due to overflow at positive infinity.

    template <class T>

    struct closed_plus

    {

      // std::abs just isn't portable :(

      template <class X>

      inline X my_abs(const X& x) const { return x < 0 ? -x : x; }

      T operator()(const T& a, const T& b) const {

        using namespace std;

        T inf = (numeric_limits<T>::max)();

        if (b > 0 && my_abs(inf - a) < b)

          return inf;

        return a + b;

      }

    };

    template <class Graph, class WeightMap, 

            class PredecessorMap, class DistanceMap, 

            class BinaryFunction, class BinaryPredicate>

    bool relax(typename graph_traits<Graph>::edge_descriptor e, 

               const Graph& g, const WeightMap& w, 

               PredecessorMap& p, DistanceMap& d, 

               const BinaryFunction& combine, const BinaryPredicate& compare)

    {

      typedef typename graph_traits<Graph>::directed_category DirCat;

      bool is_undirected = is_same<DirCat, undirected_tag>::value;

      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

      Vertex u = source(e, g), v = target(e, g);

      typedef typename property_traits<DistanceMap>::value_type D;

      typedef typename property_traits<WeightMap>::value_type W;

      D d_u = get(d, u), d_v = get(d, v);

      W w_e = get(w, e);

      if ( compare(combine(d_u, w_e), d_v) ) {

        put(d, v, combine(d_u, w_e));

        put(p, v, u);

        return true;

      } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {

        put(d, u, combine(d_v, w_e));

        put(p, u, v);

        return true;

      } else

        return false;

    }

    template <class Graph, class WeightMap, 

      class PredecessorMap, class DistanceMap>

    bool relax(typename graph_traits<Graph>::edge_descriptor e,

               const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)

    {

      typedef typename property_traits<DistanceMap>::value_type D;

      typedef closed_plus<D> Combine;

      typedef std::less<D> Compare;

      return relax(e, g, w, p, d, Combine(), Compare());

    }

} // namespace boost

#endif /* BOOST_GRAPH_RELAX_HPP */