/usr/include/boost/graph/detail/geodesic.hpp is in libboost1.46-dev 1.46.1-7ubuntu3.
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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | // (C) Copyright 2007 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_GRAPH_DETAIL_GEODESIC_HPP
#define BOOST_GRAPH_DETAIL_GEODESIC_HPP
#include <functional>
#include <boost/config.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/numeric_values.hpp>
// TODO: Should this really be in detail?
namespace boost
{
// This is a very good discussion on centrality measures. While I can't
// say that this has been the motivating factor for the design and
// implementation of ths centrality framework, it does provide a single
// point of reference for defining things like degree and closeness
// centrality. Plus, the bibliography seems fairly complete.
//
// @article{citeulike:1144245,
// author = {Borgatti, Stephen P. and Everett, Martin G.},
// citeulike-article-id = {1144245},
// doi = {10.1016/j.socnet.2005.11.005},
// journal = {Social Networks},
// month = {October},
// number = {4},
// pages = {466--484},
// priority = {0},
// title = {A Graph-theoretic perspective on centrality},
// url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
// volume = {28},
// year = {2006}
// }
// }
namespace detail {
// Note that this assumes T == property_traits<DistanceMap>::value_type
// and that the args and return of combine are also T.
template <typename Graph,
typename DistanceMap,
typename Combinator,
typename Distance>
inline Distance
combine_distances(const Graph& g,
DistanceMap dist,
Combinator combine,
Distance init)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
function_requires< NumericValueConcept<Distance> >();
typedef numeric_values<Distance> DistanceNumbers;
function_requires< AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> >();
// If there's ever an infinite distance, then we simply return
// infinity. Note that this /will/ include the a non-zero
// distance-to-self in the combined values. However, this is usually
// zero, so it shouldn't be too problematic.
Distance ret = init;
VertexIterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
Vertex v = *i;
if(get(dist, v) != DistanceNumbers::infinity()) {
ret = combine(ret, get(dist, v));
}
else {
ret = DistanceNumbers::infinity();
break;
}
}
return ret;
}
// Similar to std::plus<T>, but maximizes parameters
// rather than adding them.
template <typename T>
struct maximize : public std::binary_function<T, T, T>
{
T operator ()(T x, T y) const
{ BOOST_USING_STD_MAX(); return max BOOST_PREVENT_MACRO_SUBSTITUTION (x, y); }
};
// Another helper, like maximize() to help abstract functional
// concepts. This is trivially instantiated for builtin numeric
// types, but should be specialized for those types that have
// discrete notions of reciprocals.
template <typename T>
struct reciprocal : public std::unary_function<T, T>
{
typedef std::unary_function<T, T> function_type;
typedef typename function_type::result_type result_type;
typedef typename function_type::argument_type argument_type;
T operator ()(T t)
{ return T(1) / t; }
};
} /* namespace detail */
// This type defines the basic facilities used for computing values
// based on the geodesic distances between vertices. Examples include
// closeness centrality and mean geodesic distance.
template <typename Graph, typename DistanceType, typename ResultType>
struct geodesic_measure
{
typedef DistanceType distance_type;
typedef ResultType result_type;
typedef typename graph_traits<Graph>::vertices_size_type size_type;
typedef numeric_values<distance_type> distance_values;
typedef numeric_values<result_type> result_values;
static inline distance_type infinite_distance()
{ return distance_values::infinity(); }
static inline result_type infinite_result()
{ return result_values::infinity(); }
static inline result_type zero_result()
{ return result_values::zero(); }
};
} /* namespace boost */
#endif
|