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 { 25 const T inf; 26 closed_plusboost::closed_plus27 closed_plus() : inf((std::numeric_limits<T>::max)()) { } closed_plusboost::closed_plus28 closed_plus(T inf) : inf(inf) { } 29 operator ()boost::closed_plus30 T operator()(const T& a, const T& b) const { 31 using namespace std; 32 if (a == inf) return inf; 33 if (b == inf) 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> relax(typename graph_traits<Graph>::edge_descriptor e,const Graph & g,const WeightMap & w,PredecessorMap & p,DistanceMap & d,const BinaryFunction & combine,const BinaryPredicate & compare)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 const D d_u = get(d, u); 53 const D d_v = get(d, v); 54 const W& w_e = get(w, e); 55 56 // The seemingly redundant comparisons after the distance puts are to 57 // ensure that extra floating-point precision in x87 registers does not 58 // lead to relax() returning true when the distance did not actually 59 // change. 60 if ( compare(combine(d_u, w_e), d_v) ) { 61 put(d, v, combine(d_u, w_e)); 62 if (compare(get(d, v), d_v)) { 63 put(p, v, u); 64 return true; 65 } else { 66 return false; 67 } 68 } else if (is_undirected && compare(combine(d_v, w_e), d_u)) { 69 put(d, u, combine(d_v, w_e)); 70 if (compare(get(d, u), d_u)) { 71 put(p, u, v); 72 return true; 73 } else { 74 return false; 75 } 76 } else 77 return false; 78 } 79 80 template <class Graph, class WeightMap, 81 class PredecessorMap, class DistanceMap, 82 class BinaryFunction, class BinaryPredicate> relax_target(typename graph_traits<Graph>::edge_descriptor e,const Graph & g,const WeightMap & w,PredecessorMap & p,DistanceMap & d,const BinaryFunction & combine,const BinaryPredicate & compare)83 bool relax_target(typename graph_traits<Graph>::edge_descriptor e, 84 const Graph& g, const WeightMap& w, 85 PredecessorMap& p, DistanceMap& d, 86 const BinaryFunction& combine, const BinaryPredicate& compare) 87 { 88 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 89 typedef typename property_traits<DistanceMap>::value_type D; 90 typedef typename property_traits<WeightMap>::value_type W; 91 const Vertex u = source(e, g); 92 const Vertex v = target(e, g); 93 const D d_u = get(d, u); 94 const D d_v = get(d, v); 95 const W& w_e = get(w, e); 96 97 // The seemingly redundant comparisons after the distance puts are to 98 // ensure that extra floating-point precision in x87 registers does not 99 // lead to relax() returning true when the distance did not actually 100 // change. 101 if (compare(combine(d_u, w_e), d_v)) { 102 put(d, v, combine(d_u, w_e)); 103 if (compare(get(d, v), d_v)) { 104 put(p, v, u); 105 return true; 106 } 107 } 108 return false; 109 } 110 111 template <class Graph, class WeightMap, 112 class PredecessorMap, class DistanceMap> relax(typename graph_traits<Graph>::edge_descriptor e,const Graph & g,WeightMap w,PredecessorMap p,DistanceMap d)113 bool relax(typename graph_traits<Graph>::edge_descriptor e, 114 const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d) 115 { 116 typedef typename property_traits<DistanceMap>::value_type D; 117 typedef closed_plus<D> Combine; 118 typedef std::less<D> Compare; 119 return relax(e, g, w, p, d, Combine(), Compare()); 120 } 121 122 } // namespace boost 123 124 #endif /* BOOST_GRAPH_RELAX_HPP */ 125