//======================================================================= | |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
//======================================================================= | |
#ifndef BOOST_GRAPH_RELAX_HPP | |
#define BOOST_GRAPH_RELAX_HPP | |
#include <functional> | |
#include <boost/limits.hpp> // for numeric limits | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/property_map/property_map.hpp> | |
namespace boost { | |
// The following version of the plus functor prevents | |
// problems due to overflow at positive infinity. | |
template <class T> | |
struct closed_plus | |
{ | |
T operator()(const T& a, const T& b) const { | |
using namespace std; | |
const T inf = (std::numeric_limits<T>::max)(); | |
if (a == inf) return inf; | |
if (b == inf) return inf; | |
return a + b; | |
} | |
}; | |
template <class Graph, class WeightMap, | |
class PredecessorMap, class DistanceMap, | |
class BinaryFunction, class BinaryPredicate> | |
bool relax(typename graph_traits<Graph>::edge_descriptor e, | |
const Graph& g, const WeightMap& w, | |
PredecessorMap& p, DistanceMap& d, | |
const BinaryFunction& combine, const BinaryPredicate& compare) | |
{ | |
typedef typename graph_traits<Graph>::directed_category DirCat; | |
bool is_undirected = is_same<DirCat, undirected_tag>::value; | |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
Vertex u = source(e, g), v = target(e, g); | |
typedef typename property_traits<DistanceMap>::value_type D; | |
typedef typename property_traits<WeightMap>::value_type W; | |
D d_u = get(d, u), d_v = get(d, v); | |
W w_e = get(w, e); | |
// The redundant gets in the return statements are to ensure that extra | |
// floating-point precision in x87 registers does not lead to relax() | |
// returning true when the distance did not actually change. | |
if ( compare(combine(d_u, w_e), d_v) ) { | |
put(d, v, combine(d_u, w_e)); | |
put(p, v, u); | |
return compare(get(d, v), d_v); | |
} else if (is_undirected && compare(combine(d_v, w_e), d_u)) { | |
put(d, u, combine(d_v, w_e)); | |
put(p, u, v); | |
return compare(get(d, u), d_u); | |
} else | |
return false; | |
} | |
template <class Graph, class WeightMap, | |
class PredecessorMap, class DistanceMap> | |
bool relax(typename graph_traits<Graph>::edge_descriptor e, | |
const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d) | |
{ | |
typedef typename property_traits<DistanceMap>::value_type D; | |
typedef closed_plus<D> Combine; | |
typedef std::less<D> Compare; | |
return relax(e, g, w, p, d, Combine(), Compare()); | |
} | |
} // namespace boost | |
#endif /* BOOST_GRAPH_RELAX_HPP */ |