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 |
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 | |
64 | template <typename Graph, typename Vertex> |
65 | inline typename graph_traits<Graph>::degree_size_type |
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 |
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 |
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 |
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 |
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 |
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 | |