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
14namespace boost
15{
16template <typename Graph,
17 typename DistanceType,
18 typename ResultType,
19 typename Divides = std::divides<ResultType> >
20struct 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
41template <typename Graph, typename DistanceMap>
42inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double>
43measure_mean_geodesic(const Graph&, DistanceMap)
44{
45 return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double>();
46}
47
48template <typename T, typename Graph, typename DistanceMap>
49inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>
50measure_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.
63template <typename Graph, typename DistanceType>
64struct 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
85template <typename Graph, typename DistanceMap>
86inline mean_graph_distance_measure<Graph, typename property_traits<DistanceMap>::value_type>
87measure_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
93template <typename Graph,
94 typename DistanceMap,
95 typename Measure,
96 typename Combinator>
97inline typename Measure::result_type
98mean_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
110template <typename Graph,
111 typename DistanceMap,
112 typename Measure>
113inline typename Measure::result_type
114mean_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
122template <typename Graph, typename DistanceMap>
123inline double
124mean_geodesic(const Graph& g, DistanceMap dist)
125{ return mean_geodesic(g, dist, measure_mean_geodesic(g, dist)); }
126
127template <typename T, typename Graph, typename DistanceMap>
128inline T
129mean_geodesic(const Graph& g, DistanceMap dist)
130{ return mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist)); }
131
132
133template <typename Graph,
134 typename DistanceMatrixMap,
135 typename GeodesicMap,
136 typename Measure>
137inline typename property_traits<GeodesicMap>::value_type
138all_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
178template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap>
179inline typename property_traits<GeodesicMap>::value_type
180all_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
193template <typename Graph, typename GeodesicMap, typename Measure>
194inline typename Measure::result_type
195small_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
204template <typename Graph, typename GeodesicMap>
205inline typename property_traits<GeodesicMap>::value_type
206small_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

source code of boost/boost/graph/geodesic_distance.hpp