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>
21 inline typename graph_traits<Graph>::degree_size_type
possible_edges(const Graph & g,std::size_t k,directed_tag)22 possible_edges(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>
30 inline typename graph_traits<Graph>::degree_size_type
possible_edges(const Graph & g,size_t k,undirected_tag)31 possible_edges(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>
39 inline typename graph_traits<Graph>::degree_size_type
count_edges(const Graph & g,typename graph_traits<Graph>::vertex_descriptor u,typename graph_traits<Graph>::vertex_descriptor v,directed_tag)40 count_edges(const Graph& g,
41 typename graph_traits<Graph>::vertex_descriptor u,
42 typename graph_traits<Graph>::vertex_descriptor v,
43 directed_tag)
44
45 {
46 BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> ));
47 return (lookup_edge(u, v, g).second ? 1 : 0) +
48 (lookup_edge(v, u, g).second ? 1 : 0);
49 }
50
51 // This template matches undirectedS
52 template <class Graph>
53 inline typename graph_traits<Graph>::degree_size_type
count_edges(const Graph & g,typename graph_traits<Graph>::vertex_descriptor u,typename graph_traits<Graph>::vertex_descriptor v,undirected_tag)54 count_edges(const Graph& g,
55 typename graph_traits<Graph>::vertex_descriptor u,
56 typename graph_traits<Graph>::vertex_descriptor v,
57 undirected_tag)
58 {
59 BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph> ));
60 return lookup_edge(u, v, g).second ? 1 : 0;
61 }
62 }
63
64 template <typename Graph, typename Vertex>
65 inline typename graph_traits<Graph>::degree_size_type
num_paths_through_vertex(const Graph & g,Vertex v)66 num_paths_through_vertex(const Graph& g, Vertex v)
67 {
68 BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> ));
69 typedef typename graph_traits<Graph>::directed_category Directed;
70 typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
71
72 // TODO: There should actually be a set of neighborhood functions
73 // for things like this (num_neighbors() would be great).
74
75 AdjacencyIterator i, end;
76 boost::tie(i, end) = adjacent_vertices(v, g);
77 std::size_t k = std::distance(i, end);
78 return detail::possible_edges(g, k, Directed());
79 }
80
81 template <typename Graph, typename Vertex>
82 inline typename graph_traits<Graph>::degree_size_type
num_triangles_on_vertex(const Graph & g,Vertex v)83 num_triangles_on_vertex(const Graph& g, Vertex v)
84 {
85 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
86 BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<Graph> ));
87 typedef typename graph_traits<Graph>::degree_size_type Degree;
88 typedef typename graph_traits<Graph>::directed_category Directed;
89 typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
90
91 // TODO: I might be able to reduce the requirement from adjacency graph
92 // to incidence graph by using out edges.
93
94 Degree count(0);
95 AdjacencyIterator i, j, end;
96 for(boost::tie(i, end) = adjacent_vertices(v, g); i != end; ++i) {
97 for(j = boost::next(i); j != end; ++j) {
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>
105 inline T
clustering_coefficient(const Graph & g,Vertex v)106 clustering_coefficient(const Graph& g, Vertex v)
107 {
108 T zero(0);
109 T routes = T(num_paths_through_vertex(g, v));
110 return (routes > zero) ?
111 T(num_triangles_on_vertex(g, v)) / routes : zero;
112 }
113
114 template <typename Graph, typename Vertex>
115 inline double
clustering_coefficient(const Graph & g,Vertex v)116 clustering_coefficient(const Graph& g, Vertex v)
117 { return clustering_coefficient<double>(g, v); }
118
119 template <typename Graph, typename ClusteringMap>
120 inline typename property_traits<ClusteringMap>::value_type
all_clustering_coefficients(const Graph & g,ClusteringMap cm)121 all_clustering_coefficients(const Graph& g, ClusteringMap cm)
122 {
123 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
124 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
125 typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
126 BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ClusteringMap,Vertex> ));
127 typedef typename property_traits<ClusteringMap>::value_type Coefficient;
128
129 Coefficient sum(0);
130 VertexIterator i, end;
131 for(boost::tie(i, end) = vertices(g); i != end; ++i) {
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 cc += get(cm, *i);
153 }
154 return cc / Coefficient(num_vertices(g));
155 }
156
157 } /* namespace boost */
158
159 #endif
160