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