]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |