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