boost/graph/degree_centrality.hpp

0001 // (C) Copyright 2007-2009 Andrew Sutton
0002 //
0003 // Use, modification and distribution are subject to the
0004 // Boost Software License, Version 1.0 (See accompanying file
0005 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_DEGREE_CENTRALITY_HPP
0008 #define BOOST_GRAPH_DEGREE_CENTRALITY_HPP
0009
0010 #include <boost/graph/graph_concepts.hpp>
0011 #include <boost/concept/assert.hpp>
0012
0013 namespace boost
0014 {
0015
0016 template < typename Graph > struct degree_centrality_measure
0017 {
0018     typedef typename graph_traits< Graph >::degree_size_type degree_type;
0019     typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0020 };
0021
0022 template < typename Graph >
0023 struct influence_measure : public degree_centrality_measure< Graph >
0024 {
0025     typedef degree_centrality_measure< Graph > base_type;
0026     typedef typename base_type::degree_type degree_type;
0027     typedef typename base_type::vertex_type vertex_type;
0028
0029     inline degree_type operator()(vertex_type v, const Graph& g)
0030     {
0031         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
0032         return out_degree(v, g);
0033     }
0034 };
0035
0036 template < typename Graph >
0037 inline influence_measure< Graph > measure_influence(const Graph&)
0038 {
0039     return influence_measure< Graph >();
0040 }
0041
0042 template < typename Graph >
0043 struct prestige_measure : public degree_centrality_measure< Graph >
0044 {
0045     typedef degree_centrality_measure< Graph > base_type;
0046     typedef typename base_type::degree_type degree_type;
0047     typedef typename base_type::vertex_type vertex_type;
0048
0049     inline degree_type operator()(vertex_type v, const Graph& g)
0050     {
0051         BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< Graph >));
0052         return in_degree(v, g);
0053     }
0054 };
0055
0056 template < typename Graph >
0057 inline prestige_measure< Graph > measure_prestige(const Graph&)
0058 {
0059     return prestige_measure< Graph >();
0060 }
0061
0062 template < typename Graph, typename Vertex, typename Measure >
0063 inline typename Measure::degree_type degree_centrality(
0064     const Graph& g, Vertex v, Measure measure)
0065 {
0066     BOOST_CONCEPT_ASSERT((DegreeMeasureConcept< Measure, Graph >));
0067     return measure(v, g);
0068 }
0069
0070 template < typename Graph, typename Vertex >
0071 inline typename graph_traits< Graph >::degree_size_type degree_centrality(
0072     const Graph& g, Vertex v)
0073 {
0074     return degree_centrality(g, v, measure_influence(g));
0075 }
0076
0077 // These are alias functions, intended to provide a more expressive interface.
0078
0079 template < typename Graph, typename Vertex >
0080 inline typename graph_traits< Graph >::degree_size_type influence(
0081     const Graph& g, Vertex v)
0082 {
0083     return degree_centrality(g, v, measure_influence(g));
0084 }
0085
0086 template < typename Graph, typename Vertex >
0087 inline typename graph_traits< Graph >::degree_size_type prestige(
0088     const Graph& g, Vertex v)
0089 {
0090     return degree_centrality(g, v, measure_prestige(g));
0091 }
0092
0093 template < typename Graph, typename CentralityMap, typename Measure >
0094 inline void all_degree_centralities(
0095     const Graph& g, CentralityMap cent, Measure measure)
0096 {
0097     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0098     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0099     typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
0100     BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept< CentralityMap, Vertex >));
0101     typedef typename property_traits< CentralityMap >::value_type Centrality;
0102
0103     VertexIterator i, end;
0104     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0105     {
0106         Centrality c = degree_centrality(g, *i, measure);
0107         put(cent, *i, c);
0108     }
0109 }
0110
0111 template < typename Graph, typename CentralityMap >
0112 inline void all_degree_centralities(const Graph& g, CentralityMap cent)
0113 {
0114     all_degree_centralities(g, cent, measure_influence(g));
0115 }
0116
0117 // More helper functions for computing influence and prestige.
0118 // I hate the names of these functions, but influence and prestige
0119 // don't pluralize too well.
0120
0121 template < typename Graph, typename CentralityMap >
0122 inline void all_influence_values(const Graph& g, CentralityMap cent)
0123 {
0124     all_degree_centralities(g, cent, measure_influence(g));
0125 }
0126
0127 template < typename Graph, typename CentralityMap >
0128 inline void all_prestige_values(const Graph& g, CentralityMap cent)
0129 {
0130     all_degree_centralities(g, cent, measure_prestige(g));
0131 }
0132
0133 } /* namespace boost */
0134
0135 #endif