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_DEGREE_CENTRALITY_HPP
8 #define BOOST_GRAPH_DEGREE_CENTRALITY_HPP
9
10 #include <boost/graph/graph_concepts.hpp>
11 #include <boost/concept/assert.hpp>
12
13 namespace boost {
14
15 template <typename Graph>
16 struct degree_centrality_measure
17 {
18 typedef typename graph_traits<Graph>::degree_size_type degree_type;
19 typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
20 };
21
22 template <typename Graph>
23 struct influence_measure
24 : public degree_centrality_measure<Graph>
25 {
26 typedef degree_centrality_measure<Graph> base_type;
27 typedef typename base_type::degree_type degree_type;
28 typedef typename base_type::vertex_type vertex_type;
29
operator ()boost::influence_measure30 inline degree_type operator ()(vertex_type v, const Graph& g)
31 {
32 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
33 return out_degree(v, g);
34 }
35 };
36
37 template <typename Graph>
38 inline influence_measure<Graph>
measure_influence(const Graph &)39 measure_influence(const Graph&)
40 { return influence_measure<Graph>(); }
41
42
43 template <typename Graph>
44 struct prestige_measure
45 : public degree_centrality_measure<Graph>
46 {
47 typedef degree_centrality_measure<Graph> base_type;
48 typedef typename base_type::degree_type degree_type;
49 typedef typename base_type::vertex_type vertex_type;
50
operator ()boost::prestige_measure51 inline degree_type operator ()(vertex_type v, const Graph& g)
52 {
53 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
54 return in_degree(v, g);
55 }
56 };
57
58 template <typename Graph>
59 inline prestige_measure<Graph>
measure_prestige(const Graph &)60 measure_prestige(const Graph&)
61 { return prestige_measure<Graph>(); }
62
63
64 template <typename Graph, typename Vertex, typename Measure>
65 inline typename Measure::degree_type
degree_centrality(const Graph & g,Vertex v,Measure measure)66 degree_centrality(const Graph& g, Vertex v, Measure measure)
67 {
68 BOOST_CONCEPT_ASSERT(( DegreeMeasureConcept<Measure, Graph> ));
69 return measure(v, g);
70 }
71
72 template <typename Graph, typename Vertex>
73 inline typename graph_traits<Graph>::degree_size_type
degree_centrality(const Graph & g,Vertex v)74 degree_centrality(const Graph& g, Vertex v)
75 {
76 return degree_centrality(g, v, measure_influence(g));
77 }
78
79
80 // These are alias functions, intended to provide a more expressive interface.
81
82 template <typename Graph, typename Vertex>
83 inline typename graph_traits<Graph>::degree_size_type
influence(const Graph & g,Vertex v)84 influence(const Graph& g, Vertex v)
85 { return degree_centrality(g, v, measure_influence(g)); }
86
87
88 template <typename Graph, typename Vertex>
89 inline typename graph_traits<Graph>::degree_size_type
prestige(const Graph & g,Vertex v)90 prestige(const Graph& g, Vertex v)
91 { return degree_centrality(g, v, measure_prestige(g)); }
92
93
94 template <typename Graph, typename CentralityMap, typename Measure>
95 inline void
all_degree_centralities(const Graph & g,CentralityMap cent,Measure measure)96 all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure)
97 {
98 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
99 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
100 typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
101 BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<CentralityMap,Vertex> ));
102 typedef typename property_traits<CentralityMap>::value_type Centrality;
103
104 VertexIterator i, end;
105 for(boost::tie(i, end) = vertices(g); i != end; ++i) {
106 Centrality c = degree_centrality(g, *i, measure);
107 put(cent, *i, c);
108 }
109 }
110
111 template <typename Graph, typename CentralityMap>
all_degree_centralities(const Graph & g,CentralityMap cent)112 inline void all_degree_centralities(const Graph& g, CentralityMap cent)
113 { all_degree_centralities(g, cent, measure_influence(g)); }
114
115 // More helper functions for computing influence and prestige.
116 // I hate the names of these functions, but influence and prestige
117 // don't pluralize too well.
118
119 template <typename Graph, typename CentralityMap>
all_influence_values(const Graph & g,CentralityMap cent)120 inline void all_influence_values(const Graph& g, CentralityMap cent)
121 { all_degree_centralities(g, cent, measure_influence(g)); }
122
123 template <typename Graph, typename CentralityMap>
all_prestige_values(const Graph & g,CentralityMap cent)124 inline void all_prestige_values(const Graph& g, CentralityMap cent)
125 { all_degree_centralities(g, cent, measure_prestige(g)); }
126
127 } /* namespace boost */
128
129 #endif
130
131
132