]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
17 | namespace boost |
18 | { | |
7c673cae | 19 | |
f67539c2 TL |
20 | // The following version of the plus functor prevents |
21 | // problems due to overflow at positive infinity. | |
7c673cae | 22 | |
f67539c2 TL |
23 | template < class T > struct closed_plus |
24 | { | |
25 | const T inf; | |
7c673cae | 26 | |
f67539c2 TL |
27 | closed_plus() : inf((std::numeric_limits< T >::max)()) {} |
28 | closed_plus(T inf) : inf(inf) {} | |
7c673cae | 29 | |
f67539c2 TL |
30 | T operator()(const T& a, const T& b) const |
31 | { | |
7c673cae | 32 | using namespace std; |
f67539c2 TL |
33 | if (a == inf) |
34 | return inf; | |
35 | if (b == inf) | |
36 | return inf; | |
37 | return a + b; | |
38 | } | |
39 | }; | |
40 | ||
41 | template < class Graph, class WeightMap, class PredecessorMap, | |
42 | class DistanceMap, class BinaryFunction, class BinaryPredicate > | |
43 | bool relax(typename graph_traits< Graph >::edge_descriptor e, const Graph& g, | |
44 | const WeightMap& w, PredecessorMap& p, DistanceMap& d, | |
45 | const BinaryFunction& combine, const BinaryPredicate& compare) | |
46 | { | |
47 | typedef typename graph_traits< Graph >::directed_category DirCat; | |
48 | bool is_undirected = is_same< DirCat, undirected_tag >::value; | |
49 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; | |
50 | Vertex u = source(e, g), v = target(e, g); | |
51 | typedef typename property_traits< DistanceMap >::value_type D; | |
52 | typedef typename property_traits< WeightMap >::value_type W; | |
53 | const D d_u = get(d, u); | |
54 | const D d_v = get(d, v); | |
55 | const W& w_e = get(w, e); | |
56 | ||
57 | // The seemingly redundant comparisons after the distance puts are to | |
58 | // ensure that extra floating-point precision in x87 registers does not | |
59 | // lead to relax() returning true when the distance did not actually | |
60 | // change. | |
61 | if (compare(combine(d_u, w_e), d_v)) | |
7c673cae | 62 | { |
7c673cae | 63 | put(d, v, combine(d_u, w_e)); |
f67539c2 TL |
64 | if (compare(get(d, v), d_v)) |
65 | { | |
66 | put(p, v, u); | |
67 | return true; | |
68 | } | |
69 | else | |
70 | { | |
71 | return false; | |
7c673cae | 72 | } |
f67539c2 TL |
73 | } |
74 | else if (is_undirected && compare(combine(d_v, w_e), d_u)) | |
75 | { | |
7c673cae | 76 | put(d, u, combine(d_v, w_e)); |
f67539c2 TL |
77 | if (compare(get(d, u), d_u)) |
78 | { | |
79 | put(p, u, v); | |
80 | return true; | |
81 | } | |
82 | else | |
83 | { | |
84 | return false; | |
7c673cae | 85 | } |
7c673cae | 86 | } |
f67539c2 TL |
87 | else |
88 | return false; | |
89 | } | |
92f5a8d4 | 90 | |
f67539c2 TL |
91 | template < class Graph, class WeightMap, class PredecessorMap, |
92 | class DistanceMap, class BinaryFunction, class BinaryPredicate > | |
93 | bool relax_target(typename graph_traits< Graph >::edge_descriptor e, | |
94 | const Graph& g, const WeightMap& w, PredecessorMap& p, DistanceMap& d, | |
95 | const BinaryFunction& combine, const BinaryPredicate& compare) | |
96 | { | |
97 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; | |
98 | typedef typename property_traits< DistanceMap >::value_type D; | |
99 | typedef typename property_traits< WeightMap >::value_type W; | |
100 | const Vertex u = source(e, g); | |
101 | const Vertex v = target(e, g); | |
102 | const D d_u = get(d, u); | |
103 | const D d_v = get(d, v); | |
104 | const W& w_e = get(w, e); | |
92f5a8d4 | 105 | |
f67539c2 TL |
106 | // The seemingly redundant comparisons after the distance puts are to |
107 | // ensure that extra floating-point precision in x87 registers does not | |
108 | // lead to relax() returning true when the distance did not actually | |
109 | // change. | |
110 | if (compare(combine(d_u, w_e), d_v)) | |
111 | { | |
92f5a8d4 | 112 | put(d, v, combine(d_u, w_e)); |
f67539c2 TL |
113 | if (compare(get(d, v), d_v)) |
114 | { | |
115 | put(p, v, u); | |
116 | return true; | |
92f5a8d4 | 117 | } |
7c673cae | 118 | } |
f67539c2 TL |
119 | return false; |
120 | } | |
121 | ||
122 | template < class Graph, class WeightMap, class PredecessorMap, | |
123 | class DistanceMap > | |
124 | bool relax(typename graph_traits< Graph >::edge_descriptor e, const Graph& g, | |
125 | WeightMap w, PredecessorMap p, DistanceMap d) | |
126 | { | |
127 | typedef typename property_traits< DistanceMap >::value_type D; | |
128 | typedef closed_plus< D > Combine; | |
129 | typedef std::less< D > Compare; | |
130 | return relax(e, g, w, p, d, Combine(), Compare()); | |
131 | } | |
7c673cae FG |
132 | |
133 | } // namespace boost | |
134 | ||
135 | #endif /* BOOST_GRAPH_RELAX_HPP */ |