1 //=======================================================================

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

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

     4 //

     5 // Distributed under the Boost Software License, Version 1.0. (See

     6 // accompanying file LICENSE_1_0.txt or copy at

     7 // http://www.boost.org/LICENSE_1_0.txt)

     8 //=======================================================================

     9 #ifndef BOOST_GRAPH_RELAX_HPP

    10 #define BOOST_GRAPH_RELAX_HPP

    11 

    12 #include <functional>

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

    14 #include <boost/graph/graph_traits.hpp>

    15 #include <boost/property_map.hpp>

    16 

    17 namespace boost {

    18 

    19     // The following version of the plus functor prevents

    20     // problems due to overflow at positive infinity.

    21 

    22     template <class T>

    23     struct closed_plus

    24     {

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

    26       template <class X>

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

    28 

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

    30         using namespace std;

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

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

    33           return inf;

    34         return a + b;

    35       }

    36     };

    37     

    38     template <class Graph, class WeightMap, 

    39             class PredecessorMap, class DistanceMap, 

    40             class BinaryFunction, class BinaryPredicate>

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

    42                const Graph& g, const WeightMap& w, 

    43                PredecessorMap& p, DistanceMap& d, 

    44                const BinaryFunction& combine, const BinaryPredicate& compare)

    45     {

    46       typedef typename graph_traits<Graph>::directed_category DirCat;

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

    48       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

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

    50       typedef typename property_traits<DistanceMap>::value_type D;

    51       typedef typename property_traits<WeightMap>::value_type W;

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

    53       W w_e = get(w, e);

    54       

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

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

    57         put(p, v, u);

    58         return true;

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

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

    61         put(p, u, v);

    62         return true;

    63       } else

    64         return false;

    65     }

    66     

    67     template <class Graph, class WeightMap, 

    68       class PredecessorMap, class DistanceMap>

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

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

    71     {

    72       typedef typename property_traits<DistanceMap>::value_type D;

    73       typedef closed_plus<D> Combine;

    74       typedef std::less<D> Compare;

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

    76     }

    77 

    78 } // namespace boost

    79 

    80 #endif /* BOOST_GRAPH_RELAX_HPP */