betweenness_centrality_test.cpp

来自「Boost provides free peer-reviewed portab」· C++ 代码 · 共 520 行 · 第 1/2 页

// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
#include <boost/graph/betweenness_centrality.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <vector>
#include <stack>
#include <queue>
#include <boost/property_map.hpp>
#include <boost/test/minimal.hpp>
#include <boost/random/uniform_01.hpp>
#include <boost/random/linear_congruential.hpp>

using namespace boost;

const double error_tolerance = 0.001;

typedef property<edge_weight_t, double,
                 property<edge_index_t, std::size_t> > EdgeProperties;

struct weighted_edge 
{
  int source, target;
  double weight;
};

template<typename Graph>
void 
run_weighted_test(Graph*, int V, weighted_edge edge_init[], int E,
                  double correct_centrality[])
{
  Graph g(V);
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
  typedef typename graph_traits<Graph>::edge_descriptor Edge;

  std::vector<Vertex> vertices(V);
  {
    vertex_iterator v, v_end;
    int index = 0;
    for (tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
      put(vertex_index, g, *v, index);
      vertices[index] = *v;
    }
  }

  std::vector<Edge> edges(E);
  for (int e = 0; e < E; ++e) {
    edges[e] = add_edge(vertices[edge_init[e].source],
                        vertices[edge_init[e].target], 
                        g).first;
    put(edge_weight, g, edges[e], 1.0);
  }

  std::vector<double> centrality(V);
  brandes_betweenness_centrality(
    g,
    centrality_map(
      make_iterator_property_map(centrality.begin(), get(vertex_index, g),
                                 double()))
    .vertex_index_map(get(vertex_index, g)).weight_map(get(edge_weight, g)));


  for (int v = 0; v < V; ++v) {
    BOOST_CHECK(centrality[v] == correct_centrality[v]);
  }
}

struct unweighted_edge 
{
  int source, target;
};

template<typename Graph>
void 
run_unweighted_test(Graph*, int V, unweighted_edge edge_init[], int E,
                    double correct_centrality[],
                    double* correct_edge_centrality = 0)
{
  Graph g(V);
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
  typedef typename graph_traits<Graph>::edge_descriptor Edge;

  std::vector<Vertex> vertices(V);
  {
    vertex_iterator v, v_end;
    int index = 0;
    for (tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
      put(vertex_index, g, *v, index);
      vertices[index] = *v;
    }
  }

  std::vector<Edge> edges(E);
  for (int e = 0; e < E; ++e) {
    edges[e] = add_edge(vertices[edge_init[e].source],
                        vertices[edge_init[e].target], 
                        g).first;
    put(edge_weight, g, edges[e], 1.0);
    put(edge_index, g, edges[e], e);
  }

  std::vector<double> centrality(V);
  std::vector<double> edge_centrality1(E);

  brandes_betweenness_centrality(
    g,
    centrality_map(
      make_iterator_property_map(centrality.begin(), get(vertex_index, g),
                                 double()))
    .edge_centrality_map(
       make_iterator_property_map(edge_centrality1.begin(), 
                                  get(edge_index, g), double()))
    .vertex_index_map(get(vertex_index, g)));

  std::vector<double> centrality2(V);
  std::vector<double> edge_centrality2(E);
  brandes_betweenness_centrality(
    g,
    vertex_index_map(get(vertex_index, g)).weight_map(get(edge_weight, g))
    .centrality_map(
       make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
                                  double()))
    .edge_centrality_map(
       make_iterator_property_map(edge_centrality2.begin(), 
                                  get(edge_index, g), double())));

  std::vector<double> edge_centrality3(E);
  brandes_betweenness_centrality(
    g,
    edge_centrality_map(
      make_iterator_property_map(edge_centrality3.begin(), 
                                 get(edge_index, g), double())));

  for (int v = 0; v < V; ++v) {
    BOOST_CHECK(centrality[v] == centrality2[v]);

    double relative_error = 
      correct_centrality[v] == 0.0? centrality[v]
      : (centrality[v] - correct_centrality[v]) / correct_centrality[v];
    if (relative_error < 0) relative_error = -relative_error;
    BOOST_CHECK(relative_error < error_tolerance);
  }  

  for (int e = 0; e < E; ++e) {
    BOOST_CHECK(edge_centrality1[e] == edge_centrality2[e]);
    BOOST_CHECK(edge_centrality1[e] == edge_centrality3[e]);

    if (correct_edge_centrality) {
      double relative_error = 
        correct_edge_centrality[e] == 0.0? edge_centrality1[e]
        : (edge_centrality1[e] - correct_edge_centrality[e]) 
        / correct_edge_centrality[e];
      if (relative_error < 0) relative_error = -relative_error;
      BOOST_CHECK(relative_error < error_tolerance);

      if (relative_error >= error_tolerance) {
        std::cerr << "Edge " << e << " has edge centrality " 
                  << edge_centrality1[e] << ", should be " 
                  << correct_edge_centrality[e] << std::endl;
      }
    }
  }
}

template<typename Graph>
void
run_wheel_test(Graph*, int V)
{
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
  typedef typename graph_traits<Graph>::edge_descriptor Edge;

  Graph g(V);
  Vertex center = *boost::vertices(g).first;

  std::vector<Vertex> vertices(V);
  {
    vertex_iterator v, v_end;
    int index = 0;
    for (tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
      put(vertex_index, g, *v, index);
      vertices[index] = *v;
      if (*v != center) {
        Edge e = add_edge(*v, center, g).first;
        put(edge_weight, g, e, 1.0);
      }
    }
  }

  std::vector<double> centrality(V);
  brandes_betweenness_centrality(
    g,
    make_iterator_property_map(centrality.begin(), get(vertex_index, g),
                               double()));

  std::vector<double> centrality2(V);
  brandes_betweenness_centrality(
    g,
    centrality_map(
      make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
                                 double()))
    .vertex_index_map(get(vertex_index, g)).weight_map(get(edge_weight, g)));

  relative_betweenness_centrality(
    g,
    make_iterator_property_map(centrality.begin(), get(vertex_index, g),
                               double()));

  relative_betweenness_centrality(
    g,
    make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
                               double()));

  for (int v = 0; v < V; ++v) {
    BOOST_CHECK(centrality[v] == centrality2[v]);
    BOOST_CHECK((v == 0 && centrality[v] == 1)
               || (v != 0 && centrality[v] == 0));
  } 

  double dominance = 
    central_point_dominance(
      g, 
      make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
                                 double()));
  BOOST_CHECK(dominance == 1.0);
}

template<typename MutableGraph>
void randomly_add_edges(MutableGraph& g, double edge_probability)
{
  typedef typename graph_traits<MutableGraph>::directed_category
    directed_category;
  const bool is_undirected = 
    is_same<directed_category, undirected_tag>::value;

  minstd_rand gen;
  uniform_01<minstd_rand, double> rand_gen(gen);

  typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex;
  typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    vertex v = *vi;
    typename graph_traits<MutableGraph>::vertex_iterator wi 
      = is_undirected? vi : vertices(g).first;
    while (wi != vi_end) {
      vertex w = *wi++;
      if (v != w) {
        if (rand_gen() < edge_probability) add_edge(v, w, g);
      }
    }
  }
}