1 // (C) Copyright 2007 Andrew Sutton
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0 (See accompanying file
5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
7 #ifndef BOOST_GRAPH_DETAIL_GEODESIC_HPP
8 #define BOOST_GRAPH_DETAIL_GEODESIC_HPP
11 #include <boost/config.hpp>
12 #include <boost/graph/graph_concepts.hpp>
13 #include <boost/graph/numeric_values.hpp>
14 #include <boost/concept/assert.hpp>
16 // TODO: Should this really be in detail?
20 // This is a very good discussion on centrality measures. While I can't
21 // say that this has been the motivating factor for the design and
22 // implementation of ths centrality framework, it does provide a single
23 // point of reference for defining things like degree and closeness
24 // centrality. Plus, the bibliography seems fairly complete.
26 // @article{citeulike:1144245,
27 // author = {Borgatti, Stephen P. and Everett, Martin G.},
28 // citeulike-article-id = {1144245},
29 // doi = {10.1016/j.socnet.2005.11.005},
30 // journal = {Social Networks},
33 // pages = {466--484},
35 // title = {A Graph-theoretic perspective on centrality},
36 // url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
43 // Note that this assumes T == property_traits<DistanceMap>::value_type
44 // and that the args and return of combine are also T.
45 template <typename Graph,
50 combine_distances(const Graph& g,
55 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
56 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
57 typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
58 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
59 BOOST_CONCEPT_ASSERT(( NumericValueConcept<Distance> ));
60 typedef numeric_values<Distance> DistanceNumbers;
61 BOOST_CONCEPT_ASSERT(( AdaptableBinaryFunction<Combinator,Distance,Distance,Distance> ));
63 // If there's ever an infinite distance, then we simply return
64 // infinity. Note that this /will/ include the a non-zero
65 // distance-to-self in the combined values. However, this is usually
66 // zero, so it shouldn't be too problematic.
68 VertexIterator i, end;
69 for(boost::tie(i, end) = vertices(g); i != end; ++i) {
71 if(get(dist, v) != DistanceNumbers::infinity()) {
72 ret = combine(ret, get(dist, v));
75 ret = DistanceNumbers::infinity();
82 // Similar to std::plus<T>, but maximizes parameters
83 // rather than adding them.
85 struct maximize : public std::binary_function<T, T, T>
87 T operator ()(T x, T y) const
88 { BOOST_USING_STD_MAX(); return max BOOST_PREVENT_MACRO_SUBSTITUTION (x, y); }
91 // Another helper, like maximize() to help abstract functional
92 // concepts. This is trivially instantiated for builtin numeric
93 // types, but should be specialized for those types that have
94 // discrete notions of reciprocals.
96 struct reciprocal : public std::unary_function<T, T>
98 typedef std::unary_function<T, T> function_type;
99 typedef typename function_type::result_type result_type;
100 typedef typename function_type::argument_type argument_type;
104 } /* namespace detail */
106 // This type defines the basic facilities used for computing values
107 // based on the geodesic distances between vertices. Examples include
108 // closeness centrality and mean geodesic distance.
109 template <typename Graph, typename DistanceType, typename ResultType>
110 struct geodesic_measure
112 typedef DistanceType distance_type;
113 typedef ResultType result_type;
114 typedef typename graph_traits<Graph>::vertices_size_type size_type;
116 typedef numeric_values<distance_type> distance_values;
117 typedef numeric_values<result_type> result_values;
119 static inline distance_type infinite_distance()
120 { return distance_values::infinity(); }
122 static inline result_type infinite_result()
123 { return result_values::infinity(); }
125 static inline result_type zero_result()
126 { return result_values::zero(); }
129 } /* namespace boost */