boost/graph/closeness_centrality.hpp

0001 // (C) Copyright 2007-2009 Andrew Sutton
0002 //
0003 // Use, modification and distribution are subject to the
0004 // Boost Software License, Version 1.0 (See accompanying file
0005 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
0008 #define BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
0009
0010 #include <boost/graph/detail/geodesic.hpp>
0011 #include <boost/graph/exterior_property.hpp>
0012 #include <boost/concept/assert.hpp>
0013
0014 namespace boost
0015 {
0016 template < typename Graph, typename DistanceType, typename ResultType,
0017     typename Reciprocal = detail::reciprocal< ResultType > >
0018 struct closeness_measure
0019 : public geodesic_measure< Graph, DistanceType, ResultType >
0020 {
0021     typedef geodesic_measure< Graph, DistanceType, ResultType > base_type;
0022     typedef typename base_type::distance_type distance_type;
0023     typedef typename base_type::result_type result_type;
0024
0025     result_type operator()(distance_type d, const Graph&)
0026     {
0027         BOOST_CONCEPT_ASSERT((NumericValueConcept< DistanceType >));
0028         BOOST_CONCEPT_ASSERT((NumericValueConcept< ResultType >));
0029         BOOST_CONCEPT_ASSERT((AdaptableUnaryFunctionConcept< Reciprocal,
0030             ResultType, ResultType >));
0031         return (d == base_type::infinite_distance()) ? base_type::zero_result()
0032                                                      : rec(result_type(d));
0033     }
0034     Reciprocal rec;
0035 };
0036
0037 template < typename Graph, typename DistanceMap >
0038 inline closeness_measure< Graph,
0039     typename property_traits< DistanceMap >::value_type, double,
0040     detail::reciprocal< double > >
0041 measure_closeness(const Graph&, DistanceMap)
0042 {
0043     typedef typename property_traits< DistanceMap >::value_type Distance;
0044     return closeness_measure< Graph, Distance, double,
0045         detail::reciprocal< double > >();
0046 }
0047
0048 template < typename T, typename Graph, typename DistanceMap >
0049 inline closeness_measure< Graph,
0050     typename property_traits< DistanceMap >::value_type, T,
0051     detail::reciprocal< T > >
0052 measure_closeness(const Graph&, DistanceMap)
0053 {
0054     typedef typename property_traits< DistanceMap >::value_type Distance;
0055     return closeness_measure< Graph, Distance, T, detail::reciprocal< T > >();
0056 }
0057
0058 template < typename T, typename Graph, typename DistanceMap,
0059     typename Reciprocal >
0060 inline closeness_measure< Graph,
0061     typename property_traits< DistanceMap >::value_type, T, Reciprocal >
0062 measure_closeness(const Graph&, DistanceMap)
0063 {
0064     typedef typename property_traits< DistanceMap >::value_type Distance;
0065     return closeness_measure< Graph, Distance, T, Reciprocal >();
0066 }
0067
0068 template < typename Graph, typename DistanceMap, typename Measure,
0069     typename Combinator >
0070 inline typename Measure::result_type closeness_centrality(
0071     const Graph& g, DistanceMap dist, Measure measure, Combinator combine)
0072 {
0073     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0074     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0075     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
0076     typedef typename property_traits< DistanceMap >::value_type Distance;
0077     BOOST_CONCEPT_ASSERT((NumericValueConcept< Distance >));
0078     BOOST_CONCEPT_ASSERT((DistanceMeasureConcept< Measure, Graph >));
0079
0080     Distance n = detail::combine_distances(g, dist, combine, Distance(0));
0081     return measure(n, g);
0082 }
0083
0084 template < typename Graph, typename DistanceMap, typename Measure >
0085 inline typename Measure::result_type closeness_centrality(
0086     const Graph& g, DistanceMap dist, Measure measure)
0087 {
0088     BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
0089     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0090     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
0091     typedef typename property_traits< DistanceMap >::value_type Distance;
0092
0093     return closeness_centrality(g, dist, measure, std::plus< Distance >());
0094 }
0095
0096 template < typename Graph, typename DistanceMap >
0097 inline double closeness_centrality(const Graph& g, DistanceMap dist)
0098 {
0099     return closeness_centrality(g, dist, measure_closeness(g, dist));
0100 }
0101
0102 template < typename T, typename Graph, typename DistanceMap >
0103 inline T closeness_centrality(const Graph& g, DistanceMap dist)
0104 {
0105     return closeness_centrality(g, dist, measure_closeness< T >(g, dist));
0106 }
0107
0108 template < typename Graph, typename DistanceMatrixMap, typename CentralityMap,
0109     typename Measure >
0110 inline void all_closeness_centralities(
0111     const Graph& g, DistanceMatrixMap dist, CentralityMap cent, Measure measure)
0112 {
0113     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0114     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0115     BOOST_CONCEPT_ASSERT(
0116         (ReadablePropertyMapConcept< DistanceMatrixMap, Vertex >));
0117     typedef
0118         typename property_traits< DistanceMatrixMap >::value_type DistanceMap;
0119     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
0120     BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept< CentralityMap, Vertex >));
0121     typedef typename property_traits< CentralityMap >::value_type Centrality;
0122
0123     typename graph_traits< Graph >::vertex_iterator i, end;
0124     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0125     {
0126         DistanceMap dm = get(dist, *i);
0127         Centrality c = closeness_centrality(g, dm, measure);
0128         put(cent, *i, c);
0129     }
0130 }
0131
0132 template < typename Graph, typename DistanceMatrixMap, typename CentralityMap >
0133 inline void all_closeness_centralities(
0134     const Graph& g, DistanceMatrixMap dist, CentralityMap cent)
0135 {
0136     BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
0137     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0138     BOOST_CONCEPT_ASSERT(
0139         (ReadablePropertyMapConcept< DistanceMatrixMap, Vertex >));
0140     typedef
0141         typename property_traits< DistanceMatrixMap >::value_type DistanceMap;
0142     BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
0143     typedef typename property_traits< CentralityMap >::value_type Result;
0144
0145     all_closeness_centralities(
0146         g, dist, cent, measure_closeness< Result >(g, DistanceMap()));
0147 }
0148
0149 } /* namespace boost */
0150
0151 #endif