1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/relax.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,80 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +#ifndef BOOST_GRAPH_RELAX_HPP
    1.13 +#define BOOST_GRAPH_RELAX_HPP
    1.14 +
    1.15 +#include <functional>
    1.16 +#include <boost/limits.hpp> // for numeric limits
    1.17 +#include <boost/graph/graph_traits.hpp>
    1.18 +#include <boost/property_map.hpp>
    1.19 +
    1.20 +namespace boost {
    1.21 +
    1.22 +    // The following version of the plus functor prevents
    1.23 +    // problems due to overflow at positive infinity.
    1.24 +
    1.25 +    template <class T>
    1.26 +    struct closed_plus
    1.27 +    {
    1.28 +      // std::abs just isn't portable :(
    1.29 +      template <class X>
    1.30 +      inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
    1.31 +
    1.32 +      T operator()(const T& a, const T& b) const {
    1.33 +        using namespace std;
    1.34 +        T inf = (numeric_limits<T>::max)();
    1.35 +        if (b > 0 && my_abs(inf - a) < b)
    1.36 +          return inf;
    1.37 +        return a + b;
    1.38 +      }
    1.39 +    };
    1.40 +    
    1.41 +    template <class Graph, class WeightMap, 
    1.42 +            class PredecessorMap, class DistanceMap, 
    1.43 +            class BinaryFunction, class BinaryPredicate>
    1.44 +    bool relax(typename graph_traits<Graph>::edge_descriptor e, 
    1.45 +               const Graph& g, const WeightMap& w, 
    1.46 +               PredecessorMap& p, DistanceMap& d, 
    1.47 +               const BinaryFunction& combine, const BinaryPredicate& compare)
    1.48 +    {
    1.49 +      typedef typename graph_traits<Graph>::directed_category DirCat;
    1.50 +      bool is_undirected = is_same<DirCat, undirected_tag>::value;
    1.51 +      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    1.52 +      Vertex u = source(e, g), v = target(e, g);
    1.53 +      typedef typename property_traits<DistanceMap>::value_type D;
    1.54 +      typedef typename property_traits<WeightMap>::value_type W;
    1.55 +      D d_u = get(d, u), d_v = get(d, v);
    1.56 +      W w_e = get(w, e);
    1.57 +      
    1.58 +      if ( compare(combine(d_u, w_e), d_v) ) {
    1.59 +        put(d, v, combine(d_u, w_e));
    1.60 +        put(p, v, u);
    1.61 +        return true;
    1.62 +      } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
    1.63 +        put(d, u, combine(d_v, w_e));
    1.64 +        put(p, u, v);
    1.65 +        return true;
    1.66 +      } else
    1.67 +        return false;
    1.68 +    }
    1.69 +    
    1.70 +    template <class Graph, class WeightMap, 
    1.71 +      class PredecessorMap, class DistanceMap>
    1.72 +    bool relax(typename graph_traits<Graph>::edge_descriptor e,
    1.73 +               const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
    1.74 +    {
    1.75 +      typedef typename property_traits<DistanceMap>::value_type D;
    1.76 +      typedef closed_plus<D> Combine;
    1.77 +      typedef std::less<D> Compare;
    1.78 +      return relax(e, g, w, p, d, Combine(), Compare());
    1.79 +    }
    1.80 +
    1.81 +} // namespace boost
    1.82 +
    1.83 +#endif /* BOOST_GRAPH_RELAX_HPP */