libs/graph/test/clustering_coefficient.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 <iostream>
   8
   9 #include <boost/graph/undirected_graph.hpp>
  10 #include <boost/graph/directed_graph.hpp>
  11 #include <boost/graph/exterior_property.hpp>
  12 #include <boost/graph/clustering_coefficient.hpp>
  13
  14 using namespace std;
  15 using namespace boost;
  16
  17 // number of vertices in the graph
  18 static const unsigned N = 5;
  19
  20 template <typename Graph>
  21 struct vertex_vector
  22 {
  23     typedef graph_traits<Graph> traits;
  24     typedef vector<typename traits::vertex_descriptor> type;
  25 };
  26
  27 template <typename Graph>
  28 void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
  29 {
  30     // add vertices
  31     for(size_t i = 0; i < N; ++i) {
  32         v[i] = add_vertex(g);
  33     }
  34
  35     // add edges
  36     add_edge(v[0], v[1], g);
  37     add_edge(v[1], v[2], g);
  38     add_edge(v[2], v[0], g);
  39     add_edge(v[3], v[4], g);
  40     add_edge(v[4], v[0], g);
  41 }
  42
  43 template <typename Graph>
  44 void test_undirected()
  45 {
  46     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  47
  48     typedef exterior_vertex_property<Graph, double> ClusteringProperty;
  49     typedef typename ClusteringProperty::container_type ClusteringContainer;
  50     typedef typename ClusteringProperty::map_type ClusteringMap;
  51
  52     Graph g;
  53     vector<Vertex> v(N);
  54     build_graph(g, v);
  55
  56     ClusteringContainer cc(num_vertices(g));
  57     ClusteringMap cm(cc, g);
  58
  59     BOOST_ASSERT(num_paths_through_vertex(g, v[0]) == 3);
  60     BOOST_ASSERT(num_paths_through_vertex(g, v[1]) == 1);
  61     BOOST_ASSERT(num_paths_through_vertex(g, v[2]) == 1);
  62     BOOST_ASSERT(num_paths_through_vertex(g, v[3]) == 0);
  63     BOOST_ASSERT(num_paths_through_vertex(g, v[4]) == 1);
  64
  65     BOOST_ASSERT(num_triangles_on_vertex(g, v[0]) == 1);
  66     BOOST_ASSERT(num_triangles_on_vertex(g, v[1]) == 1);
  67     BOOST_ASSERT(num_triangles_on_vertex(g, v[2]) == 1);
  68     BOOST_ASSERT(num_triangles_on_vertex(g, v[3]) == 0);
  69     BOOST_ASSERT(num_triangles_on_vertex(g, v[4]) == 0);
  70
  71     // TODO: Need a FP approximation to assert here.
  72     // BOOST_ASSERT(clustering_coefficient(g, v[0]) == double(1)/3);
  73     BOOST_ASSERT(clustering_coefficient(g, v[1]) == 1);
  74     BOOST_ASSERT(clustering_coefficient(g, v[2]) == 1);
  75     BOOST_ASSERT(clustering_coefficient(g, v[3]) == 0);
  76     BOOST_ASSERT(clustering_coefficient(g, v[4]) == 0);
  77
  78     all_clustering_coefficients(g, cm);
  79
  80     // TODO: Need a FP approximation to assert here.
  81     // BOOST_ASSERT(cm[v[0]] == double(1)/3);
  82     BOOST_ASSERT(cm[v[1]] == 1);
  83     BOOST_ASSERT(cm[v[2]] == 1);
  84     BOOST_ASSERT(cm[v[3]] == 0);
  85     BOOST_ASSERT(cm[v[4]] == 0);
  86
  87     // I would have used check_close, but apparently, that requires
  88     // me to link this against a library - which I don't really want
  89     // to do. Basically, this makes sure that that coefficient is
  90     // within some tolerance (like 1/10 million).
  91     double coef = mean_clustering_coefficient(g, cm);
  92     BOOST_ASSERT((coef - (7.0f / 15.0f)) < 1e-7f);
  93 }
  94
  95 int
  96 main(int, char *[])
  97 {
  98     typedef undirected_graph<> Graph;
  99     // typedef directed_graph<> Digraph;
 100
 101     // TODO: write a test for directed clustering coefficient.
 102
 103     test_undirected<Graph>();
 104     // test<Digraph>();
 105 }