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 | |
27 | closed_plus() : inf((std::numeric_limits<T>::max)()) { } |
28 | closed_plus(T inf) : inf(inf) { } |
29 | |
30 | 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> |
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 | bool relax(typename graph_traits<Graph>::edge_descriptor e, |
83 | const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d) |
84 | { |
85 | typedef typename property_traits<DistanceMap>::value_type D; |
86 | typedef closed_plus<D> Combine; |
87 | typedef std::less<D> Compare; |
88 | return relax(e, g, w, p, d, Combine(), Compare()); |
89 | } |
90 | |
91 | } // namespace boost |
92 | |
93 | #endif /* BOOST_GRAPH_RELAX_HPP */ |
94 | |