1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
#define BOOST_GRAPH_CLOSENESS_CENTRALITY_HPP
#include <boost/graph/detail/geodesic.hpp>
#include <boost/graph/exterior_property.hpp>
#include <boost/concept/assert.hpp>
namespace boost
{
template <typename Graph,
typename DistanceType,
typename ResultType,
typename Reciprocal = detail::reciprocal<ResultType> >
struct closeness_measure
: public geodesic_measure<Graph, DistanceType, ResultType>
{
typedef geodesic_measure< Graph, DistanceType, ResultType> base_type;
typedef typename base_type::distance_type distance_type;
typedef typename base_type::result_type result_type;
result_type operator ()(distance_type d, const Graph&)
{
BOOST_CONCEPT_ASSERT(( NumericValueConcept<DistanceType> ));
BOOST_CONCEPT_ASSERT(( NumericValueConcept<ResultType> ));
BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Reciprocal,ResultType,ResultType> ));
return (d == base_type::infinite_distance())
? base_type::zero_result()
: rec(result_type(d));
}
Reciprocal rec;
};
template <typename Graph, typename DistanceMap>
inline closeness_measure<
Graph, typename property_traits<DistanceMap>::value_type, double,
detail::reciprocal<double> >
measure_closeness(const Graph&, DistanceMap)
{
typedef typename property_traits<DistanceMap>::value_type Distance;
return closeness_measure<Graph, Distance, double, detail::reciprocal<double> >();
}
template <typename T, typename Graph, typename DistanceMap>
inline closeness_measure<
Graph, typename property_traits<DistanceMap>::value_type, T,
detail::reciprocal<T> >
measure_closeness(const Graph&, DistanceMap)
{
typedef typename property_traits<DistanceMap>::value_type Distance;
return closeness_measure<Graph, Distance, T, detail::reciprocal<T> >();
}
template <typename T, typename Graph, typename DistanceMap, typename Reciprocal>
inline closeness_measure<
Graph, typename property_traits<DistanceMap>::value_type, T,
Reciprocal>
measure_closeness(const Graph&, DistanceMap)
{
typedef typename property_traits<DistanceMap>::value_type Distance;
return closeness_measure<Graph, Distance, T, Reciprocal>();
}
template <typename Graph,
typename DistanceMap,
typename Measure,
typename Combinator>
inline typename Measure::result_type
closeness_centrality(const Graph& g,
DistanceMap dist,
Measure measure,
Combinator combine)
{
BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
typedef typename property_traits<DistanceMap>::value_type Distance;
BOOST_CONCEPT_ASSERT(( NumericValueConcept<Distance> ));
BOOST_CONCEPT_ASSERT(( DistanceMeasureConcept<Measure,Graph> ));
Distance n = detail::combine_distances(g, dist, combine, Distance(0));
return measure(n, g);
}
template <typename Graph, typename DistanceMap, typename Measure>
inline typename Measure::result_type
closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
{
BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
typedef typename property_traits<DistanceMap>::value_type Distance;
return closeness_centrality(g, dist, measure, std::plus<Distance>());
}
template <typename Graph, typename DistanceMap>
inline double closeness_centrality(const Graph& g, DistanceMap dist)
{ return closeness_centrality(g, dist, measure_closeness(g, dist)); }
template <typename T, typename Graph, typename DistanceMap>
inline T closeness_centrality(const Graph& g, DistanceMap dist)
{ return closeness_centrality(g, dist, measure_closeness<T>(g, dist)); }
template <typename Graph,
typename DistanceMatrixMap,
typename CentralityMap,
typename Measure>
inline void
all_closeness_centralities(const Graph& g,
DistanceMatrixMap dist,
CentralityMap cent,
Measure measure)
{
BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> ));
typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<CentralityMap,Vertex> ));
typedef typename property_traits<CentralityMap>::value_type Centrality;
typename graph_traits<Graph>::vertex_iterator i, end;
for(boost::tie(i, end) = vertices(g); i != end; ++i) {
DistanceMap dm = get(dist, *i);
Centrality c = closeness_centrality(g, dm, measure);
put(cent, *i, c);
}
}
template <typename Graph,
typename DistanceMatrixMap,
typename CentralityMap>
inline void
all_closeness_centralities(const Graph& g,
DistanceMatrixMap dist,
CentralityMap cent)
{
BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> ));
typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
typedef typename property_traits<CentralityMap>::value_type Result;
all_closeness_centralities(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
}
} /* namespace boost */
#endif
|
