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
14 namespace boost
15 {
16 template <typename Graph,
17 typename DistanceType,
18 typename ResultType,
19 typename Reciprocal = detail::reciprocal<ResultType> >
20 struct 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
operator ()boost::closeness_measure27 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
39 template <typename Graph, typename DistanceMap>
40 inline closeness_measure<
41 Graph, typename property_traits<DistanceMap>::value_type, double,
42 detail::reciprocal<double> >
measure_closeness(const Graph &,DistanceMap)43 measure_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
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> >
measure_closeness(const Graph &,DistanceMap)53 measure_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
59 template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
60 inline closeness_measure<
61 Graph, typename property_traits<DistanceMap>::value_type, T,
62 Reciprocal>
measure_closeness(const Graph &,DistanceMap)63 measure_closeness(const Graph&, DistanceMap)
64 {
65 typedef typename property_traits<DistanceMap>::value_type Distance;
66 return closeness_measure<Graph, Distance, T, Reciprocal>();
67 }
68
69 template <typename Graph,
70 typename DistanceMap,
71 typename Measure,
72 typename Combinator>
73 inline typename Measure::result_type
closeness_centrality(const Graph & g,DistanceMap dist,Measure measure,Combinator combine)74 closeness_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
90 template <typename Graph, typename DistanceMap, typename Measure>
91 inline typename Measure::result_type
closeness_centrality(const Graph & g,DistanceMap dist,Measure measure)92 closeness_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
102 template <typename Graph, typename DistanceMap>
closeness_centrality(const Graph & g,DistanceMap dist)103 inline double closeness_centrality(const Graph& g, DistanceMap dist)
104 { return closeness_centrality(g, dist, measure_closeness(g, dist)); }
105
106 template <typename T, typename Graph, typename DistanceMap>
closeness_centrality(const Graph & g,DistanceMap dist)107 inline T closeness_centrality(const Graph& g, DistanceMap dist)
108 { return closeness_centrality(g, dist, measure_closeness<T>(g, dist)); }
109
110 template <typename Graph,
111 typename DistanceMatrixMap,
112 typename CentralityMap,
113 typename Measure>
114 inline void
all_closeness_centralities(const Graph & g,DistanceMatrixMap dist,CentralityMap cent,Measure measure)115 all_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
136 template <typename Graph,
137 typename DistanceMatrixMap,
138 typename CentralityMap>
139 inline void
all_closeness_centralities(const Graph & g,DistanceMatrixMap dist,CentralityMap cent)140 all_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