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 #ifndef BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
8 #define BOOST_GRAPH_CLUSTERING_COEFFICIENT_HPP
9
10 #include <boost/next_prior.hpp>
11 #include <boost/graph/graph_traits.hpp>
12 #include <boost/graph/graph_concepts.hpp>
13 #include <boost/graph/lookup_edge.hpp>
14 #include <boost/concept/assert.hpp>
15
16 namespace boost
17 {
18 namespace detail
19 {
20 template < class Graph >
possible_edges(const Graph & g,std::size_t k,directed_tag)21 inline typename graph_traits< Graph >::degree_size_type possible_edges(
22 const Graph& g, std::size_t k, directed_tag)
23 {
24 BOOST_CONCEPT_ASSERT((GraphConcept< Graph >));
25 typedef typename graph_traits< Graph >::degree_size_type T;
26 return T(k) * (T(k) - 1);
27 }
28
29 template < class Graph >
possible_edges(const Graph & g,size_t k,undirected_tag)30 inline typename graph_traits< Graph >::degree_size_type possible_edges(
31 const Graph& g, size_t k, undirected_tag)
32 {
33 // dirty little trick...
34 return possible_edges(g, k, directed_tag()) / 2;
35 }
36
37 // This template matches directedS and bidirectionalS.
38 template < class Graph >
count_edges(const Graph & g,typename graph_traits<Graph>::vertex_descriptor u,typename graph_traits<Graph>::vertex_descriptor v,directed_tag)39 inline typename graph_traits< Graph >::degree_size_type count_edges(
40 const Graph& g, typename graph_traits< Graph >::vertex_descriptor u,
41 typename graph_traits< Graph >::vertex_descriptor v, directed_tag)
42
43 {
44 BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< Graph >));
45 return (lookup_edge(u, v, g).second ? 1 : 0)
46 + (lookup_edge(v, u, g).second ? 1 : 0);
47 }
48
49 // This template matches undirectedS
50 template < class Graph >
count_edges(const Graph & g,typename graph_traits<Graph>::vertex_descriptor u,typename graph_traits<Graph>::vertex_descriptor v,undirected_tag)51 inline typename graph_traits< Graph >::degree_size_type count_edges(
52 const Graph& g, typename graph_traits< Graph >::vertex_descriptor u,
53 typename graph_traits< Graph >::vertex_descriptor v, undirected_tag)
54 {
55 BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< Graph >));
56 return lookup_edge(u, v, g).second ? 1 : 0;
57 }
58 }
59
60 template < typename Graph, typename Vertex >
61 inline typename graph_traits< Graph >::degree_size_type
num_paths_through_vertex(const Graph & g,Vertex v)62 num_paths_through_vertex(const Graph& g, Vertex v)
63 {
64 BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept< Graph >));
65 typedef typename graph_traits< Graph >::directed_category Directed;
66 typedef
67 typename graph_traits< Graph >::adjacency_iterator AdjacencyIterator;
68
69 // TODO: There should actually be a set of neighborhood functions
70 // for things like this (num_neighbors() would be great).
71
72 AdjacencyIterator i, end;
73 boost::tie(i, end) = adjacent_vertices(v, g);
74 std::size_t k = std::distance(i, end);
75 return detail::possible_edges(g, k, Directed());
76 }
77
78 template < typename Graph, typename Vertex >
num_triangles_on_vertex(const Graph & g,Vertex v)79 inline typename graph_traits< Graph >::degree_size_type num_triangles_on_vertex(
80 const Graph& g, Vertex v)
81 {
82 BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >));
83 BOOST_CONCEPT_ASSERT((AdjacencyGraphConcept< Graph >));
84 typedef typename graph_traits< Graph >::degree_size_type Degree;
85 typedef typename graph_traits< Graph >::directed_category Directed;
86 typedef
87 typename graph_traits< Graph >::adjacency_iterator AdjacencyIterator;
88
89 // TODO: I might be able to reduce the requirement from adjacency graph
90 // to incidence graph by using out edges.
91
92 Degree count(0);
93 AdjacencyIterator i, j, end;
94 for (boost::tie(i, end) = adjacent_vertices(v, g); i != end; ++i)
95 {
96 for (j = boost::next(i); j != end; ++j)
97 {
98 count += detail::count_edges(g, *i, *j, Directed());
99 }
100 }
101 return count;
102 } /* namespace detail */
103
104 template < typename T, typename Graph, typename Vertex >
clustering_coefficient(const Graph & g,Vertex v)105 inline T clustering_coefficient(const Graph& g, Vertex v)
106 {
107 T zero(0);
108 T routes = T(num_paths_through_vertex(g, v));
109 return (routes > zero) ? T(num_triangles_on_vertex(g, v)) / routes : zero;
110 }
111
112 template < typename Graph, typename Vertex >
clustering_coefficient(const Graph & g,Vertex v)113 inline double clustering_coefficient(const Graph& g, Vertex v)
114 {
115 return clustering_coefficient< double >(g, v);
116 }
117
118 template < typename Graph, typename ClusteringMap >
119 inline typename property_traits< ClusteringMap >::value_type
all_clustering_coefficients(const Graph & g,ClusteringMap cm)120 all_clustering_coefficients(const Graph& g, ClusteringMap cm)
121 {
122 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
123 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
124 typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
125 BOOST_CONCEPT_ASSERT((WritablePropertyMapConcept< ClusteringMap, Vertex >));
126 typedef typename property_traits< ClusteringMap >::value_type Coefficient;
127
128 Coefficient sum(0);
129 VertexIterator i, end;
130 for (boost::tie(i, end) = vertices(g); i != end; ++i)
131 {
132 Coefficient cc = clustering_coefficient< Coefficient >(g, *i);
133 put(cm, *i, cc);
134 sum += cc;
135 }
136 return sum / Coefficient(num_vertices(g));
137 }
138
139 template < typename Graph, typename ClusteringMap >
140 inline typename property_traits< ClusteringMap >::value_type
mean_clustering_coefficient(const Graph & g,ClusteringMap cm)141 mean_clustering_coefficient(const Graph& g, ClusteringMap cm)
142 {
143 BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
144 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
145 typedef typename graph_traits< Graph >::vertex_iterator VertexIterator;
146 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< ClusteringMap, Vertex >));
147 typedef typename property_traits< ClusteringMap >::value_type Coefficient;
148
149 Coefficient cc(0);
150 VertexIterator i, end;
151 for (boost::tie(i, end) = vertices(g); i != end; ++i)
152 {
153 cc += get(cm, *i);
154 }
155 return cc / Coefficient(num_vertices(g));
156 }
157
158 } /* namespace boost */
159
160 #endif
161