/usr/include/boost/graph/relax.hpp is in libboost1.55-dev 1.55.0+dfsg-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | //=======================================================================
// 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
{
const T inf;
closed_plus() : inf((std::numeric_limits<T>::max)()) { }
closed_plus(T inf) : inf(inf) { }
T operator()(const T& a, const T& b) const {
using namespace std;
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;
const D d_u = get(d, u);
const D d_v = get(d, v);
const W& w_e = get(w, e);
// The seemingly redundant comparisons after the distance puts 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));
if (compare(get(d, v), d_v)) {
put(p, v, u);
return true;
} else {
return false;
}
} else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
put(d, u, combine(d_v, w_e));
if (compare(get(d, u), d_u)) {
put(p, u, v);
return true;
} else {
return false;
}
} 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 */
|