ceph/src/boost/libs/graph/test/degree_centrality.cpp

   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 #include <vector>
   8
   9 #include <boost/graph/undirected_graph.hpp>
  10 #include <boost/graph/directed_graph.hpp>
  11 #include <boost/graph/degree_centrality.hpp>
  12 #include <boost/graph/exterior_property.hpp>
  13
  14 using namespace std;
  15 using namespace boost;
  16
  17 // useful types
  18 // number of vertices in the graph
  19 static const unsigned N = 5;
  20
  21 template <typename Graph>
  22 void build_graph(Graph& g,
  23                  vector<typename graph_traits<Graph>::vertex_descriptor>& v)
  24 {
  25     // add vertices
  26     for(size_t i = 0; i < N; ++i) {
  27         v[i] = add_vertex(g);
  28     }
  29
  30     // add edges
  31     add_edge(v[0], v[1], g);
  32     add_edge(v[1], v[2], g);
  33     add_edge(v[2], v[0], g);
  34     add_edge(v[3], v[4], g);
  35     add_edge(v[4], v[0], g);
  36 }
  37
  38 template <typename Graph>
  39 void test_undirected()
  40 {
  41     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  42
  43     typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
  44     typedef typename CentralityProperty::container_type CentralityContainer;
  45     typedef typename CentralityProperty::map_type CentralityMap;
  46
  47     Graph g;
  48     vector<Vertex> v(N);
  49     build_graph(g, v);
  50
  51     CentralityContainer cents(num_vertices(g));
  52     CentralityMap cm(cents, g);
  53     all_degree_centralities(g, cm);
  54
  55     BOOST_ASSERT(cm[v[0]] == 3);
  56     BOOST_ASSERT(cm[v[1]] == 2);
  57     BOOST_ASSERT(cm[v[2]] == 2);
  58     BOOST_ASSERT(cm[v[3]] == 1);
  59     BOOST_ASSERT(cm[v[4]] == 2);
  60 }
  61
  62 template <typename Graph>
  63 void test_influence()
  64 {
  65     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  66
  67     typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
  68     typedef typename CentralityProperty::container_type CentralityContainer;
  69     typedef typename CentralityProperty::map_type CentralityMap;
  70
  71     Graph g;
  72
  73     vector<Vertex> v(N);
  74     build_graph(g, v);
  75
  76     CentralityContainer cents(num_vertices(g));
  77     CentralityMap cm(cents, g);
  78     all_influence_values(g, cm);
  79
  80     BOOST_ASSERT(cm[v[0]] == 1);
  81     BOOST_ASSERT(cm[v[1]] == 1);
  82     BOOST_ASSERT(cm[v[2]] == 1);
  83     BOOST_ASSERT(cm[v[3]] == 1);
  84     BOOST_ASSERT(cm[v[4]] == 1);
  85 }
  86
  87 template <typename Graph>
  88 void test_prestige()
  89 {
  90     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  91
  92     typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
  93     typedef typename CentralityProperty::container_type CentralityContainer;
  94     typedef typename CentralityProperty::map_type CentralityMap;
  95
  96     Graph g;
  97
  98     vector<Vertex> v(N);
  99     build_graph(g, v);
 100
 101     CentralityContainer cents(num_vertices(g));
 102     CentralityMap cm(cents, g);
 103     all_prestige_values(g, cm);
 104
 105     BOOST_ASSERT(cm[v[0]] == 2);
 106     BOOST_ASSERT(cm[v[1]] == 1);
 107     BOOST_ASSERT(cm[v[2]] == 1);
 108     BOOST_ASSERT(cm[v[3]] == 0);
 109     BOOST_ASSERT(cm[v[4]] == 1);
 110 }
 111
 112 int
 113 main(int, char *[])
 114 {
 115     typedef undirected_graph<> Graph;
 116     typedef directed_graph<> Digraph;
 117
 118     test_undirected<Graph>();
 119     test_influence<Digraph>();
 120     test_prestige<Digraph>();
 121 }