ceph/src/boost/libs/graph/include/boost/graph/degree_centrality.hpp

   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
  30     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>
  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
  51     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>
  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
  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
  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
  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
  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
  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>
 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>
 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>
 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