]>
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}, | |
92f5a8d4 | 36 | // url = {https://doi.org/10.1016/j.socnet.2005.11.005}, |
7c673cae FG |
37 | // volume = {28}, |
38 | // year = {2006} | |
39 | // } | |
40 | // } | |
41 | ||
f67539c2 TL |
42 | namespace detail |
43 | { | |
7c673cae FG |
44 | // Note that this assumes T == property_traits<DistanceMap>::value_type |
45 | // and that the args and return of combine are also T. | |
f67539c2 TL |
46 | template < typename Graph, typename DistanceMap, typename Combinator, |
47 | typename Distance > | |
48 | inline Distance combine_distances( | |
49 | const Graph& g, DistanceMap dist, Combinator combine, Distance init) | |
7c673cae | 50 | { |
f67539c2 TL |
51 | BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >)); |
52 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; | |
53 | typedef typename graph_traits< Graph >::vertex_iterator VertexIterator; | |
54 | BOOST_CONCEPT_ASSERT( | |
55 | (ReadablePropertyMapConcept< DistanceMap, Vertex >)); | |
56 | BOOST_CONCEPT_ASSERT((NumericValueConcept< Distance >)); | |
57 | typedef numeric_values< Distance > DistanceNumbers; | |
58 | BOOST_CONCEPT_ASSERT((AdaptableBinaryFunction< Combinator, Distance, | |
59 | Distance, Distance >)); | |
7c673cae FG |
60 | |
61 | // If there's ever an infinite distance, then we simply return | |
62 | // infinity. Note that this /will/ include the a non-zero | |
63 | // distance-to-self in the combined values. However, this is usually | |
64 | // zero, so it shouldn't be too problematic. | |
65 | Distance ret = init; | |
66 | VertexIterator i, end; | |
f67539c2 TL |
67 | for (boost::tie(i, end) = vertices(g); i != end; ++i) |
68 | { | |
7c673cae | 69 | Vertex v = *i; |
f67539c2 TL |
70 | if (get(dist, v) != DistanceNumbers::infinity()) |
71 | { | |
7c673cae FG |
72 | ret = combine(ret, get(dist, v)); |
73 | } | |
f67539c2 TL |
74 | else |
75 | { | |
7c673cae FG |
76 | ret = DistanceNumbers::infinity(); |
77 | break; | |
78 | } | |
79 | } | |
80 | return ret; | |
81 | } | |
82 | ||
83 | // Similar to std::plus<T>, but maximizes parameters | |
84 | // rather than adding them. | |
f67539c2 | 85 | template < typename T > struct maximize |
7c673cae | 86 | { |
92f5a8d4 TL |
87 | typedef T result_type; |
88 | typedef T first_argument_type; | |
89 | typedef T second_argument_type; | |
f67539c2 TL |
90 | T operator()(T x, T y) const |
91 | { | |
92 | BOOST_USING_STD_MAX(); | |
93 | return max BOOST_PREVENT_MACRO_SUBSTITUTION(x, y); | |
94 | } | |
7c673cae FG |
95 | }; |
96 | ||
97 | // Another helper, like maximize() to help abstract functional | |
98 | // concepts. This is trivially instantiated for builtin numeric | |
99 | // types, but should be specialized for those types that have | |
100 | // discrete notions of reciprocals. | |
f67539c2 | 101 | template < typename T > struct reciprocal |
7c673cae | 102 | { |
92f5a8d4 TL |
103 | typedef T result_type; |
104 | typedef T argument_type; | |
f67539c2 | 105 | T operator()(T t) { return T(1) / t; } |
7c673cae FG |
106 | }; |
107 | } /* namespace detail */ | |
108 | ||
109 | // This type defines the basic facilities used for computing values | |
110 | // based on the geodesic distances between vertices. Examples include | |
111 | // closeness centrality and mean geodesic distance. | |
f67539c2 | 112 | template < typename Graph, typename DistanceType, typename ResultType > |
7c673cae FG |
113 | struct geodesic_measure |
114 | { | |
115 | typedef DistanceType distance_type; | |
116 | typedef ResultType result_type; | |
f67539c2 | 117 | typedef typename graph_traits< Graph >::vertices_size_type size_type; |
7c673cae | 118 | |
f67539c2 TL |
119 | typedef numeric_values< distance_type > distance_values; |
120 | typedef numeric_values< result_type > result_values; | |
7c673cae FG |
121 | |
122 | static inline distance_type infinite_distance() | |
f67539c2 TL |
123 | { |
124 | return distance_values::infinity(); | |
125 | } | |
7c673cae FG |
126 | |
127 | static inline result_type infinite_result() | |
f67539c2 TL |
128 | { |
129 | return result_values::infinity(); | |
130 | } | |
7c673cae | 131 | |
f67539c2 | 132 | static inline result_type zero_result() { return result_values::zero(); } |
7c673cae FG |
133 | }; |
134 | ||
135 | } /* namespace boost */ | |
136 | ||
137 | #endif |