|
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_BRANDES_BETWEENNESS_CENTRALITY_HPP |
|
10 #define BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP |
|
11 |
|
12 #include <stack> |
|
13 #include <vector> |
|
14 #include <boost/graph/dijkstra_shortest_paths.hpp> |
|
15 #include <boost/graph/breadth_first_search.hpp> |
|
16 #include <boost/graph/relax.hpp> |
|
17 #include <boost/graph/graph_traits.hpp> |
|
18 #include <boost/tuple/tuple.hpp> |
|
19 #include <boost/type_traits/is_convertible.hpp> |
|
20 #include <boost/type_traits/is_same.hpp> |
|
21 #include <boost/mpl/if.hpp> |
|
22 #include <boost/property_map.hpp> |
|
23 #include <boost/graph/named_function_params.hpp> |
|
24 #include <algorithm> |
|
25 |
|
26 namespace boost { |
|
27 |
|
28 namespace detail { namespace graph { |
|
29 |
|
30 /** |
|
31 * Customized visitor passed to Dijkstra's algorithm by Brandes' |
|
32 * betweenness centrality algorithm. This visitor is responsible for |
|
33 * keeping track of the order in which vertices are discovered, the |
|
34 * predecessors on the shortest path(s) to a vertex, and the number |
|
35 * of shortest paths. |
|
36 */ |
|
37 template<typename Graph, typename WeightMap, typename IncomingMap, |
|
38 typename DistanceMap, typename PathCountMap> |
|
39 struct brandes_dijkstra_visitor : public bfs_visitor<> |
|
40 { |
|
41 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
|
42 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
|
43 |
|
44 brandes_dijkstra_visitor(std::stack<vertex_descriptor>& ordered_vertices, |
|
45 WeightMap weight, |
|
46 IncomingMap incoming, |
|
47 DistanceMap distance, |
|
48 PathCountMap path_count) |
|
49 : ordered_vertices(ordered_vertices), weight(weight), |
|
50 incoming(incoming), distance(distance), |
|
51 path_count(path_count) |
|
52 { } |
|
53 |
|
54 /** |
|
55 * Whenever an edge e = (v, w) is relaxed, the incoming edge list |
|
56 * for w is set to {(v, w)} and the shortest path count of w is set to |
|
57 * the number of paths that reach {v}. |
|
58 */ |
|
59 void edge_relaxed(edge_descriptor e, const Graph& g) |
|
60 { |
|
61 vertex_descriptor v = source(e, g), w = target(e, g); |
|
62 incoming[w].clear(); |
|
63 incoming[w].push_back(e); |
|
64 put(path_count, w, get(path_count, v)); |
|
65 } |
|
66 |
|
67 /** |
|
68 * If an edge e = (v, w) was not relaxed, it may still be the case |
|
69 * that we've found more equally-short paths, so include {(v, w)} in the |
|
70 * incoming edges of w and add all of the shortest paths to v to the |
|
71 * shortest path count of w. |
|
72 */ |
|
73 void edge_not_relaxed(edge_descriptor e, const Graph& g) |
|
74 { |
|
75 typedef typename property_traits<WeightMap>::value_type weight_type; |
|
76 typedef typename property_traits<DistanceMap>::value_type distance_type; |
|
77 vertex_descriptor v = source(e, g), w = target(e, g); |
|
78 distance_type d_v = get(distance, v), d_w = get(distance, w); |
|
79 weight_type w_e = get(weight, e); |
|
80 |
|
81 closed_plus<distance_type> combine; |
|
82 if (d_w == combine(d_v, w_e)) { |
|
83 put(path_count, w, get(path_count, w) + get(path_count, v)); |
|
84 incoming[w].push_back(e); |
|
85 } |
|
86 } |
|
87 |
|
88 /// Keep track of vertices as they are reached |
|
89 void examine_vertex(vertex_descriptor w, const Graph&) |
|
90 { |
|
91 ordered_vertices.push(w); |
|
92 } |
|
93 |
|
94 private: |
|
95 std::stack<vertex_descriptor>& ordered_vertices; |
|
96 WeightMap weight; |
|
97 IncomingMap incoming; |
|
98 DistanceMap distance; |
|
99 PathCountMap path_count; |
|
100 }; |
|
101 |
|
102 /** |
|
103 * Function object that calls Dijkstra's shortest paths algorithm |
|
104 * using the Dijkstra visitor for the Brandes betweenness centrality |
|
105 * algorithm. |
|
106 */ |
|
107 template<typename WeightMap> |
|
108 struct brandes_dijkstra_shortest_paths |
|
109 { |
|
110 brandes_dijkstra_shortest_paths(WeightMap weight_map) |
|
111 : weight_map(weight_map) { } |
|
112 |
|
113 template<typename Graph, typename IncomingMap, typename DistanceMap, |
|
114 typename PathCountMap, typename VertexIndexMap> |
|
115 void |
|
116 operator()(Graph& g, |
|
117 typename graph_traits<Graph>::vertex_descriptor s, |
|
118 std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov, |
|
119 IncomingMap incoming, |
|
120 DistanceMap distance, |
|
121 PathCountMap path_count, |
|
122 VertexIndexMap vertex_index) |
|
123 { |
|
124 typedef brandes_dijkstra_visitor<Graph, WeightMap, IncomingMap, |
|
125 DistanceMap, PathCountMap> visitor_type; |
|
126 visitor_type visitor(ov, weight_map, incoming, distance, path_count); |
|
127 |
|
128 dijkstra_shortest_paths(g, s, |
|
129 boost::weight_map(weight_map) |
|
130 .vertex_index_map(vertex_index) |
|
131 .distance_map(distance) |
|
132 .visitor(visitor)); |
|
133 } |
|
134 |
|
135 private: |
|
136 WeightMap weight_map; |
|
137 }; |
|
138 |
|
139 /** |
|
140 * Function object that invokes breadth-first search for the |
|
141 * unweighted form of the Brandes betweenness centrality algorithm. |
|
142 */ |
|
143 struct brandes_unweighted_shortest_paths |
|
144 { |
|
145 /** |
|
146 * Customized visitor passed to breadth-first search, which |
|
147 * records predecessor and the number of shortest paths to each |
|
148 * vertex. |
|
149 */ |
|
150 template<typename Graph, typename IncomingMap, typename DistanceMap, |
|
151 typename PathCountMap> |
|
152 struct visitor_type : public bfs_visitor<> |
|
153 { |
|
154 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
|
155 typedef typename graph_traits<Graph>::vertex_descriptor |
|
156 vertex_descriptor; |
|
157 |
|
158 visitor_type(IncomingMap incoming, DistanceMap distance, |
|
159 PathCountMap path_count, |
|
160 std::stack<vertex_descriptor>& ordered_vertices) |
|
161 : incoming(incoming), distance(distance), |
|
162 path_count(path_count), ordered_vertices(ordered_vertices) { } |
|
163 |
|
164 /// Keep track of vertices as they are reached |
|
165 void examine_vertex(vertex_descriptor v, Graph&) |
|
166 { |
|
167 ordered_vertices.push(v); |
|
168 } |
|
169 |
|
170 /** |
|
171 * Whenever an edge e = (v, w) is labelled a tree edge, the |
|
172 * incoming edge list for w is set to {(v, w)} and the shortest |
|
173 * path count of w is set to the number of paths that reach {v}. |
|
174 */ |
|
175 void tree_edge(edge_descriptor e, Graph& g) |
|
176 { |
|
177 vertex_descriptor v = source(e, g); |
|
178 vertex_descriptor w = target(e, g); |
|
179 put(distance, w, get(distance, v) + 1); |
|
180 |
|
181 put(path_count, w, get(path_count, v)); |
|
182 incoming[w].push_back(e); |
|
183 } |
|
184 |
|
185 /** |
|
186 * If an edge e = (v, w) is not a tree edge, it may still be the |
|
187 * case that we've found more equally-short paths, so include (v, w) |
|
188 * in the incoming edge list of w and add all of the shortest |
|
189 * paths to v to the shortest path count of w. |
|
190 */ |
|
191 void non_tree_edge(edge_descriptor e, Graph& g) |
|
192 { |
|
193 vertex_descriptor v = source(e, g); |
|
194 vertex_descriptor w = target(e, g); |
|
195 if (get(distance, w) == get(distance, v) + 1) { |
|
196 put(path_count, w, get(path_count, w) + get(path_count, v)); |
|
197 incoming[w].push_back(e); |
|
198 } |
|
199 } |
|
200 |
|
201 private: |
|
202 IncomingMap incoming; |
|
203 DistanceMap distance; |
|
204 PathCountMap path_count; |
|
205 std::stack<vertex_descriptor>& ordered_vertices; |
|
206 }; |
|
207 |
|
208 template<typename Graph, typename IncomingMap, typename DistanceMap, |
|
209 typename PathCountMap, typename VertexIndexMap> |
|
210 void |
|
211 operator()(Graph& g, |
|
212 typename graph_traits<Graph>::vertex_descriptor s, |
|
213 std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov, |
|
214 IncomingMap incoming, |
|
215 DistanceMap distance, |
|
216 PathCountMap path_count, |
|
217 VertexIndexMap vertex_index) |
|
218 { |
|
219 typedef typename graph_traits<Graph>::vertex_descriptor |
|
220 vertex_descriptor; |
|
221 |
|
222 visitor_type<Graph, IncomingMap, DistanceMap, PathCountMap> |
|
223 visitor(incoming, distance, path_count, ov); |
|
224 |
|
225 std::vector<default_color_type> |
|
226 colors(num_vertices(g), color_traits<default_color_type>::white()); |
|
227 boost::queue<vertex_descriptor> Q; |
|
228 breadth_first_visit(g, s, Q, visitor, |
|
229 make_iterator_property_map(colors.begin(), |
|
230 vertex_index)); |
|
231 } |
|
232 }; |
|
233 |
|
234 // When the edge centrality map is a dummy property map, no |
|
235 // initialization is needed. |
|
236 template<typename Iter> |
|
237 inline void |
|
238 init_centrality_map(std::pair<Iter, Iter>, dummy_property_map) { } |
|
239 |
|
240 // When we have a real edge centrality map, initialize all of the |
|
241 // centralities to zero. |
|
242 template<typename Iter, typename Centrality> |
|
243 void |
|
244 init_centrality_map(std::pair<Iter, Iter> keys, Centrality centrality_map) |
|
245 { |
|
246 typedef typename property_traits<Centrality>::value_type |
|
247 centrality_type; |
|
248 while (keys.first != keys.second) { |
|
249 put(centrality_map, *keys.first, centrality_type(0)); |
|
250 ++keys.first; |
|
251 } |
|
252 } |
|
253 |
|
254 // When the edge centrality map is a dummy property map, no update |
|
255 // is performed. |
|
256 template<typename Key, typename T> |
|
257 inline void |
|
258 update_centrality(dummy_property_map, const Key&, const T&) { } |
|
259 |
|
260 // When we have a real edge centrality map, add the value to the map |
|
261 template<typename CentralityMap, typename Key, typename T> |
|
262 inline void |
|
263 update_centrality(CentralityMap centrality_map, Key k, const T& x) |
|
264 { put(centrality_map, k, get(centrality_map, k) + x); } |
|
265 |
|
266 template<typename Iter> |
|
267 inline void |
|
268 divide_centrality_by_two(std::pair<Iter, Iter>, dummy_property_map) {} |
|
269 |
|
270 template<typename Iter, typename CentralityMap> |
|
271 inline void |
|
272 divide_centrality_by_two(std::pair<Iter, Iter> keys, |
|
273 CentralityMap centrality_map) |
|
274 { |
|
275 typename property_traits<CentralityMap>::value_type two(2); |
|
276 while (keys.first != keys.second) { |
|
277 put(centrality_map, *keys.first, get(centrality_map, *keys.first) / two); |
|
278 ++keys.first; |
|
279 } |
|
280 } |
|
281 |
|
282 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
|
283 typename IncomingMap, typename DistanceMap, |
|
284 typename DependencyMap, typename PathCountMap, |
|
285 typename VertexIndexMap, typename ShortestPaths> |
|
286 void |
|
287 brandes_betweenness_centrality_impl(const Graph& g, |
|
288 CentralityMap centrality, // C_B |
|
289 EdgeCentralityMap edge_centrality_map, |
|
290 IncomingMap incoming, // P |
|
291 DistanceMap distance, // d |
|
292 DependencyMap dependency, // delta |
|
293 PathCountMap path_count, // sigma |
|
294 VertexIndexMap vertex_index, |
|
295 ShortestPaths shortest_paths) |
|
296 { |
|
297 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; |
|
298 typedef typename graph_traits<Graph>::edge_iterator edge_iterator; |
|
299 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
|
300 |
|
301 // Initialize centrality |
|
302 init_centrality_map(vertices(g), centrality); |
|
303 init_centrality_map(edges(g), edge_centrality_map); |
|
304 |
|
305 std::stack<vertex_descriptor> ordered_vertices; |
|
306 vertex_iterator s, s_end; |
|
307 for (tie(s, s_end) = vertices(g); s != s_end; ++s) { |
|
308 // Initialize for this iteration |
|
309 vertex_iterator w, w_end; |
|
310 for (tie(w, w_end) = vertices(g); w != w_end; ++w) { |
|
311 incoming[*w].clear(); |
|
312 put(path_count, *w, 0); |
|
313 put(dependency, *w, 0); |
|
314 } |
|
315 put(path_count, *s, 1); |
|
316 |
|
317 // Execute the shortest paths algorithm. This will be either |
|
318 // Dijkstra's algorithm or a customized breadth-first search, |
|
319 // depending on whether the graph is weighted or unweighted. |
|
320 shortest_paths(g, *s, ordered_vertices, incoming, distance, |
|
321 path_count, vertex_index); |
|
322 |
|
323 while (!ordered_vertices.empty()) { |
|
324 vertex_descriptor w = ordered_vertices.top(); |
|
325 ordered_vertices.pop(); |
|
326 |
|
327 typedef typename property_traits<IncomingMap>::value_type |
|
328 incoming_type; |
|
329 typedef typename incoming_type::iterator incoming_iterator; |
|
330 typedef typename property_traits<DependencyMap>::value_type |
|
331 dependency_type; |
|
332 |
|
333 for (incoming_iterator vw = incoming[w].begin(); |
|
334 vw != incoming[w].end(); ++vw) { |
|
335 vertex_descriptor v = source(*vw, g); |
|
336 dependency_type factor = dependency_type(get(path_count, v)) |
|
337 / dependency_type(get(path_count, w)); |
|
338 factor *= (dependency_type(1) + get(dependency, w)); |
|
339 put(dependency, v, get(dependency, v) + factor); |
|
340 update_centrality(edge_centrality_map, *vw, factor); |
|
341 } |
|
342 |
|
343 if (w != *s) { |
|
344 update_centrality(centrality, w, get(dependency, w)); |
|
345 } |
|
346 } |
|
347 } |
|
348 |
|
349 typedef typename graph_traits<Graph>::directed_category directed_category; |
|
350 const bool is_undirected = |
|
351 is_convertible<directed_category*, undirected_tag*>::value; |
|
352 if (is_undirected) { |
|
353 divide_centrality_by_two(vertices(g), centrality); |
|
354 divide_centrality_by_two(edges(g), edge_centrality_map); |
|
355 } |
|
356 } |
|
357 |
|
358 } } // end namespace detail::graph |
|
359 |
|
360 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
|
361 typename IncomingMap, typename DistanceMap, |
|
362 typename DependencyMap, typename PathCountMap, |
|
363 typename VertexIndexMap> |
|
364 void |
|
365 brandes_betweenness_centrality(const Graph& g, |
|
366 CentralityMap centrality, // C_B |
|
367 EdgeCentralityMap edge_centrality_map, |
|
368 IncomingMap incoming, // P |
|
369 DistanceMap distance, // d |
|
370 DependencyMap dependency, // delta |
|
371 PathCountMap path_count, // sigma |
|
372 VertexIndexMap vertex_index) |
|
373 { |
|
374 detail::graph::brandes_unweighted_shortest_paths shortest_paths; |
|
375 |
|
376 detail::graph::brandes_betweenness_centrality_impl(g, centrality, |
|
377 edge_centrality_map, |
|
378 incoming, distance, |
|
379 dependency, path_count, |
|
380 vertex_index, |
|
381 shortest_paths); |
|
382 } |
|
383 |
|
384 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
|
385 typename IncomingMap, typename DistanceMap, |
|
386 typename DependencyMap, typename PathCountMap, |
|
387 typename VertexIndexMap, typename WeightMap> |
|
388 void |
|
389 brandes_betweenness_centrality(const Graph& g, |
|
390 CentralityMap centrality, // C_B |
|
391 EdgeCentralityMap edge_centrality_map, |
|
392 IncomingMap incoming, // P |
|
393 DistanceMap distance, // d |
|
394 DependencyMap dependency, // delta |
|
395 PathCountMap path_count, // sigma |
|
396 VertexIndexMap vertex_index, |
|
397 WeightMap weight_map) |
|
398 { |
|
399 detail::graph::brandes_dijkstra_shortest_paths<WeightMap> |
|
400 shortest_paths(weight_map); |
|
401 |
|
402 detail::graph::brandes_betweenness_centrality_impl(g, centrality, |
|
403 edge_centrality_map, |
|
404 incoming, distance, |
|
405 dependency, path_count, |
|
406 vertex_index, |
|
407 shortest_paths); |
|
408 } |
|
409 |
|
410 namespace detail { namespace graph { |
|
411 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
|
412 typename WeightMap, typename VertexIndexMap> |
|
413 void |
|
414 brandes_betweenness_centrality_dispatch2(const Graph& g, |
|
415 CentralityMap centrality, |
|
416 EdgeCentralityMap edge_centrality_map, |
|
417 WeightMap weight_map, |
|
418 VertexIndexMap vertex_index) |
|
419 { |
|
420 typedef typename graph_traits<Graph>::degree_size_type degree_size_type; |
|
421 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
|
422 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
|
423 typedef typename mpl::if_c<(is_same<CentralityMap, |
|
424 dummy_property_map>::value), |
|
425 EdgeCentralityMap, |
|
426 CentralityMap>::type a_centrality_map; |
|
427 typedef typename property_traits<a_centrality_map>::value_type |
|
428 centrality_type; |
|
429 |
|
430 typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); |
|
431 |
|
432 std::vector<std::vector<edge_descriptor> > incoming(V); |
|
433 std::vector<centrality_type> distance(V); |
|
434 std::vector<centrality_type> dependency(V); |
|
435 std::vector<degree_size_type> path_count(V); |
|
436 |
|
437 brandes_betweenness_centrality( |
|
438 g, centrality, edge_centrality_map, |
|
439 make_iterator_property_map(incoming.begin(), vertex_index), |
|
440 make_iterator_property_map(distance.begin(), vertex_index), |
|
441 make_iterator_property_map(dependency.begin(), vertex_index), |
|
442 make_iterator_property_map(path_count.begin(), vertex_index), |
|
443 vertex_index, |
|
444 weight_map); |
|
445 } |
|
446 |
|
447 |
|
448 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
|
449 typename VertexIndexMap> |
|
450 void |
|
451 brandes_betweenness_centrality_dispatch2(const Graph& g, |
|
452 CentralityMap centrality, |
|
453 EdgeCentralityMap edge_centrality_map, |
|
454 VertexIndexMap vertex_index) |
|
455 { |
|
456 typedef typename graph_traits<Graph>::degree_size_type degree_size_type; |
|
457 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
|
458 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
|
459 typedef typename mpl::if_c<(is_same<CentralityMap, |
|
460 dummy_property_map>::value), |
|
461 EdgeCentralityMap, |
|
462 CentralityMap>::type a_centrality_map; |
|
463 typedef typename property_traits<a_centrality_map>::value_type |
|
464 centrality_type; |
|
465 |
|
466 typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); |
|
467 |
|
468 std::vector<std::vector<edge_descriptor> > incoming(V); |
|
469 std::vector<centrality_type> distance(V); |
|
470 std::vector<centrality_type> dependency(V); |
|
471 std::vector<degree_size_type> path_count(V); |
|
472 |
|
473 brandes_betweenness_centrality( |
|
474 g, centrality, edge_centrality_map, |
|
475 make_iterator_property_map(incoming.begin(), vertex_index), |
|
476 make_iterator_property_map(distance.begin(), vertex_index), |
|
477 make_iterator_property_map(dependency.begin(), vertex_index), |
|
478 make_iterator_property_map(path_count.begin(), vertex_index), |
|
479 vertex_index); |
|
480 } |
|
481 |
|
482 template<typename WeightMap> |
|
483 struct brandes_betweenness_centrality_dispatch1 |
|
484 { |
|
485 template<typename Graph, typename CentralityMap, |
|
486 typename EdgeCentralityMap, typename VertexIndexMap> |
|
487 static void |
|
488 run(const Graph& g, CentralityMap centrality, |
|
489 EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
|
490 WeightMap weight_map) |
|
491 { |
|
492 brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map, |
|
493 weight_map, vertex_index); |
|
494 } |
|
495 }; |
|
496 |
|
497 template<> |
|
498 struct brandes_betweenness_centrality_dispatch1<error_property_not_found> |
|
499 { |
|
500 template<typename Graph, typename CentralityMap, |
|
501 typename EdgeCentralityMap, typename VertexIndexMap> |
|
502 static void |
|
503 run(const Graph& g, CentralityMap centrality, |
|
504 EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
|
505 error_property_not_found) |
|
506 { |
|
507 brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map, |
|
508 vertex_index); |
|
509 } |
|
510 }; |
|
511 |
|
512 } } // end namespace detail::graph |
|
513 |
|
514 template<typename Graph, typename Param, typename Tag, typename Rest> |
|
515 void |
|
516 brandes_betweenness_centrality(const Graph& g, |
|
517 const bgl_named_params<Param,Tag,Rest>& params) |
|
518 { |
|
519 typedef bgl_named_params<Param,Tag,Rest> named_params; |
|
520 |
|
521 typedef typename property_value<named_params, edge_weight_t>::type ew; |
|
522 detail::graph::brandes_betweenness_centrality_dispatch1<ew>::run( |
|
523 g, |
|
524 choose_param(get_param(params, vertex_centrality), |
|
525 dummy_property_map()), |
|
526 choose_param(get_param(params, edge_centrality), |
|
527 dummy_property_map()), |
|
528 choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
|
529 get_param(params, edge_weight)); |
|
530 } |
|
531 |
|
532 template<typename Graph, typename CentralityMap> |
|
533 void |
|
534 brandes_betweenness_centrality(const Graph& g, CentralityMap centrality) |
|
535 { |
|
536 detail::graph::brandes_betweenness_centrality_dispatch2( |
|
537 g, centrality, dummy_property_map(), get(vertex_index, g)); |
|
538 } |
|
539 |
|
540 template<typename Graph, typename CentralityMap, typename EdgeCentralityMap> |
|
541 void |
|
542 brandes_betweenness_centrality(const Graph& g, CentralityMap centrality, |
|
543 EdgeCentralityMap edge_centrality_map) |
|
544 { |
|
545 detail::graph::brandes_betweenness_centrality_dispatch2( |
|
546 g, centrality, edge_centrality_map, get(vertex_index, g)); |
|
547 } |
|
548 |
|
549 /** |
|
550 * Converts "absolute" betweenness centrality (as computed by the |
|
551 * brandes_betweenness_centrality algorithm) in the centrality map |
|
552 * into "relative" centrality. The result is placed back into the |
|
553 * given centrality map. |
|
554 */ |
|
555 template<typename Graph, typename CentralityMap> |
|
556 void |
|
557 relative_betweenness_centrality(const Graph& g, CentralityMap centrality) |
|
558 { |
|
559 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; |
|
560 typedef typename property_traits<CentralityMap>::value_type centrality_type; |
|
561 |
|
562 typename graph_traits<Graph>::vertices_size_type n = num_vertices(g); |
|
563 centrality_type factor = centrality_type(2)/centrality_type(n*n - 3*n + 2); |
|
564 vertex_iterator v, v_end; |
|
565 for (tie(v, v_end) = vertices(g); v != v_end; ++v) { |
|
566 put(centrality, *v, factor * get(centrality, *v)); |
|
567 } |
|
568 } |
|
569 |
|
570 // Compute the central point dominance of a graph. |
|
571 template<typename Graph, typename CentralityMap> |
|
572 typename property_traits<CentralityMap>::value_type |
|
573 central_point_dominance(const Graph& g, CentralityMap centrality) |
|
574 { |
|
575 using std::max; |
|
576 |
|
577 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; |
|
578 typedef typename property_traits<CentralityMap>::value_type centrality_type; |
|
579 |
|
580 typename graph_traits<Graph>::vertices_size_type n = num_vertices(g); |
|
581 |
|
582 // Find max centrality |
|
583 centrality_type max_centrality(0); |
|
584 vertex_iterator v, v_end; |
|
585 for (tie(v, v_end) = vertices(g); v != v_end; ++v) { |
|
586 max_centrality = (max)(max_centrality, get(centrality, *v)); |
|
587 } |
|
588 |
|
589 // Compute central point dominance |
|
590 centrality_type sum(0); |
|
591 for (tie(v, v_end) = vertices(g); v != v_end; ++v) { |
|
592 sum += (max_centrality - get(centrality, *v)); |
|
593 } |
|
594 return sum/(n-1); |
|
595 } |
|
596 |
|
597 } // end namespace boost |
|
598 |
|
599 #endif // BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP |