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