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, typename DistanceType, typename ResultType,
17 typename Reciprocal = detail::reciprocal< ResultType > >
18 struct closeness_measure
19 : public geodesic_measure< Graph, DistanceType, ResultType >
20 {
21 typedef geodesic_measure< Graph, DistanceType, ResultType > base_type;
22 typedef typename base_type::distance_type distance_type;
23 typedef typename base_type::result_type result_type;
24
operator ()boost::closeness_measure25 result_type operator()(distance_type d, const Graph&)
26 {
27 BOOST_CONCEPT_ASSERT((NumericValueConcept< DistanceType >));
28 BOOST_CONCEPT_ASSERT((NumericValueConcept< ResultType >));
29 BOOST_CONCEPT_ASSERT((AdaptableUnaryFunctionConcept< Reciprocal,
30 ResultType, ResultType >));
31 return (d == base_type::infinite_distance()) ? base_type::zero_result()
32 : rec(result_type(d));
33 }
34 Reciprocal rec;
35 };
36
37 template < typename Graph, typename DistanceMap >
38 inline closeness_measure< Graph,
39 typename property_traits< DistanceMap >::value_type, double,
40 detail::reciprocal< double > >
measure_closeness(const Graph &,DistanceMap)41 measure_closeness(const Graph&, DistanceMap)
42 {
43 typedef typename property_traits< DistanceMap >::value_type Distance;
44 return closeness_measure< Graph, Distance, double,
45 detail::reciprocal< double > >();
46 }
47
48 template < typename T, typename Graph, typename DistanceMap >
49 inline closeness_measure< Graph,
50 typename property_traits< DistanceMap >::value_type, T,
51 detail::reciprocal< T > >
measure_closeness(const Graph &,DistanceMap)52 measure_closeness(const Graph&, DistanceMap)
53 {
54 typedef typename property_traits< DistanceMap >::value_type Distance;
55 return closeness_measure< Graph, Distance, T, detail::reciprocal< T > >();
56 }
57
58 template < typename T, typename Graph, typename DistanceMap,
59 typename Reciprocal >
60 inline closeness_measure< Graph,
61 typename property_traits< DistanceMap >::value_type, T, Reciprocal >
measure_closeness(const Graph &,DistanceMap)62 measure_closeness(const Graph&, DistanceMap)
63 {
64 typedef typename property_traits< DistanceMap >::value_type Distance;
65 return closeness_measure< Graph, Distance, T, Reciprocal >();
66 }
67
68 template < typename Graph, typename DistanceMap, typename Measure,
69 typename Combinator >
closeness_centrality(const Graph & g,DistanceMap dist,Measure measure,Combinator combine)70 inline typename Measure::result_type closeness_centrality(
71 const Graph& g, DistanceMap dist, Measure measure, Combinator combine)
72 {
73 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
74 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
75 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
76 typedef typename property_traits< DistanceMap >::value_type Distance;
77 BOOST_CONCEPT_ASSERT((NumericValueConcept< Distance >));
78 BOOST_CONCEPT_ASSERT((DistanceMeasureConcept< Measure, Graph >));
79
80 Distance n = detail::combine_distances(g, dist, combine, Distance(0));
81 return measure(n, g);
82 }
83
84 template < typename Graph, typename DistanceMap, typename Measure >
closeness_centrality(const Graph & g,DistanceMap dist,Measure measure)85 inline typename Measure::result_type closeness_centrality(
86 const Graph& g, DistanceMap dist, Measure measure)
87 {
88 BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
89 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
90 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
91 typedef typename property_traits< DistanceMap >::value_type Distance;
92
93 return closeness_centrality(g, dist, measure, std::plus< Distance >());
94 }
95
96 template < typename Graph, typename DistanceMap >
closeness_centrality(const Graph & g,DistanceMap dist)97 inline double closeness_centrality(const Graph& g, DistanceMap dist)
98 {
99 return closeness_centrality(g, dist, measure_closeness(g, dist));
100 }
101
102 template < typename T, typename Graph, typename DistanceMap >
closeness_centrality(const Graph & g,DistanceMap dist)103 inline T closeness_centrality(const Graph& g, DistanceMap dist)
104 {
105 return closeness_centrality(g, dist, measure_closeness< T >(g, dist));
106 }
107
108 template < typename Graph, typename DistanceMatrixMap, typename CentralityMap,
109 typename Measure >
all_closeness_centralities(const Graph & g,DistanceMatrixMap dist,CentralityMap cent,Measure measure)110 inline void all_closeness_centralities(
111 const Graph& g, DistanceMatrixMap dist, CentralityMap cent, Measure measure)
112 {
113 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
114 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
115 BOOST_CONCEPT_ASSERT(
116 (ReadablePropertyMapConcept< DistanceMatrixMap, Vertex >));
117 typedef
118 typename property_traits< DistanceMatrixMap >::value_type DistanceMap;
119 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
120 BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept< CentralityMap, Vertex >));
121 typedef typename property_traits< CentralityMap >::value_type Centrality;
122
123 typename graph_traits< Graph >::vertex_iterator i, end;
124 for (boost::tie(i, end) = vertices(g); i != end; ++i)
125 {
126 DistanceMap dm = get(dist, *i);
127 Centrality c = closeness_centrality(g, dm, measure);
128 put(cent, *i, c);
129 }
130 }
131
132 template < typename Graph, typename DistanceMatrixMap, typename CentralityMap >
all_closeness_centralities(const Graph & g,DistanceMatrixMap dist,CentralityMap cent)133 inline void all_closeness_centralities(
134 const Graph& g, DistanceMatrixMap dist, CentralityMap cent)
135 {
136 BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
137 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
138 BOOST_CONCEPT_ASSERT(
139 (ReadablePropertyMapConcept< DistanceMatrixMap, Vertex >));
140 typedef
141 typename property_traits< DistanceMatrixMap >::value_type DistanceMap;
142 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< DistanceMap, Vertex >));
143 typedef typename property_traits< CentralityMap >::value_type Result;
144
145 all_closeness_centralities(
146 g, dist, cent, measure_closeness< Result >(g, DistanceMap()));
147 }
148
149 } /* namespace boost */
150
151 #endif
152