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