Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / relax.hpp
1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5 //
6 // This file is part of the Boost Graph Library
7 //
8 // You should have received a copy of the License Agreement for the
9 // Boost Graph Library along with the software; see the file LICENSE.
10 // If not, contact Office of Research, University of Notre Dame, Notre
11 // Dame, IN 46556.
12 //
13 // Permission to modify the code and to distribute modified code is
14 // granted, provided the text of this NOTICE is retained, a notice that
15 // the code was modified is included with the above COPYRIGHT NOTICE and
16 // with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
17 // file is distributed with the modified code.
18 //
19 // LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
20 // By way of example, but not limitation, Licensor MAKES NO
21 // REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
22 // PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
23 // OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
24 // OR OTHER RIGHTS.
25 //=======================================================================
26 //
27
28 #ifndef BOOST_GRAPH_RELAX_HPP
29 #define BOOST_GRAPH_RELAX_HPP
30
31 #include <functional>
32 #include <boost/limits.hpp> // for numeric limits
33 #include <boost/graph/graph_traits.hpp>
34 #include <boost/property_map.hpp>
35
36 namespace boost {
37
38     // The following version of the plus functor prevents
39     // problems due to overflow at positive infinity.
40
41     template <class T>
42     struct closed_plus
43     {
44       // std::abs just isn't portable :(
45       template <class X>
46       inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
47
48       T operator()(const T& a, const T& b) const {
49         using namespace std;
50         T inf = (numeric_limits<T>::max)();
51         if (b > 0 && my_abs(inf - a) < b)
52           return inf;
53         return a + b;
54       }
55     };
56     
57     template <class Graph, class WeightMap, 
58             class PredecessorMap, class DistanceMap, 
59             class BinaryFunction, class BinaryPredicate>
60     bool relax(typename graph_traits<Graph>::edge_descriptor e, 
61                const Graph& g, const WeightMap& w, 
62                PredecessorMap& p, DistanceMap& d, 
63                const BinaryFunction& combine, const BinaryPredicate& compare)
64     {
65       typedef typename graph_traits<Graph>::directed_category DirCat;
66       bool is_undirected = is_same<DirCat, undirected_tag>::value;
67       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
68       Vertex u = source(e, g), v = target(e, g);
69       typedef typename property_traits<DistanceMap>::value_type D;
70       typedef typename property_traits<WeightMap>::value_type W;
71       D d_u = get(d, u), d_v = get(d, v);
72       W w_e = get(w, e);
73       
74       if ( compare(combine(d_u, w_e), d_v) ) {
75         put(d, v, combine(d_u, w_e));
76         put(p, v, u);
77         return true;
78       } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
79         put(d, u, combine(d_v, w_e));
80         put(p, u, v);
81         return true;
82       } else
83         return false;
84     }
85     
86     template <class Graph, class WeightMap, 
87       class PredecessorMap, class DistanceMap>
88     bool relax(typename graph_traits<Graph>::edge_descriptor e,
89                const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
90     {
91       typedef typename property_traits<DistanceMap>::value_type D;
92       typedef closed_plus<D> Combine;
93       typedef std::less<D> Compare;
94       return relax(e, g, w, p, d, Combine(), Compare());
95     }
96
97 } // namespace boost
98
99 #endif /* BOOST_GRAPH_RELAX_HPP */