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