1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
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
13 #include <boost/limits.hpp> // for numeric limits
14 #include <boost/graph/graph_traits.hpp>
15 #include <boost/property_map.hpp>
19 // The following version of the plus functor prevents
20 // problems due to overflow at positive infinity.
25 // std::abs just isn't portable :(
27 inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
29 T operator()(const T& a, const T& b) const {
31 T inf = (numeric_limits<T>::max)();
32 if (b > 0 && my_abs(inf - a) < b)
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)
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);
55 if ( compare(combine(d_u, w_e), d_v) ) {
56 put(d, v, combine(d_u, w_e));
59 } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
60 put(d, u, combine(d_v, w_e));
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)
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());
80 #endif /* BOOST_GRAPH_RELAX_HPP */