// (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 |