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/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 { operator ()boost::closed_plus25 T operator()(const T& a, const T& b) const { 26 using namespace std; 27 const T inf = (std::numeric_limits<T>::max)(); 28 if (a == inf) return inf; 29 if (b == inf) return inf; 30 return a + b; 31 } 32 }; 33 34 template <class Graph, class WeightMap, 35 class PredecessorMap, class DistanceMap, 36 class BinaryFunction, class BinaryPredicate> relax(typename graph_traits<Graph>::edge_descriptor e,const Graph & g,const WeightMap & w,PredecessorMap & p,DistanceMap & d,const BinaryFunction & combine,const BinaryPredicate & compare)37 bool relax(typename graph_traits<Graph>::edge_descriptor e, 38 const Graph& g, const WeightMap& w, 39 PredecessorMap& p, DistanceMap& d, 40 const BinaryFunction& combine, const BinaryPredicate& compare) 41 { 42 typedef typename graph_traits<Graph>::directed_category DirCat; 43 bool is_undirected = is_same<DirCat, undirected_tag>::value; 44 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 45 Vertex u = source(e, g), v = target(e, g); 46 typedef typename property_traits<DistanceMap>::value_type D; 47 typedef typename property_traits<WeightMap>::value_type W; 48 D d_u = get(d, u), d_v = get(d, v); 49 W w_e = get(w, e); 50 51 // The redundant gets in the return statements are to ensure that extra 52 // floating-point precision in x87 registers does not lead to relax() 53 // returning true when the distance did not actually change. 54 if ( compare(combine(d_u, w_e), d_v) ) { 55 put(d, v, combine(d_u, w_e)); 56 put(p, v, u); 57 return compare(get(d, v), d_v); 58 } else if (is_undirected && compare(combine(d_v, w_e), d_u)) { 59 put(d, u, combine(d_v, w_e)); 60 put(p, u, v); 61 return compare(get(d, u), d_u); 62 } else 63 return false; 64 } 65 66 template <class Graph, class WeightMap, 67 class PredecessorMap, class DistanceMap> relax(typename graph_traits<Graph>::edge_descriptor e,const Graph & g,WeightMap w,PredecessorMap p,DistanceMap d)68 bool relax(typename graph_traits<Graph>::edge_descriptor e, 69 const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d) 70 { 71 typedef typename property_traits<DistanceMap>::value_type D; 72 typedef closed_plus<D> Combine; 73 typedef std::less<D> Compare; 74 return relax(e, g, w, p, d, Combine(), Compare()); 75 } 76 77 } // namespace boost 78 79 #endif /* BOOST_GRAPH_RELAX_HPP */ 80