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