1 // (C) Copyright 2007-2009 Andrew Sutton
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0 (See accompanying file
5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
7 #ifndef BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
8 #define BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
10 #include <boost/graph/detail/geodesic.hpp>
11 #include <boost/graph/exterior_property.hpp>
12 #include <boost/concept/assert.hpp>
16 template <typename Graph,
17 typename DistanceType,
19 typename Reciprocal = detail::reciprocal<ResultType> >
20 struct closeness_measure
21 : public geodesic_measure<Graph, DistanceType, ResultType>
23 typedef geodesic_measure< Graph, DistanceType, ResultType> base_type;
24 typedef typename base_type::distance_type distance_type;
25 typedef typename base_type::result_type result_type;
27 result_type operator ()(distance_type d, const Graph&)
29 BOOST_CONCEPT_ASSERT(( NumericValueConcept<DistanceType> ));
30 BOOST_CONCEPT_ASSERT(( NumericValueConcept<ResultType> ));
31 BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Reciprocal,ResultType,ResultType> ));
32 return (d == base_type::infinite_distance())
33 ? base_type::zero_result()
34 : rec(result_type(d));
39 template <typename Graph, typename DistanceMap>
40 inline closeness_measure<
41 Graph, typename property_traits<DistanceMap>::value_type, double,
42 detail::reciprocal<double> >
43 measure_closeness(const Graph&, DistanceMap)
45 typedef typename property_traits<DistanceMap>::value_type Distance;
46 return closeness_measure<Graph, Distance, double, detail::reciprocal<double> >();
49 template <typename T, typename Graph, typename DistanceMap>
50 inline closeness_measure<
51 Graph, typename property_traits<DistanceMap>::value_type, T,
52 detail::reciprocal<T> >
53 measure_closeness(const Graph&, DistanceMap)
55 typedef typename property_traits<DistanceMap>::value_type Distance;
56 return closeness_measure<Graph, Distance, T, detail::reciprocal<T> >();
59 template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
60 inline closeness_measure<
61 Graph, typename property_traits<DistanceMap>::value_type, T,
63 measure_closeness(const Graph&, DistanceMap)
65 typedef typename property_traits<DistanceMap>::value_type Distance;
66 return closeness_measure<Graph, Distance, T, Reciprocal>();
69 template <typename Graph,
73 inline typename Measure::result_type
74 closeness_centrality(const Graph& g,
79 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
80 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
81 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
82 typedef typename property_traits<DistanceMap>::value_type Distance;
83 BOOST_CONCEPT_ASSERT(( NumericValueConcept<Distance> ));
84 BOOST_CONCEPT_ASSERT(( DistanceMeasureConcept<Measure,Graph> ));
86 Distance n = detail::combine_distances(g, dist, combine, Distance(0));
90 template <typename Graph, typename DistanceMap, typename Measure>
91 inline typename Measure::result_type
92 closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
94 BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
95 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
96 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
97 typedef typename property_traits<DistanceMap>::value_type Distance;
99 return closeness_centrality(g, dist, measure, std::plus<Distance>());
102 template <typename Graph, typename DistanceMap>
103 inline double closeness_centrality(const Graph& g, DistanceMap dist)
104 { return closeness_centrality(g, dist, measure_closeness(g, dist)); }
106 template <typename T, typename Graph, typename DistanceMap>
107 inline T closeness_centrality(const Graph& g, DistanceMap dist)
108 { return closeness_centrality(g, dist, measure_closeness<T>(g, dist)); }
110 template <typename Graph,
111 typename DistanceMatrixMap,
112 typename CentralityMap,
115 all_closeness_centralities(const Graph& g,
116 DistanceMatrixMap dist,
120 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
121 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
122 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> ));
123 typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
124 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
125 BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<CentralityMap,Vertex> ));
126 typedef typename property_traits<CentralityMap>::value_type Centrality;
128 typename graph_traits<Graph>::vertex_iterator i, end;
129 for(boost::tie(i, end) = vertices(g); i != end; ++i) {
130 DistanceMap dm = get(dist, *i);
131 Centrality c = closeness_centrality(g, dm, measure);
136 template <typename Graph,
137 typename DistanceMatrixMap,
138 typename CentralityMap>
140 all_closeness_centralities(const Graph& g,
141 DistanceMatrixMap dist,
144 BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
145 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
146 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> ));
147 typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
148 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
149 typedef typename property_traits<CentralityMap>::value_type Result;
151 all_closeness_centralities(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
154 } /* namespace boost */