]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |