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