Chris@16: // (C) Copyright 2007-2009 Andrew Sutton
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_CLOSENESS_CENTRALITY_HPP
Chris@16: #define BOOST_GRAPH_CLOSENESS_CENTRALITY_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 Reciprocal = detail::reciprocal<ResultType> >
Chris@16: struct closeness_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&)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT(( NumericValueConcept<DistanceType> ));
Chris@16:         BOOST_CONCEPT_ASSERT(( NumericValueConcept<ResultType> ));
Chris@16:         BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Reciprocal,ResultType,ResultType> ));
Chris@16:         return (d == base_type::infinite_distance())
Chris@16:             ? base_type::zero_result()
Chris@16:             : rec(result_type(d));
Chris@16:     }
Chris@16:     Reciprocal rec;
Chris@16: };
Chris@16: 
Chris@16: template <typename Graph, typename DistanceMap>
Chris@16: inline closeness_measure<
Chris@16:         Graph, typename property_traits<DistanceMap>::value_type, double,
Chris@16:         detail::reciprocal<double> >
Chris@16: measure_closeness(const Graph&, DistanceMap)
Chris@16: {
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16:     return closeness_measure<Graph, Distance, double, detail::reciprocal<double> >();
Chris@16: }
Chris@16: 
Chris@16: template <typename T, typename Graph, typename DistanceMap>
Chris@16: inline closeness_measure<
Chris@16:         Graph, typename property_traits<DistanceMap>::value_type, T,
Chris@16:         detail::reciprocal<T> >
Chris@16: measure_closeness(const Graph&, DistanceMap)
Chris@16: {
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16:     return closeness_measure<Graph, Distance, T, detail::reciprocal<T> >();
Chris@16: }
Chris@16: 
Chris@16: template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
Chris@16: inline closeness_measure<
Chris@16:         Graph, typename property_traits<DistanceMap>::value_type, T,
Chris@16:         Reciprocal>
Chris@16: measure_closeness(const Graph&, DistanceMap)
Chris@16: {
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16:     return closeness_measure<Graph, Distance, T, Reciprocal>();
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: closeness_centrality(const Graph& g,
Chris@16:                      DistanceMap dist,
Chris@16:                      Measure measure,
Chris@16:                      Combinator combine)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16:     BOOST_CONCEPT_ASSERT(( NumericValueConcept<Distance> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( DistanceMeasureConcept<Measure,Graph> ));
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, typename DistanceMap, typename Measure>
Chris@16: inline typename Measure::result_type
Chris@16: closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
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<DistanceMap,Vertex> ));
Chris@16:     typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16: 
Chris@16:     return closeness_centrality(g, dist, measure, std::plus<Distance>());
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename DistanceMap>
Chris@16: inline double closeness_centrality(const Graph& g, DistanceMap dist)
Chris@16: { return closeness_centrality(g, dist, measure_closeness(g, dist)); }
Chris@16: 
Chris@16: template <typename T, typename Graph, typename DistanceMap>
Chris@16: inline T closeness_centrality(const Graph& g, DistanceMap dist)
Chris@16: { return closeness_centrality(g, dist, measure_closeness<T>(g, dist)); }
Chris@16: 
Chris@16: template <typename Graph,
Chris@16:           typename DistanceMatrixMap,
Chris@16:           typename CentralityMap,
Chris@16:           typename Measure>
Chris@16: inline void
Chris@16: all_closeness_centralities(const Graph& g,
Chris@16:                            DistanceMatrixMap dist,
Chris@16:                            CentralityMap cent,
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:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> ));
Chris@16:     typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<CentralityMap,Vertex> ));
Chris@16:     typedef typename property_traits<CentralityMap>::value_type Centrality;
Chris@16: 
Chris@16:     typename graph_traits<Graph>::vertex_iterator i, end;
Chris@16:     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
Chris@16:         DistanceMap dm = get(dist, *i);
Chris@16:         Centrality c = closeness_centrality(g, dm, measure);
Chris@16:         put(cent, *i, c);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph,
Chris@16:           typename DistanceMatrixMap,
Chris@16:           typename CentralityMap>
Chris@16: inline void
Chris@16: all_closeness_centralities(const Graph& g,
Chris@16:                             DistanceMatrixMap dist,
Chris@16:                             CentralityMap cent)
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(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
Chris@16:     typedef typename property_traits<CentralityMap>::value_type Result;
Chris@16: 
Chris@16:     all_closeness_centralities(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
Chris@16: }
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif