// (C) Copyright Andrew Sutton 2007 | |
// | |
// Use, modification and distribution are subject to the | |
// Boost Software License, Version 1.0 (See accompanying file | |
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) | |
#ifndef BOOST_GRAPH_GEODESIC_DISTANCE_HPP | |
#define BOOST_GRAPH_GEODESIC_DISTANCE_HPP | |
#include <boost/graph/detail/geodesic.hpp> | |
#include <boost/graph/exterior_property.hpp> | |
namespace boost | |
{ | |
template <typename Graph, | |
typename DistanceType, | |
typename ResultType, | |
typename Divides = std::divides<ResultType> > | |
struct mean_geodesic_measure | |
: public geodesic_measure<Graph, DistanceType, ResultType> | |
{ | |
typedef geodesic_measure<Graph, DistanceType, ResultType> base_type; | |
typedef typename base_type::distance_type distance_type; | |
typedef typename base_type::result_type result_type; | |
result_type operator ()(distance_type d, const Graph& g) | |
{ | |
function_requires< VertexListGraphConcept<Graph> >(); | |
function_requires< NumericValueConcept<DistanceType> >(); | |
function_requires< NumericValueConcept<ResultType> >(); | |
function_requires< AdaptableBinaryFunctionConcept<Divides,ResultType,ResultType,ResultType> >(); | |
return (d == base_type::infinite_distance()) | |
? base_type::infinite_result() | |
: div(result_type(d), result_type(num_vertices(g) - 1)); | |
} | |
Divides div; | |
}; | |
template <typename Graph, typename DistanceMap> | |
inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double> | |
measure_mean_geodesic(const Graph&, DistanceMap) | |
{ | |
return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, double>(); | |
} | |
template <typename T, typename Graph, typename DistanceMap> | |
inline mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T> | |
measure_mean_geodesic(const Graph&, DistanceMap) | |
{ | |
return mean_geodesic_measure<Graph, typename property_traits<DistanceMap>::value_type, T>(); | |
} | |
// This is a little different because it's expected that the result type | |
// should (must?) be the same as the distance type. There's a type of | |
// transitivity in this thinking... If the average of distances has type | |
// X then the average of x's should also be type X. Is there a case where this | |
// is not true? | |
// | |
// This type is a little under-genericized... It needs generic parameters | |
// for addition and division. | |
template <typename Graph, typename DistanceType> | |
struct mean_graph_distance_measure | |
: public geodesic_measure<Graph, DistanceType, DistanceType> | |
{ | |
typedef geodesic_measure<Graph, DistanceType, DistanceType> base_type; | |
typedef typename base_type::distance_type distance_type; | |
typedef typename base_type::result_type result_type; | |
inline result_type operator ()(distance_type d, const Graph& g) | |
{ | |
function_requires< VertexListGraphConcept<Graph> >(); | |
function_requires< NumericValueConcept<DistanceType> >(); | |
if(d == base_type::infinite_distance()) { | |
return base_type::infinite_result(); | |
} | |
else { | |
return d / result_type(num_vertices(g)); | |
} | |
} | |
}; | |
template <typename Graph, typename DistanceMap> | |
inline mean_graph_distance_measure<Graph, typename property_traits<DistanceMap>::value_type> | |
measure_graph_mean_geodesic(const Graph&, DistanceMap) | |
{ | |
typedef typename property_traits<DistanceMap>::value_type T; | |
return mean_graph_distance_measure<Graph, T>(); | |
} | |
template <typename Graph, | |
typename DistanceMap, | |
typename Measure, | |
typename Combinator> | |
inline typename Measure::result_type | |
mean_geodesic(const Graph& g, | |
DistanceMap dist, | |
Measure measure, | |
Combinator combine) | |
{ | |
function_requires< DistanceMeasureConcept<Measure,Graph> >(); | |
typedef typename Measure::distance_type Distance; | |
Distance n = detail::combine_distances(g, dist, combine, Distance(0)); | |
return measure(n, g); | |
} | |
template <typename Graph, | |
typename DistanceMap, | |
typename Measure> | |
inline typename Measure::result_type | |
mean_geodesic(const Graph& g, DistanceMap dist, Measure measure) | |
{ | |
function_requires< DistanceMeasureConcept<Measure,Graph> >(); | |
typedef typename Measure::distance_type Distance; | |
return mean_geodesic(g, dist, measure, std::plus<Distance>()); | |
} | |
template <typename Graph, typename DistanceMap> | |
inline double | |
mean_geodesic(const Graph& g, DistanceMap dist) | |
{ return mean_geodesic(g, dist, measure_mean_geodesic(g, dist)); } | |
template <typename T, typename Graph, typename DistanceMap> | |
inline T | |
mean_geodesic(const Graph& g, DistanceMap dist) | |
{ return mean_geodesic(g, dist, measure_mean_geodesic<T>(g, dist)); } | |
template <typename Graph, | |
typename DistanceMatrixMap, | |
typename GeodesicMap, | |
typename Measure> | |
inline typename property_traits<GeodesicMap>::value_type | |
all_mean_geodesics(const Graph& g, | |
DistanceMatrixMap dist, | |
GeodesicMap geo, | |
Measure measure) | |
{ | |
function_requires< VertexListGraphConcept<Graph> >(); | |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
typedef typename graph_traits<Graph>::vertex_iterator VertexIterator; | |
function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >(); | |
typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap; | |
function_requires< DistanceMeasureConcept<Measure,Graph> >(); | |
typedef typename Measure::result_type Result; | |
function_requires< WritablePropertyMapConcept<GeodesicMap,Vertex> >(); | |
function_requires< NumericValueConcept<Result> >(); | |
// NOTE: We could compute the mean geodesic here by performing additional | |
// computations (i.e., adding and dividing). However, I don't really feel | |
// like fully genericizing the entire operation yet so I'm not going to. | |
Result inf = numeric_values<Result>::infinity(); | |
Result sum = numeric_values<Result>::zero(); | |
VertexIterator i, end; | |
for(tie(i, end) = vertices(g); i != end; ++i) { | |
DistanceMap dm = get(dist, *i); | |
Result r = mean_geodesic(g, dm, measure); | |
put(geo, *i, r); | |
// compute the sum along with geodesics | |
if(r == inf) { | |
sum = inf; | |
} | |
else if(sum != inf) { | |
sum += r; | |
} | |
} | |
// return the average of averages. | |
return sum / Result(num_vertices(g)); | |
} | |
template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap> | |
inline typename property_traits<GeodesicMap>::value_type | |
all_mean_geodesics(const Graph& g, DistanceMatrixMap dist, GeodesicMap geo) | |
{ | |
function_requires< GraphConcept<Graph> >(); | |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
function_requires< ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> >(); | |
typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap; | |
function_requires< WritablePropertyMapConcept<GeodesicMap,Vertex> >(); | |
typedef typename property_traits<GeodesicMap>::value_type Result; | |
return all_mean_geodesics(g, dist, geo, measure_mean_geodesic<Result>(g, DistanceMap())); | |
} | |
template <typename Graph, typename GeodesicMap, typename Measure> | |
inline typename Measure::result_type | |
small_world_distance(const Graph& g, GeodesicMap geo, Measure measure) | |
{ | |
function_requires< DistanceMeasureConcept<Measure,Graph> >(); | |
typedef typename Measure::result_type Result; | |
Result sum = detail::combine_distances(g, geo, std::plus<Result>(), Result(0)); | |
return measure(sum, g); | |
} | |
template <typename Graph, typename GeodesicMap> | |
inline typename property_traits<GeodesicMap>::value_type | |
small_world_distance(const Graph& g, GeodesicMap geo) | |
{ return small_world_distance(g, geo, measure_graph_mean_geodesic(g, geo)); } | |
} | |
#endif |