|
sl@0
|
1 |
//=======================================================================
|
|
sl@0
|
2 |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
|
sl@0
|
3 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
|
|
sl@0
|
4 |
//
|
|
sl@0
|
5 |
// Distributed under the Boost Software License, Version 1.0. (See
|
|
sl@0
|
6 |
// accompanying file LICENSE_1_0.txt or copy at
|
|
sl@0
|
7 |
// http://www.boost.org/LICENSE_1_0.txt)
|
|
sl@0
|
8 |
//=======================================================================
|
|
sl@0
|
9 |
#ifndef BOOST_GRAPH_RELAX_HPP
|
|
sl@0
|
10 |
#define BOOST_GRAPH_RELAX_HPP
|
|
sl@0
|
11 |
|
|
sl@0
|
12 |
#include <functional>
|
|
sl@0
|
13 |
#include <boost/limits.hpp> // for numeric limits
|
|
sl@0
|
14 |
#include <boost/graph/graph_traits.hpp>
|
|
sl@0
|
15 |
#include <boost/property_map.hpp>
|
|
sl@0
|
16 |
|
|
sl@0
|
17 |
namespace boost {
|
|
sl@0
|
18 |
|
|
sl@0
|
19 |
// The following version of the plus functor prevents
|
|
sl@0
|
20 |
// problems due to overflow at positive infinity.
|
|
sl@0
|
21 |
|
|
sl@0
|
22 |
template <class T>
|
|
sl@0
|
23 |
struct closed_plus
|
|
sl@0
|
24 |
{
|
|
sl@0
|
25 |
// std::abs just isn't portable :(
|
|
sl@0
|
26 |
template <class X>
|
|
sl@0
|
27 |
inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
|
|
sl@0
|
28 |
|
|
sl@0
|
29 |
T operator()(const T& a, const T& b) const {
|
|
sl@0
|
30 |
using namespace std;
|
|
sl@0
|
31 |
T inf = (numeric_limits<T>::max)();
|
|
sl@0
|
32 |
if (b > 0 && my_abs(inf - a) < b)
|
|
sl@0
|
33 |
return inf;
|
|
sl@0
|
34 |
return a + b;
|
|
sl@0
|
35 |
}
|
|
sl@0
|
36 |
};
|
|
sl@0
|
37 |
|
|
sl@0
|
38 |
template <class Graph, class WeightMap,
|
|
sl@0
|
39 |
class PredecessorMap, class DistanceMap,
|
|
sl@0
|
40 |
class BinaryFunction, class BinaryPredicate>
|
|
sl@0
|
41 |
bool relax(typename graph_traits<Graph>::edge_descriptor e,
|
|
sl@0
|
42 |
const Graph& g, const WeightMap& w,
|
|
sl@0
|
43 |
PredecessorMap& p, DistanceMap& d,
|
|
sl@0
|
44 |
const BinaryFunction& combine, const BinaryPredicate& compare)
|
|
sl@0
|
45 |
{
|
|
sl@0
|
46 |
typedef typename graph_traits<Graph>::directed_category DirCat;
|
|
sl@0
|
47 |
bool is_undirected = is_same<DirCat, undirected_tag>::value;
|
|
sl@0
|
48 |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
|
|
sl@0
|
49 |
Vertex u = source(e, g), v = target(e, g);
|
|
sl@0
|
50 |
typedef typename property_traits<DistanceMap>::value_type D;
|
|
sl@0
|
51 |
typedef typename property_traits<WeightMap>::value_type W;
|
|
sl@0
|
52 |
D d_u = get(d, u), d_v = get(d, v);
|
|
sl@0
|
53 |
W w_e = get(w, e);
|
|
sl@0
|
54 |
|
|
sl@0
|
55 |
if ( compare(combine(d_u, w_e), d_v) ) {
|
|
sl@0
|
56 |
put(d, v, combine(d_u, w_e));
|
|
sl@0
|
57 |
put(p, v, u);
|
|
sl@0
|
58 |
return true;
|
|
sl@0
|
59 |
} else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
|
|
sl@0
|
60 |
put(d, u, combine(d_v, w_e));
|
|
sl@0
|
61 |
put(p, u, v);
|
|
sl@0
|
62 |
return true;
|
|
sl@0
|
63 |
} else
|
|
sl@0
|
64 |
return false;
|
|
sl@0
|
65 |
}
|
|
sl@0
|
66 |
|
|
sl@0
|
67 |
template <class Graph, class WeightMap,
|
|
sl@0
|
68 |
class PredecessorMap, class DistanceMap>
|
|
sl@0
|
69 |
bool relax(typename graph_traits<Graph>::edge_descriptor e,
|
|
sl@0
|
70 |
const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
|
|
sl@0
|
71 |
{
|
|
sl@0
|
72 |
typedef typename property_traits<DistanceMap>::value_type D;
|
|
sl@0
|
73 |
typedef closed_plus<D> Combine;
|
|
sl@0
|
74 |
typedef std::less<D> Compare;
|
|
sl@0
|
75 |
return relax(e, g, w, p, d, Combine(), Compare());
|
|
sl@0
|
76 |
}
|
|
sl@0
|
77 |
|
|
sl@0
|
78 |
} // namespace boost
|
|
sl@0
|
79 |
|
|
sl@0
|
80 |
#endif /* BOOST_GRAPH_RELAX_HPP */
|