1 | // (C) Copyright Andrew Sutton 2007 |
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_GEODESIC_DISTANCE_HPP |
8 | #define BOOST_GRAPH_GEODESIC_DISTANCE_HPP |
9 | |
10 | #include <boost/graph/detail/geodesic.hpp> |
11 | #include <boost/graph/exterior_property.hpp> |
12 | #include <boost/concept/assert.hpp> |
13 | |
14 | namespace boost |
15 | { |
16 | template <typename Graph, |
17 | typename DistanceType, |
18 | typename ResultType, |
19 | typename Divides = std::divides<ResultType> > |
20 | struct mean_geodesic_measure |
21 | : public geodesic_measure<Graph, DistanceType, ResultType> |
22 | { |
23 | typedef geodesic_measure<Graph, DistanceType, ResultType> base_type; |
24 | typedef typename base_type::distance_type distance_type; |
25 | typedef typename base_type::result_type result_type; |
26 | |
27 | result_type operator ()(distance_type d, const Graph& g) |
28 | { |
29 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); |
30 | BOOST_CONCEPT_ASSERT(( NumericValueConcept<DistanceType> )); |
31 | BOOST_CONCEPT_ASSERT(( NumericValueConcept<ResultType> )); |
32 | BOOST_CONCEPT_ASSERT(( AdaptableBinaryFunctionConcept<Divides,ResultType,ResultType,ResultType> )); |
33 | |
34 | return (d == base_type::infinite_distance()) |
35 | ? base_type::infinite_result() |
36 | : div(result_type(d), result_type(num_vertices(g) - 1)); |
37 | } |
38 | Divides div; |
39 | }; |
40 | |
41 | template <typename Graph, typename DistanceMap> |
42 | inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double> |
43 | measure_mean_geodesic(const Graph&, DistanceMap) |
44 | { |
45 | return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double>(); |
46 | } |
47 | |
48 | template <typename T, typename Graph, typename DistanceMap> |
49 | inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T> |
50 | measure_mean_geodesic(const Graph&, DistanceMap) |
51 | { |
52 | return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>(); |
53 | } |
54 | |
55 | // This is a little different because it's expected that the result type |
56 | // should (must?) be the same as the distance type. There's a type of |
57 | // transitivity in this thinking... If the average of distances has type |
58 | // X then the average of x's should also be type X. Is there a case where this |
59 | // is not true? |
60 | // |
61 | // This type is a little under-genericized... It needs generic parameters |
62 | // for addition and division. |
63 | template <typename Graph, typename DistanceType> |
64 | struct mean_graph_distance_measure |
65 | : public geodesic_measure<Graph, DistanceType, DistanceType> |
66 | { |
67 | typedef geodesic_measure<Graph, DistanceType, DistanceType> base_type; |
68 | typedef typename base_type::distance_type distance_type; |
69 | typedef typename base_type::result_type result_type; |
70 | |
71 | inline result_type operator ()(distance_type d, const Graph& g) |
72 | { |
73 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); |
74 | BOOST_CONCEPT_ASSERT(( NumericValueConcept<DistanceType> )); |
75 | |
76 | if(d == base_type::infinite_distance()) { |
77 | return base_type::infinite_result(); |
78 | } |
79 | else { |
80 | return d / result_type(num_vertices(g)); |
81 | } |
82 | } |
83 | }; |
84 | |
85 | template <typename Graph, typename DistanceMap> |
86 | inline mean_graph_distance_measure<Graph, typename property_traits<DistanceMap>::value_type> |
87 | measure_graph_mean_geodesic(const Graph&, DistanceMap) |
88 | { |
89 | typedef typename property_traits<DistanceMap>::value_type T; |
90 | return mean_graph_distance_measure<Graph, T>(); |
91 | } |
92 | |
93 | template <typename Graph, |
94 | typename DistanceMap, |
95 | typename Measure, |
96 | typename Combinator> |
97 | inline typename Measure::result_type |
98 | mean_geodesic(const Graph& g, |
99 | DistanceMap dist, |
100 | Measure measure, |
101 | Combinator combine) |
102 | { |
103 | BOOST_CONCEPT_ASSERT(( DistanceMeasureConcept<Measure,Graph> )); |
104 | typedef typename Measure::distance_type Distance; |
105 | |
106 | Distance n = detail::combine_distances(g, dist, combine, Distance(0)); |
107 | return measure(n, g); |
108 | } |
109 | |
110 | template <typename Graph, |
111 | typename DistanceMap, |
112 | typename Measure> |
113 | inline typename Measure::result_type |
114 | mean_geodesic(const Graph& g, DistanceMap dist, Measure measure) |
115 | { |
116 | BOOST_CONCEPT_ASSERT(( DistanceMeasureConcept<Measure,Graph> )); |
117 | typedef typename Measure::distance_type Distance; |
118 | |
119 | return mean_geodesic(g, dist, measure, std::plus<Distance>()); |
120 | } |
121 | |
122 | template <typename Graph, typename DistanceMap> |
123 | inline double |
124 | mean_geodesic(const Graph& g, DistanceMap dist) |
125 | { return mean_geodesic(g, dist, measure_mean_geodesic(g, dist)); } |
126 | |
127 | template <typename T, typename Graph, typename DistanceMap> |
128 | inline T |
129 | mean_geodesic(const Graph& g, DistanceMap dist) |
130 | { return mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist)); } |
131 | |
132 | |
133 | template <typename Graph, |
134 | typename DistanceMatrixMap, |
135 | typename GeodesicMap, |
136 | typename Measure> |
137 | inline typename property_traits<GeodesicMap>::value_type |
138 | all_mean_geodesics(const Graph& g, |
139 | DistanceMatrixMap dist, |
140 | GeodesicMap geo, |
141 | Measure measure) |
142 | { |
143 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); |
144 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
145 | typedef typename graph_traits<Graph>::vertex_iterator VertexIterator; |
146 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> )); |
147 | typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap; |
148 | BOOST_CONCEPT_ASSERT(( DistanceMeasureConcept<Measure,Graph> )); |
149 | typedef typename Measure::result_type Result; |
150 | BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<GeodesicMap,Vertex> )); |
151 | BOOST_CONCEPT_ASSERT(( NumericValueConcept<Result> )); |
152 | |
153 | // NOTE: We could compute the mean geodesic here by performing additional |
154 | // computations (i.e., adding and dividing). However, I don't really feel |
155 | // like fully genericizing the entire operation yet so I'm not going to. |
156 | |
157 | Result inf = numeric_values<Result>::infinity(); |
158 | Result sum = numeric_values<Result>::zero(); |
159 | VertexIterator i, end; |
160 | for(boost::tie(i, end) = vertices(g); i != end; ++i) { |
161 | DistanceMap dm = get(dist, *i); |
162 | Result r = mean_geodesic(g, dm, measure); |
163 | put(geo, *i, r); |
164 | |
165 | // compute the sum along with geodesics |
166 | if(r == inf) { |
167 | sum = inf; |
168 | } |
169 | else if(sum != inf) { |
170 | sum += r; |
171 | } |
172 | } |
173 | |
174 | // return the average of averages. |
175 | return sum / Result(num_vertices(g)); |
176 | } |
177 | |
178 | template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap> |
179 | inline typename property_traits<GeodesicMap>::value_type |
180 | all_mean_geodesics(const Graph& g, DistanceMatrixMap dist, GeodesicMap geo) |
181 | { |
182 | BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> )); |
183 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
184 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> )); |
185 | typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap; |
186 | BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<GeodesicMap,Vertex> )); |
187 | typedef typename property_traits<GeodesicMap>::value_type Result; |
188 | |
189 | return all_mean_geodesics(g, dist, geo, measure_mean_geodesic<Result>(g, DistanceMap())); |
190 | } |
191 | |
192 | |
193 | template <typename Graph, typename GeodesicMap, typename Measure> |
194 | inline typename Measure::result_type |
195 | small_world_distance(const Graph& g, GeodesicMap geo, Measure measure) |
196 | { |
197 | BOOST_CONCEPT_ASSERT(( DistanceMeasureConcept<Measure,Graph> )); |
198 | typedef typename Measure::result_type Result; |
199 | |
200 | Result sum = detail::combine_distances(g, geo, std::plus<Result>(), Result(0)); |
201 | return measure(sum, g); |
202 | } |
203 | |
204 | template <typename Graph, typename GeodesicMap> |
205 | inline typename property_traits<GeodesicMap>::value_type |
206 | small_world_distance(const Graph& g, GeodesicMap geo) |
207 | { return small_world_distance(g, geo, measure_graph_mean_geodesic(g, geo)); } |
208 | |
209 | } |
210 | |
211 | #endif |
212 | |