]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2004 The Trustees of Indiana University. |
2 | ||
3 | // Distributed under the Boost Software License, Version 1.0. | |
4 | // (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
9 | #ifndef BOOST_GRAPH_BETWEENNESS_CENTRALITY_CLUSTERING_HPP | |
10 | #define BOOST_GRAPH_BETWEENNESS_CENTRALITY_CLUSTERING_HPP | |
11 | ||
12 | #include <boost/graph/betweenness_centrality.hpp> | |
13 | #include <boost/graph/graph_traits.hpp> | |
14 | #include <boost/graph/graph_utility.hpp> | |
15 | #include <boost/pending/indirect_cmp.hpp> | |
16 | #include <algorithm> | |
17 | #include <vector> | |
18 | #include <boost/property_map/property_map.hpp> | |
19 | ||
20 | namespace boost { | |
21 | ||
22 | /** Threshold termination function for the betweenness centrality | |
23 | * clustering algorithm. | |
24 | */ | |
25 | template<typename T> | |
26 | struct bc_clustering_threshold | |
27 | { | |
28 | typedef T centrality_type; | |
29 | ||
30 | /// Terminate clustering when maximum absolute edge centrality is | |
31 | /// below the given threshold. | |
32 | explicit bc_clustering_threshold(T threshold) | |
33 | : threshold(threshold), dividend(1.0) {} | |
34 | ||
35 | /** | |
36 | * Terminate clustering when the maximum edge centrality is below | |
37 | * the given threshold. | |
38 | * | |
39 | * @param threshold the threshold value | |
40 | * | |
41 | * @param g the graph on which the threshold will be calculated | |
42 | * | |
43 | * @param normalize when true, the threshold is compared against the | |
44 | * normalized edge centrality based on the input graph; otherwise, | |
45 | * the threshold is compared against the absolute edge centrality. | |
46 | */ | |
47 | template<typename Graph> | |
48 | bc_clustering_threshold(T threshold, const Graph& g, bool normalize = true) | |
49 | : threshold(threshold), dividend(1.0) | |
50 | { | |
51 | if (normalize) { | |
52 | typename graph_traits<Graph>::vertices_size_type n = num_vertices(g); | |
53 | dividend = T((n - 1) * (n - 2)) / T(2); | |
54 | } | |
55 | } | |
56 | ||
57 | /** Returns true when the given maximum edge centrality (potentially | |
58 | * normalized) falls below the threshold. | |
59 | */ | |
60 | template<typename Graph, typename Edge> | |
61 | bool operator()(T max_centrality, Edge, const Graph&) | |
62 | { | |
63 | return (max_centrality / dividend) < threshold; | |
64 | } | |
65 | ||
66 | protected: | |
67 | T threshold; | |
68 | T dividend; | |
69 | }; | |
70 | ||
71 | /** Graph clustering based on edge betweenness centrality. | |
72 | * | |
73 | * This algorithm implements graph clustering based on edge | |
74 | * betweenness centrality. It is an iterative algorithm, where in each | |
75 | * step it compute the edge betweenness centrality (via @ref | |
76 | * brandes_betweenness_centrality) and removes the edge with the | |
77 | * maximum betweenness centrality. The @p done function object | |
78 | * determines when the algorithm terminates (the edge found when the | |
79 | * algorithm terminates will not be removed). | |
80 | * | |
81 | * @param g The graph on which clustering will be performed. The type | |
82 | * of this parameter (@c MutableGraph) must be a model of the | |
83 | * VertexListGraph, IncidenceGraph, EdgeListGraph, and Mutable Graph | |
84 | * concepts. | |
85 | * | |
86 | * @param done The function object that indicates termination of the | |
87 | * algorithm. It must be a ternary function object thats accepts the | |
88 | * maximum centrality, the descriptor of the edge that will be | |
89 | * removed, and the graph @p g. | |
90 | * | |
91 | * @param edge_centrality (UTIL/OUT) The property map that will store | |
92 | * the betweenness centrality for each edge. When the algorithm | |
93 | * terminates, it will contain the edge centralities for the | |
94 | * graph. The type of this property map must model the | |
95 | * ReadWritePropertyMap concept. Defaults to an @c | |
96 | * iterator_property_map whose value type is | |
97 | * @c Done::centrality_type and using @c get(edge_index, g) for the | |
98 | * index map. | |
99 | * | |
100 | * @param vertex_index (IN) The property map that maps vertices to | |
101 | * indices in the range @c [0, num_vertices(g)). This type of this | |
102 | * property map must model the ReadablePropertyMap concept and its | |
103 | * value type must be an integral type. Defaults to | |
104 | * @c get(vertex_index, g). | |
105 | */ | |
106 | template<typename MutableGraph, typename Done, typename EdgeCentralityMap, | |
107 | typename VertexIndexMap> | |
108 | void | |
109 | betweenness_centrality_clustering(MutableGraph& g, Done done, | |
110 | EdgeCentralityMap edge_centrality, | |
111 | VertexIndexMap vertex_index) | |
112 | { | |
113 | typedef typename property_traits<EdgeCentralityMap>::value_type | |
114 | centrality_type; | |
115 | typedef typename graph_traits<MutableGraph>::edge_iterator edge_iterator; | |
116 | typedef typename graph_traits<MutableGraph>::edge_descriptor edge_descriptor; | |
117 | ||
118 | if (has_no_edges(g)) return; | |
119 | ||
120 | // Function object that compares the centrality of edges | |
121 | indirect_cmp<EdgeCentralityMap, std::less<centrality_type> > | |
122 | cmp(edge_centrality); | |
123 | ||
124 | bool is_done; | |
125 | do { | |
126 | brandes_betweenness_centrality(g, | |
127 | edge_centrality_map(edge_centrality) | |
128 | .vertex_index_map(vertex_index)); | |
129 | std::pair<edge_iterator, edge_iterator> edges_iters = edges(g); | |
130 | edge_descriptor e = *max_element(edges_iters.first, edges_iters.second, cmp); | |
131 | is_done = done(get(edge_centrality, e), e, g); | |
132 | if (!is_done) remove_edge(e, g); | |
133 | } while (!is_done && !has_no_edges(g)); | |
134 | } | |
135 | ||
136 | /** | |
137 | * \overload | |
138 | */ | |
139 | template<typename MutableGraph, typename Done, typename EdgeCentralityMap> | |
140 | void | |
141 | betweenness_centrality_clustering(MutableGraph& g, Done done, | |
142 | EdgeCentralityMap edge_centrality) | |
143 | { | |
144 | betweenness_centrality_clustering(g, done, edge_centrality, | |
145 | get(vertex_index, g)); | |
146 | } | |
147 | ||
148 | /** | |
149 | * \overload | |
150 | */ | |
151 | template<typename MutableGraph, typename Done> | |
152 | void | |
153 | betweenness_centrality_clustering(MutableGraph& g, Done done) | |
154 | { | |
155 | typedef typename Done::centrality_type centrality_type; | |
156 | std::vector<centrality_type> edge_centrality(num_edges(g)); | |
157 | betweenness_centrality_clustering(g, done, | |
158 | make_iterator_property_map(edge_centrality.begin(), get(edge_index, g)), | |
159 | get(vertex_index, g)); | |
160 | } | |
161 | ||
162 | } // end namespace boost | |
163 | ||
164 | #endif // BOOST_GRAPH_BETWEENNESS_CENTRALITY_CLUSTERING_HPP |