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
20 // The following version of the plus functor prevents
21 // problems due to overflow at positive infinity.
22
23 template < class T > 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 {
32 using namespace std;
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 >
relax(typename graph_traits<Graph>::edge_descriptor e,const Graph & g,const WeightMap & w,PredecessorMap & p,DistanceMap & d,const BinaryFunction & combine,const BinaryPredicate & compare)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))
62 {
63 put(d, v, combine(d_u, w_e));
64 if (compare(get(d, v), d_v))
65 {
66 put(p, v, u);
67 return true;
68 }
69 else
70 {
71 return false;
72 }
73 }
74 else if (is_undirected && compare(combine(d_v, w_e), d_u))
75 {
76 put(d, u, combine(d_v, w_e));
77 if (compare(get(d, u), d_u))
78 {
79 put(p, u, v);
80 return true;
81 }
82 else
83 {
84 return false;
85 }
86 }
87 else
88 return false;
89 }
90
91 template < class Graph, class WeightMap, class PredecessorMap,
92 class DistanceMap, 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)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);
105
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 {
112 put(d, v, combine(d_u, w_e));
113 if (compare(get(d, v), d_v))
114 {
115 put(p, v, u);
116 return true;
117 }
118 }
119 return false;
120 }
121
122 template < class Graph, class WeightMap, class PredecessorMap,
123 class DistanceMap >
relax(typename graph_traits<Graph>::edge_descriptor e,const Graph & g,WeightMap w,PredecessorMap p,DistanceMap d)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 }
132
133 } // namespace boost
134
135 #endif /* BOOST_GRAPH_RELAX_HPP */
136