Chris@16: // (C) Copyright 2007-2009 Andrew Sutton
Chris@16: //
Chris@16: // Use, modification and distribution are subject to the
Chris@16: // Boost Software License, Version 1.0 (See accompanying file
Chris@16: // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_DEGREE_CENTRALITY_HPP
Chris@16: #define BOOST_GRAPH_DEGREE_CENTRALITY_HPP
Chris@16: 
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: struct degree_centrality_measure
Chris@16: {
Chris@16:     typedef typename graph_traits<Graph>::degree_size_type degree_type;
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
Chris@16: };
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: struct influence_measure
Chris@16:     : public degree_centrality_measure<Graph>
Chris@16: {
Chris@16:     typedef degree_centrality_measure<Graph> base_type;
Chris@16:     typedef typename base_type::degree_type degree_type;
Chris@16:     typedef typename base_type::vertex_type vertex_type;
Chris@16: 
Chris@16:     inline degree_type operator ()(vertex_type v, const Graph& g)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
Chris@16:         return out_degree(v, g);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: inline influence_measure<Graph>
Chris@16: measure_influence(const Graph&)
Chris@16: { return influence_measure<Graph>(); }
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: struct prestige_measure
Chris@16:     : public degree_centrality_measure<Graph>
Chris@16: {
Chris@16:     typedef degree_centrality_measure<Graph> base_type;
Chris@16:     typedef typename base_type::degree_type degree_type;
Chris@16:     typedef typename base_type::vertex_type vertex_type;
Chris@16: 
Chris@16:     inline degree_type operator ()(vertex_type v, const Graph& g)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));
Chris@16:         return in_degree(v, g);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: inline prestige_measure<Graph>
Chris@16: measure_prestige(const Graph&)
Chris@16: { return prestige_measure<Graph>(); }
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph, typename Vertex, typename Measure>
Chris@16: inline typename Measure::degree_type
Chris@16: degree_centrality(const Graph& g, Vertex v, Measure measure)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( DegreeMeasureConcept<Measure, Graph> ));
Chris@16:     return measure(v, g);
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename Vertex>
Chris@16: inline typename graph_traits<Graph>::degree_size_type
Chris@16: degree_centrality(const Graph& g, Vertex v)
Chris@16: {
Chris@16:     return degree_centrality(g, v, measure_influence(g));
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // These are alias functions, intended to provide a more expressive interface.
Chris@16: 
Chris@16: template <typename Graph, typename Vertex>
Chris@16: inline typename graph_traits<Graph>::degree_size_type
Chris@16: influence(const Graph& g, Vertex v)
Chris@16: { return degree_centrality(g, v, measure_influence(g)); }
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph, typename Vertex>
Chris@16: inline typename graph_traits<Graph>::degree_size_type
Chris@16: prestige(const Graph& g, Vertex v)
Chris@16: { return degree_centrality(g, v, measure_prestige(g)); }
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph, typename CentralityMap, typename Measure>
Chris@16: inline void
Chris@16: all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure)
Chris@16: {
Chris@16:     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
Chris@16:     BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<CentralityMap,Vertex> ));
Chris@16:     typedef typename property_traits<CentralityMap>::value_type Centrality;
Chris@16: 
Chris@16:     VertexIterator i, end;
Chris@16:     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
Chris@16:         Centrality c = degree_centrality(g, *i, measure);
Chris@16:         put(cent, *i, c);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: template <typename Graph, typename CentralityMap>
Chris@16: inline void all_degree_centralities(const Graph& g, CentralityMap cent)
Chris@16: { all_degree_centralities(g, cent, measure_influence(g)); }
Chris@16: 
Chris@16: // More helper functions for computing influence and prestige.
Chris@16: // I hate the names of these functions, but influence and prestige
Chris@16: // don't pluralize too well.
Chris@16: 
Chris@16: template <typename Graph, typename CentralityMap>
Chris@16: inline void all_influence_values(const Graph& g, CentralityMap cent)
Chris@16: { all_degree_centralities(g, cent, measure_influence(g)); }
Chris@16: 
Chris@16: template <typename Graph, typename CentralityMap>
Chris@16: inline void all_prestige_values(const Graph& g, CentralityMap cent)
Chris@16: { all_degree_centralities(g, cent, measure_prestige(g)); }
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: