]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
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 | { | |
87 | 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; | |
101 | 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 | ||
119 | static inline distance_type infinite_distance() | |
120 | { return distance_values::infinity(); } | |
121 | ||
122 | static inline result_type infinite_result() | |
123 | { return result_values::infinity(); } | |
124 | ||
125 | static inline result_type zero_result() | |
126 | { return result_values::zero(); } | |
127 | }; | |
128 | ||
129 | } /* namespace boost */ | |
130 | ||
131 | #endif |