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
16namespace boost
17{
18namespace detail
19{
20 template <class Graph>
21 inline typename graph_traits<Graph>::degree_size_type
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
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
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
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
64template <typename Graph, typename Vertex>
65inline typename graph_traits<Graph>::degree_size_type
66num_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
81template <typename Graph, typename Vertex>
82inline typename graph_traits<Graph>::degree_size_type
83num_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
104template <typename T, typename Graph, typename Vertex>
105inline T
106clustering_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
114template <typename Graph, typename Vertex>
115inline double
116clustering_coefficient(const Graph& g, Vertex v)
117{ return clustering_coefficient<double>(g, v); }
118
119template <typename Graph, typename ClusteringMap>
120inline typename property_traits<ClusteringMap>::value_type
121all_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
139template <typename Graph, typename ClusteringMap>
140inline typename property_traits<ClusteringMap>::value_type
141mean_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

source code of boost/boost/graph/clustering_coefficient.hpp