/usr/include/boost/graph/eccentricity.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 | // (C) Copyright 2007-2009 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_ECCENTRICITY_HPP
#define BOOST_GRAPH_ECCENTRICITY_HPP
#include <boost/utility.hpp>
#include <boost/config.hpp>
#include <boost/graph/detail/geodesic.hpp>
namespace boost
{
template <typename Graph,
typename DistanceMap,
typename Combinator>
inline typename property_traits<DistanceMap>::value_type
eccentricity(const Graph& g, DistanceMap dist, Combinator combine)
{
function_requires< GraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
typedef typename property_traits<DistanceMap>::value_type Distance;
return detail::combine_distances(g, dist, combine, Distance(0));
}
template <typename Graph, typename DistanceMap>
inline typename property_traits<DistanceMap>::value_type
eccentricity(const Graph& g, DistanceMap dist)
{
function_requires< GraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
function_requires< ReadablePropertyMapConcept<DistanceMap,Vertex> >();
typedef typename property_traits<DistanceMap>::value_type Distance;
return eccentricity(g, dist, detail::maximize<Distance>());
}
template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
inline std::pair<typename property_traits<EccentricityMap>::value_type,
typename property_traits<EccentricityMap>::value_type>
all_eccentricities(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
function_requires< ReadablePropertyMapConcept<DistanceMatrix,Vertex> >();
typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
function_requires< WritablePropertyMapConcept<EccentricityMap,Vertex> >();
typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
BOOST_USING_STD_MIN();
BOOST_USING_STD_MAX();
Eccentricity
r = numeric_values<Eccentricity>::infinity(),
d = numeric_values<Eccentricity>::zero();
VertexIterator i, end;
boost::tie(i, end) = vertices(g);
for(boost::tie(i, end) = vertices(g); i != end; ++i) {
DistanceMap dm = get(dist, *i);
Eccentricity e = eccentricity(g, dm);
put(ecc, *i, e);
// track the radius and diameter at the same time
r = min BOOST_PREVENT_MACRO_SUBSTITUTION (r, e);
d = max BOOST_PREVENT_MACRO_SUBSTITUTION (d, e);
}
return std::make_pair(r, d);
}
template <typename Graph, typename EccentricityMap>
inline std::pair<typename property_traits<EccentricityMap>::value_type,
typename property_traits<EccentricityMap>::value_type>
radius_and_diameter(const Graph& g, EccentricityMap ecc)
{
function_requires< VertexListGraphConcept<Graph> >();
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
function_requires< ReadablePropertyMapConcept<EccentricityMap, Vertex> >();
typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
BOOST_USING_STD_MIN();
BOOST_USING_STD_MAX();
VertexIterator i, end;
boost::tie(i, end) = vertices(g);
Eccentricity radius = get(ecc, *i);
Eccentricity diameter = get(ecc, *i);
for(i = boost::next(i); i != end; ++i) {
Eccentricity cur = get(ecc, *i);
radius = min BOOST_PREVENT_MACRO_SUBSTITUTION (radius, cur);
diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION (diameter, cur);
}
return std::make_pair(radius, diameter);
}
template <typename Graph, typename EccentricityMap>
inline typename property_traits<EccentricityMap>::value_type
radius(const Graph& g, EccentricityMap ecc)
{ return radius_and_diameter(g, ecc).first; }
template <typename Graph, typename EccentricityMap>
inline typename property_traits<EccentricityMap>::value_type
diameter(const Graph& g, EccentricityMap ecc)
{ return radius_and_diameter(g, ecc).second; }
} /* namespace boost */
#endif
|