[Boost-commit] svn:boost r38850 - sandbox/SOC/2007/graphs/libs/graph/test

From: asutton_at_[hidden]
Date: 2007-08-22 11:09:00

Author: asutton
Date: 2007-08-22 11:09:00 EDT (Wed, 22 Aug 2007)
New Revision: 38850
URL: http://svn.boost.org/trac/boost/changeset/38850

Log:
Added clustering coef tests

Added:
   sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp
      - copied, changed from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp
Removed:
   sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2                 |     2                                         
   sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp   |     1                                         
   sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp |    94 +++++++++++++++++++++++++++------------ 
   3 files changed, 65 insertions(+), 32 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	2007-08-22 11:09:00 EDT (Wed, 22 Aug 2007)
@@ -29,7 +29,7 @@
 #
 # exe components : components.cpp ;
 #
-# exe cluster : cluster.cpp ;
+exe clustering_coefficient : clustering_coefficient.cpp ;
 #
 # exe generate : generate.cpp ;
 #

Modified: sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp	2007-08-22 11:09:00 EDT (Wed, 22 Aug 2007)
@@ -17,7 +17,6 @@
 using namespace std;
 using namespace boost;
 
-// useful types
 // number of vertices in the graph
 static const unsigned N = 5;
 

Deleted: sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp	2007-08-22 11:09:00 EDT (Wed, 22 Aug 2007)
+++ (empty file)
@@ -1,74 +0,0 @@
-// (C) Copyright Andrew Sutton 2007
-//
-// Use, modification and distribution are subject to the
-// Boost Software License, Version 1.0 (See accompanying file
-// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
-
-#include <iostream>
-#include <iterator>
-#include <algorithm>
-#include <vector>
-#include <map>
-#include <tr1/unordered_map>
-
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/clustering_coefficient.hpp>
-
-using namespace std;
-using namespace boost;
-
-template <typename Graph>
-void build_graph(Graph& g)
-{
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::edge_descriptor Edge;
-
-    static const unsigned N = 5;
-    vector<Vertex> v(N);
-    vector<Edge> e;
-
-    // add some vertices
-    for(size_t i = 0; i < N; ++i) {
-        // v[i] = add_vertex(g);
-        v[i] = add_vertex(g);
-    }
-
-    // add some edges (with weights)
-    add_edge(v[0], v[1], g);
-    add_edge(v[1], v[2], g);
-    add_edge(v[2], v[0], g);
-    add_edge(v[3], v[4], g);
-    add_edge(v[4], v[0], g);
-};
-
-template <typename Graph>
-void test()
-{
-    Graph g;
-    build_graph(g);
-
-    typename graph_traits<Graph>::vertex_iterator i, end;
-    for(tie(i, end) = vertices(g); i != end; ++i) {
-        unsigned id = get(vertex_index, g, *i);
-        size_t r = vertex_num_routes(g, *i);
-        size_t t = vertex_num_triangles(g, *i);
-        float coef = vertex_clustering_coefficient(g, *i);
-        std::cout << id << " {" << r << " " << t << " " << coef << "}\n";
-    }
-    cerr << "  cc: " << graph_clustering_coefficient(g) << "\n";
-}
-
-int
-main(int argc, char *argv[])
-{
-    typedef undirected_graph<> Graph;
-    typedef directed_graph<> Digraph;
-
-    std::cout << "*** undirected_graph<> ***\n";
-    test<Graph>();
-
-    std::cout << "*** directed_graph<> ***\n";
-    test<Digraph>();
-}

Copied: sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp (from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp	2007-08-22 11:09:00 EDT (Wed, 22 Aug 2007)
@@ -5,37 +5,39 @@
 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
 
 #include <iostream>
-#include <iterator>
-#include <algorithm>
-#include <vector>
-#include <map>
-#include <tr1/unordered_map>
 
-#include <boost/graph/adjacency_list.hpp>
+#include <boost/detail/lightweight_test.hpp>
+
 #include <boost/graph/undirected_graph.hpp>
 #include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
 #include <boost/graph/clustering_coefficient.hpp>
 
 using namespace std;
 using namespace boost;
 
+// number of vertices in the graph
+static const unsigned N = 5;
+
 template <typename Graph>
-void build_graph(Graph& g)
+        struct vertex_vector
 {
-    typedef typename Graph::vertex_descriptor Vertex;
-    typedef typename Graph::edge_descriptor Edge;
+    typedef graph_traits<Graph> traits;
+    typedef vector<typename traits::vertex_descriptor> type;
+};
 
-    static const unsigned N = 5;
-    vector<Vertex> v(N);
-    vector<Edge> e;
+template <typename Graph>
+        void build_graph(Graph& g,
+                         typename vertex_vector<Graph>::type& v)
+{
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 
-    // add some vertices
+    // add vertices
     for(size_t i = 0; i < N; ++i) {
-        // v[i] = add_vertex(g);
         v[i] = add_vertex(g);
     }
 
-    // add some edges (with weights)
+    // add edges
     add_edge(v[0], v[1], g);
     add_edge(v[1], v[2], g);
     add_edge(v[2], v[0], g);
@@ -44,20 +46,53 @@
 };
 
 template <typename Graph>
-void test()
+void test_undirected()
 {
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+    typedef exterior_vertex_property<Graph, float> ClusteringProperty;
+    typedef typename ClusteringProperty::container_type ClusteringContainer;
+    typedef typename ClusteringProperty::map_type ClusteringMap;
+
     Graph g;
-    build_graph(g);
+    vector<Vertex> v(N);
+    build_graph(g, v);
 
-    typename graph_traits<Graph>::vertex_iterator i, end;
-    for(tie(i, end) = vertices(g); i != end; ++i) {
-        unsigned id = get(vertex_index, g, *i);
-        size_t r = vertex_num_routes(g, *i);
-        size_t t = vertex_num_triangles(g, *i);
-        float coef = vertex_clustering_coefficient(g, *i);
-        std::cout << id << " {" << r << " " << t << " " << coef << "}\n";
-    }
-    cerr << "  cc: " << graph_clustering_coefficient(g) << "\n";
+    ClusteringContainer cc(num_vertices(g));
+    ClusteringMap cm(cc, g);
+
+    BOOST_TEST(num_paths_through_vertex(g, v[0]) == 3);
+    BOOST_TEST(num_paths_through_vertex(g, v[1]) == 1);
+    BOOST_TEST(num_paths_through_vertex(g, v[2]) == 1);
+    BOOST_TEST(num_paths_through_vertex(g, v[3]) == 0);
+    BOOST_TEST(num_paths_through_vertex(g, v[4]) == 1);
+
+    BOOST_TEST(num_triangles_on_vertex(g, v[0]) == 1);
+    BOOST_TEST(num_triangles_on_vertex(g, v[1]) == 1);
+    BOOST_TEST(num_triangles_on_vertex(g, v[2]) == 1);
+    BOOST_TEST(num_triangles_on_vertex(g, v[3]) == 0);
+    BOOST_TEST(num_triangles_on_vertex(g, v[4]) == 0);
+
+    BOOST_TEST(clustering_coefficient(g, v[0]) == float(1)/3);
+    BOOST_TEST(clustering_coefficient(g, v[1]) == 1);
+    BOOST_TEST(clustering_coefficient(g, v[2]) == 1);
+    BOOST_TEST(clustering_coefficient(g, v[3]) == 0);
+    BOOST_TEST(clustering_coefficient(g, v[4]) == 0);
+
+    all_clustering_coefficients(g, cm);
+
+    BOOST_TEST(cm[v[0]] == float(1)/3);
+    BOOST_TEST(cm[v[1]] == 1);
+    BOOST_TEST(cm[v[2]] == 1);
+    BOOST_TEST(cm[v[3]] == 0);
+    BOOST_TEST(cm[v[4]] == 0);
+
+    // I would have used check_close, but apparently, that requires
+    // me to link this against a library - which I don't really want
+    // to do. Basically, this makes sure that that coefficient is
+    // within some tolerance (like 1/10 million).
+    float coef = mean_clustering_coefficient(g, cm);
+    BOOST_TEST((coef - (7.0f / 15.0f)) < 1e-7f);
 }
 
 int
@@ -66,9 +101,8 @@
     typedef undirected_graph<> Graph;
     typedef directed_graph<> Digraph;
 
-    std::cout << "*** undirected_graph<> ***\n";
-    test<Graph>();
+    // TODO: write a test for directed clustering coefficient.
 
-    std::cout << "*** directed_graph<> ***\n";
-    test<Digraph>();
+    test_undirected<Graph>();
+    // test<Digraph>();
 }