1 // (C) Copyright 2007 Andrew Sutton
2 //
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)
6 
7 #ifndef BOOST_GRAPH_DETAIL_GEODESIC_HPP
8 #define BOOST_GRAPH_DETAIL_GEODESIC_HPP
9 
10 #include <functional>
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>
15 
16 // TODO: Should this really be in detail?
17 
18 namespace boost
19 {
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.
25 //
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},
31 //         month = {October},
32 //         number = {4},
33 //         pages = {466--484},
34 //         priority = {0},
35 //         title = {A Graph-theoretic perspective on centrality},
36 //         url = {http://dx.doi.org/10.1016/j.socnet.2005.11.005},
37 //             volume = {28},
38 //             year = {2006}
39 //         }
40 //     }
41 
42 namespace detail {
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,
46                 typename DistanceMap,
47                 typename Combinator,
48                 typename Distance>
49     inline Distance
combine_distances(const Graph & g,DistanceMap dist,Combinator combine,Distance init)50     combine_distances(const Graph& g,
51                         DistanceMap dist,
52                         Combinator combine,
53                         Distance init)
54     {
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> ));
62 
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.
67         Distance ret = init;
68         VertexIterator i, end;
69         for(boost::tie(i, end) = vertices(g); i != end; ++i) {
70             Vertex v = *i;
71             if(get(dist, v) != DistanceNumbers::infinity()) {
72                 ret = combine(ret, get(dist, v));
73             }
74             else {
75                 ret = DistanceNumbers::infinity();
76                 break;
77             }
78         }
79         return ret;
80     }
81 
82     // Similar to std::plus<T>, but maximizes parameters
83     // rather than adding them.
84     template <typename T>
85     struct maximize : public std::binary_function<T, T, T>
86     {
operator ()boost::detail::maximize87         T operator ()(T x, T y) const
88         { BOOST_USING_STD_MAX(); return max BOOST_PREVENT_MACRO_SUBSTITUTION (x, y); }
89     };
90 
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.
95     template <typename T>
96     struct reciprocal : public std::unary_function<T, T>
97     {
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;
operator ()boost::detail::reciprocal101         T operator ()(T t)
102         { return T(1) / t; }
103     };
104 } /* namespace detail */
105 
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
111 {
112     typedef DistanceType distance_type;
113     typedef ResultType result_type;
114     typedef typename graph_traits<Graph>::vertices_size_type size_type;
115 
116     typedef numeric_values<distance_type> distance_values;
117     typedef numeric_values<result_type> result_values;
118 
infinite_distanceboost::geodesic_measure119     static inline distance_type infinite_distance()
120     { return distance_values::infinity(); }
121 
infinite_resultboost::geodesic_measure122     static inline result_type infinite_result()
123     { return result_values::infinity(); }
124 
zero_resultboost::geodesic_measure125     static inline result_type zero_result()
126     { return result_values::zero(); }
127 };
128 
129 } /* namespace boost */
130 
131 #endif
132