1// (C) Copyright 2007-2009 Andrew Sutton
2//
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)
6
7#ifndef BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
8#define BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
9
10#include <boost/graph/detail/geodesic.hpp>
11#include <boost/graph/exterior_property.hpp>
12#include <boost/concept/assert.hpp>
13
14namespace boost
15{
16template <typename Graph,
17 typename DistanceType,
18 typename ResultType,
19 typename Reciprocal = detail::reciprocal<ResultType> >
20struct closeness_measure
21 : public geodesic_measure<Graph, DistanceType, ResultType>
22{
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;
26
27 result_type operator ()(distance_type d, const Graph&)
28 {
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));
35 }
36 Reciprocal rec;
37};
38
39template <typename Graph, typename DistanceMap>
40inline closeness_measure<
41 Graph, typename property_traits<DistanceMap>::value_type, double,
42 detail::reciprocal<double> >
43measure_closeness(const Graph&, DistanceMap)
44{
45 typedef typename property_traits<DistanceMap>::value_type Distance;
46 return closeness_measure<Graph, Distance, double, detail::reciprocal<double> >();
47}
48
49template <typename T, typename Graph, typename DistanceMap>
50inline closeness_measure<
51 Graph, typename property_traits<DistanceMap>::value_type, T,
52 detail::reciprocal<T> >
53measure_closeness(const Graph&, DistanceMap)
54{
55 typedef typename property_traits<DistanceMap>::value_type Distance;
56 return closeness_measure<Graph, Distance, T, detail::reciprocal<T> >();
57}
58
59template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
60inline closeness_measure<
61 Graph, typename property_traits<DistanceMap>::value_type, T,
62 Reciprocal>
63measure_closeness(const Graph&, DistanceMap)
64{
65 typedef typename property_traits<DistanceMap>::value_type Distance;
66 return closeness_measure<Graph, Distance, T, Reciprocal>();
67}
68
69template <typename Graph,
70 typename DistanceMap,
71 typename Measure,
72 typename Combinator>
73inline typename Measure::result_type
74closeness_centrality(const Graph& g,
75 DistanceMap dist,
76 Measure measure,
77 Combinator combine)
78{
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> ));
85
86 Distance n = detail::combine_distances(g, dist, combine, Distance(0));
87 return measure(n, g);
88}
89
90template <typename Graph, typename DistanceMap, typename Measure>
91inline typename Measure::result_type
92closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
93{
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;
98
99 return closeness_centrality(g, dist, measure, std::plus<Distance>());
100}
101
102template <typename Graph, typename DistanceMap>
103inline double closeness_centrality(const Graph& g, DistanceMap dist)
104{ return closeness_centrality(g, dist, measure_closeness(g, dist)); }
105
106template <typename T, typename Graph, typename DistanceMap>
107inline T closeness_centrality(const Graph& g, DistanceMap dist)
108{ return closeness_centrality(g, dist, measure_closeness<T>(g, dist)); }
109
110template <typename Graph,
111 typename DistanceMatrixMap,
112 typename CentralityMap,
113 typename Measure>
114inline void
115all_closeness_centralities(const Graph& g,
116 DistanceMatrixMap dist,
117 CentralityMap cent,
118 Measure measure)
119{
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;
127
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);
132 put(cent, *i, c);
133 }
134}
135
136template <typename Graph,
137 typename DistanceMatrixMap,
138 typename CentralityMap>
139inline void
140all_closeness_centralities(const Graph& g,
141 DistanceMatrixMap dist,
142 CentralityMap cent)
143{
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;
150
151 all_closeness_centralities(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
152}
153
154} /* namespace boost */
155
156#endif
157

source code of boost/boost/graph/closeness_centrality.hpp