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 | |
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 | |
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) |
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> > |
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> |
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 |
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 |
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> |
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> |
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 |
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 |
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 | |