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/overloading.hpp> |
15 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
16 | #include <boost/graph/breadth_first_search.hpp> |
17 | #include <boost/graph/relax.hpp> |
18 | #include <boost/graph/graph_traits.hpp> |
19 | #include <boost/tuple/tuple.hpp> |
20 | #include <boost/type_traits/is_convertible.hpp> |
21 | #include <boost/type_traits/is_same.hpp> |
22 | #include <boost/mpl/if.hpp> |
23 | #include <boost/property_map/property_map.hpp> |
24 | #include <boost/graph/named_function_params.hpp> |
25 | #include <algorithm> |
26 | |
27 | namespace boost { |
28 | |
29 | namespace detail { namespace graph { |
30 | |
31 | /** |
32 | * Customized visitor passed to Dijkstra's algorithm by Brandes' |
33 | * betweenness centrality algorithm. This visitor is responsible for |
34 | * keeping track of the order in which vertices are discovered, the |
35 | * predecessors on the shortest path(s) to a vertex, and the number |
36 | * of shortest paths. |
37 | */ |
38 | template<typename Graph, typename WeightMap, typename IncomingMap, |
39 | typename DistanceMap, typename PathCountMap> |
40 | struct brandes_dijkstra_visitor : public bfs_visitor<> |
41 | { |
42 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; |
43 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
44 | |
45 | brandes_dijkstra_visitor(std::stack<vertex_descriptor>& ordered_vertices, |
46 | WeightMap weight, |
47 | IncomingMap incoming, |
48 | DistanceMap distance, |
49 | PathCountMap path_count) |
50 | : ordered_vertices(ordered_vertices), weight(weight), |
51 | incoming(incoming), distance(distance), |
52 | path_count(path_count) |
53 | { } |
54 | |
55 | /** |
56 | * Whenever an edge e = (v, w) is relaxed, the incoming edge list |
57 | * for w is set to {(v, w)} and the shortest path count of w is set to |
58 | * the number of paths that reach {v}. |
59 | */ |
60 | void edge_relaxed(edge_descriptor e, const Graph& g) |
61 | { |
62 | vertex_descriptor v = source(e, g), w = target(e, g); |
63 | incoming[w].clear(); |
64 | incoming[w].push_back(e); |
65 | put(path_count, w, get(path_count, v)); |
66 | } |
67 | |
68 | /** |
69 | * If an edge e = (v, w) was not relaxed, it may still be the case |
70 | * that we've found more equally-short paths, so include {(v, w)} in the |
71 | * incoming edges of w and add all of the shortest paths to v to the |
72 | * shortest path count of w. |
73 | */ |
74 | void edge_not_relaxed(edge_descriptor e, const Graph& g) |
75 | { |
76 | typedef typename property_traits<WeightMap>::value_type weight_type; |
77 | typedef typename property_traits<DistanceMap>::value_type distance_type; |
78 | vertex_descriptor v = source(e, g), w = target(e, g); |
79 | distance_type d_v = get(distance, v), d_w = get(distance, w); |
80 | weight_type w_e = get(weight, e); |
81 | |
82 | closed_plus<distance_type> combine; |
83 | if (d_w == combine(d_v, w_e)) { |
84 | put(path_count, w, get(path_count, w) + get(path_count, v)); |
85 | incoming[w].push_back(e); |
86 | } |
87 | } |
88 | |
89 | /// Keep track of vertices as they are reached |
90 | void examine_vertex(vertex_descriptor w, const Graph&) |
91 | { |
92 | ordered_vertices.push(w); |
93 | } |
94 | |
95 | private: |
96 | std::stack<vertex_descriptor>& ordered_vertices; |
97 | WeightMap weight; |
98 | IncomingMap incoming; |
99 | DistanceMap distance; |
100 | PathCountMap path_count; |
101 | }; |
102 | |
103 | /** |
104 | * Function object that calls Dijkstra's shortest paths algorithm |
105 | * using the Dijkstra visitor for the Brandes betweenness centrality |
106 | * algorithm. |
107 | */ |
108 | template<typename WeightMap> |
109 | struct brandes_dijkstra_shortest_paths |
110 | { |
111 | brandes_dijkstra_shortest_paths(WeightMap weight_map) |
112 | : weight_map(weight_map) { } |
113 | |
114 | template<typename Graph, typename IncomingMap, typename DistanceMap, |
115 | typename PathCountMap, typename VertexIndexMap> |
116 | void |
117 | operator()(Graph& g, |
118 | typename graph_traits<Graph>::vertex_descriptor s, |
119 | std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov, |
120 | IncomingMap incoming, |
121 | DistanceMap distance, |
122 | PathCountMap path_count, |
123 | VertexIndexMap vertex_index) |
124 | { |
125 | typedef brandes_dijkstra_visitor<Graph, WeightMap, IncomingMap, |
126 | DistanceMap, PathCountMap> visitor_type; |
127 | visitor_type visitor(ov, weight_map, incoming, distance, path_count); |
128 | |
129 | dijkstra_shortest_paths(g, s, |
130 | boost::weight_map(weight_map) |
131 | .vertex_index_map(vertex_index) |
132 | .distance_map(distance) |
133 | .visitor(visitor)); |
134 | } |
135 | |
136 | private: |
137 | WeightMap weight_map; |
138 | }; |
139 | |
140 | /** |
141 | * Function object that invokes breadth-first search for the |
142 | * unweighted form of the Brandes betweenness centrality algorithm. |
143 | */ |
144 | struct brandes_unweighted_shortest_paths |
145 | { |
146 | /** |
147 | * Customized visitor passed to breadth-first search, which |
148 | * records predecessor and the number of shortest paths to each |
149 | * vertex. |
150 | */ |
151 | template<typename Graph, typename IncomingMap, typename DistanceMap, |
152 | typename PathCountMap> |
153 | struct visitor_type : public bfs_visitor<> |
154 | { |
155 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
156 | typedef typename graph_traits<Graph>::vertex_descriptor |
157 | vertex_descriptor; |
158 | |
159 | visitor_type(IncomingMap incoming, DistanceMap distance, |
160 | PathCountMap path_count, |
161 | std::stack<vertex_descriptor>& ordered_vertices) |
162 | : incoming(incoming), distance(distance), |
163 | path_count(path_count), ordered_vertices(ordered_vertices) { } |
164 | |
165 | /// Keep track of vertices as they are reached |
166 | void examine_vertex(vertex_descriptor v, Graph&) |
167 | { |
168 | ordered_vertices.push(v); |
169 | } |
170 | |
171 | /** |
172 | * Whenever an edge e = (v, w) is labelled a tree edge, the |
173 | * incoming edge list for w is set to {(v, w)} and the shortest |
174 | * path count of w is set to the number of paths that reach {v}. |
175 | */ |
176 | void tree_edge(edge_descriptor e, Graph& g) |
177 | { |
178 | vertex_descriptor v = source(e, g); |
179 | vertex_descriptor w = target(e, g); |
180 | put(distance, w, get(distance, v) + 1); |
181 | |
182 | put(path_count, w, get(path_count, v)); |
183 | incoming[w].push_back(e); |
184 | } |
185 | |
186 | /** |
187 | * If an edge e = (v, w) is not a tree edge, it may still be the |
188 | * case that we've found more equally-short paths, so include (v, w) |
189 | * in the incoming edge list of w and add all of the shortest |
190 | * paths to v to the shortest path count of w. |
191 | */ |
192 | void non_tree_edge(edge_descriptor e, Graph& g) |
193 | { |
194 | vertex_descriptor v = source(e, g); |
195 | vertex_descriptor w = target(e, g); |
196 | if (get(distance, w) == get(distance, v) + 1) { |
197 | put(path_count, w, get(path_count, w) + get(path_count, v)); |
198 | incoming[w].push_back(e); |
199 | } |
200 | } |
201 | |
202 | private: |
203 | IncomingMap incoming; |
204 | DistanceMap distance; |
205 | PathCountMap path_count; |
206 | std::stack<vertex_descriptor>& ordered_vertices; |
207 | }; |
208 | |
209 | template<typename Graph, typename IncomingMap, typename DistanceMap, |
210 | typename PathCountMap, typename VertexIndexMap> |
211 | void |
212 | operator()(Graph& g, |
213 | typename graph_traits<Graph>::vertex_descriptor s, |
214 | std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov, |
215 | IncomingMap incoming, |
216 | DistanceMap distance, |
217 | PathCountMap path_count, |
218 | VertexIndexMap vertex_index) |
219 | { |
220 | typedef typename graph_traits<Graph>::vertex_descriptor |
221 | vertex_descriptor; |
222 | |
223 | visitor_type<Graph, IncomingMap, DistanceMap, PathCountMap> |
224 | visitor(incoming, distance, path_count, ov); |
225 | |
226 | std::vector<default_color_type> |
227 | colors(num_vertices(g), color_traits<default_color_type>::white()); |
228 | boost::queue<vertex_descriptor> Q; |
229 | breadth_first_visit(g, s, Q, visitor, |
230 | make_iterator_property_map(colors.begin(), |
231 | vertex_index)); |
232 | } |
233 | }; |
234 | |
235 | // When the edge centrality map is a dummy property map, no |
236 | // initialization is needed. |
237 | template<typename Iter> |
238 | inline void |
239 | init_centrality_map(std::pair<Iter, Iter>, dummy_property_map) { } |
240 | |
241 | // When we have a real edge centrality map, initialize all of the |
242 | // centralities to zero. |
243 | template<typename Iter, typename Centrality> |
244 | void |
245 | init_centrality_map(std::pair<Iter, Iter> keys, Centrality centrality_map) |
246 | { |
247 | typedef typename property_traits<Centrality>::value_type |
248 | centrality_type; |
249 | while (keys.first != keys.second) { |
250 | put(centrality_map, *keys.first, centrality_type(0)); |
251 | ++keys.first; |
252 | } |
253 | } |
254 | |
255 | // When the edge centrality map is a dummy property map, no update |
256 | // is performed. |
257 | template<typename Key, typename T> |
258 | inline void |
259 | update_centrality(dummy_property_map, const Key&, const T&) { } |
260 | |
261 | // When we have a real edge centrality map, add the value to the map |
262 | template<typename CentralityMap, typename Key, typename T> |
263 | inline void |
264 | update_centrality(CentralityMap centrality_map, Key k, const T& x) |
265 | { put(centrality_map, k, get(centrality_map, k) + x); } |
266 | |
267 | template<typename Iter> |
268 | inline void |
269 | divide_centrality_by_two(std::pair<Iter, Iter>, dummy_property_map) {} |
270 | |
271 | template<typename Iter, typename CentralityMap> |
272 | inline void |
273 | divide_centrality_by_two(std::pair<Iter, Iter> keys, |
274 | CentralityMap centrality_map) |
275 | { |
276 | typename property_traits<CentralityMap>::value_type two(2); |
277 | while (keys.first != keys.second) { |
278 | put(centrality_map, *keys.first, get(centrality_map, *keys.first) / two); |
279 | ++keys.first; |
280 | } |
281 | } |
282 | |
283 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
284 | typename IncomingMap, typename DistanceMap, |
285 | typename DependencyMap, typename PathCountMap, |
286 | typename VertexIndexMap, typename ShortestPaths> |
287 | void |
288 | brandes_betweenness_centrality_impl(const Graph& g, |
289 | CentralityMap centrality, // C_B |
290 | EdgeCentralityMap edge_centrality_map, |
291 | IncomingMap incoming, // P |
292 | DistanceMap distance, // d |
293 | DependencyMap dependency, // delta |
294 | PathCountMap path_count, // sigma |
295 | VertexIndexMap vertex_index, |
296 | ShortestPaths shortest_paths) |
297 | { |
298 | typedef typename graph_traits<Graph>::vertex_iterator vertex_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 (boost::tie(s, s_end) = vertices(g); s != s_end; ++s) { |
308 | // Initialize for this iteration |
309 | vertex_iterator w, w_end; |
310 | for (boost::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 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
374 | { |
375 | detail::graph::brandes_unweighted_shortest_paths shortest_paths; |
376 | |
377 | detail::graph::brandes_betweenness_centrality_impl(g, centrality, |
378 | edge_centrality_map, |
379 | incoming, distance, |
380 | dependency, path_count, |
381 | vertex_index, |
382 | shortest_paths); |
383 | } |
384 | |
385 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
386 | typename IncomingMap, typename DistanceMap, |
387 | typename DependencyMap, typename PathCountMap, |
388 | typename VertexIndexMap, typename WeightMap> |
389 | void |
390 | brandes_betweenness_centrality(const Graph& g, |
391 | CentralityMap centrality, // C_B |
392 | EdgeCentralityMap edge_centrality_map, |
393 | IncomingMap incoming, // P |
394 | DistanceMap distance, // d |
395 | DependencyMap dependency, // delta |
396 | PathCountMap path_count, // sigma |
397 | VertexIndexMap vertex_index, |
398 | WeightMap weight_map |
399 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
400 | { |
401 | detail::graph::brandes_dijkstra_shortest_paths<WeightMap> |
402 | shortest_paths(weight_map); |
403 | |
404 | detail::graph::brandes_betweenness_centrality_impl(g, centrality, |
405 | edge_centrality_map, |
406 | incoming, distance, |
407 | dependency, path_count, |
408 | vertex_index, |
409 | shortest_paths); |
410 | } |
411 | |
412 | namespace detail { namespace graph { |
413 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
414 | typename WeightMap, typename VertexIndexMap> |
415 | void |
416 | brandes_betweenness_centrality_dispatch2(const Graph& g, |
417 | CentralityMap centrality, |
418 | EdgeCentralityMap edge_centrality_map, |
419 | WeightMap weight_map, |
420 | VertexIndexMap vertex_index) |
421 | { |
422 | typedef typename graph_traits<Graph>::degree_size_type degree_size_type; |
423 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
424 | typedef typename mpl::if_c<(is_same<CentralityMap, |
425 | dummy_property_map>::value), |
426 | EdgeCentralityMap, |
427 | CentralityMap>::type a_centrality_map; |
428 | typedef typename property_traits<a_centrality_map>::value_type |
429 | centrality_type; |
430 | |
431 | typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); |
432 | |
433 | std::vector<std::vector<edge_descriptor> > incoming(V); |
434 | std::vector<centrality_type> distance(V); |
435 | std::vector<centrality_type> dependency(V); |
436 | std::vector<degree_size_type> path_count(V); |
437 | |
438 | brandes_betweenness_centrality( |
439 | g, centrality, edge_centrality_map, |
440 | make_iterator_property_map(incoming.begin(), vertex_index), |
441 | make_iterator_property_map(distance.begin(), vertex_index), |
442 | make_iterator_property_map(dependency.begin(), vertex_index), |
443 | make_iterator_property_map(path_count.begin(), vertex_index), |
444 | vertex_index, |
445 | weight_map); |
446 | } |
447 | |
448 | |
449 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
450 | typename VertexIndexMap> |
451 | void |
452 | brandes_betweenness_centrality_dispatch2(const Graph& g, |
453 | CentralityMap centrality, |
454 | EdgeCentralityMap edge_centrality_map, |
455 | VertexIndexMap vertex_index) |
456 | { |
457 | typedef typename graph_traits<Graph>::degree_size_type degree_size_type; |
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<param_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 | param_not_found) |
506 | { |
507 | brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map, |
508 | vertex_index); |
509 | } |
510 | }; |
511 | |
512 | template <typename T> |
513 | struct is_bgl_named_params { |
514 | BOOST_STATIC_CONSTANT(bool, value = false); |
515 | }; |
516 | |
517 | template <typename Param, typename Tag, typename Rest> |
518 | struct is_bgl_named_params<bgl_named_params<Param, Tag, Rest> > { |
519 | BOOST_STATIC_CONSTANT(bool, value = true); |
520 | }; |
521 | |
522 | } } // end namespace detail::graph |
523 | |
524 | template<typename Graph, typename Param, typename Tag, typename Rest> |
525 | void |
526 | brandes_betweenness_centrality(const Graph& g, |
527 | const bgl_named_params<Param,Tag,Rest>& params |
528 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
529 | { |
530 | typedef bgl_named_params<Param,Tag,Rest> named_params; |
531 | |
532 | typedef typename get_param_type<edge_weight_t, named_params>::type ew; |
533 | detail::graph::brandes_betweenness_centrality_dispatch1<ew>::run( |
534 | g, |
535 | choose_param(get_param(params, vertex_centrality), |
536 | dummy_property_map()), |
537 | choose_param(get_param(params, edge_centrality), |
538 | dummy_property_map()), |
539 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
540 | get_param(params, edge_weight)); |
541 | } |
542 | |
543 | // disable_if is required to work around problem with MSVC 7.1 (it seems to not |
544 | // get partial ordering getween this overload and the previous one correct) |
545 | template<typename Graph, typename CentralityMap> |
546 | typename disable_if<detail::graph::is_bgl_named_params<CentralityMap>, |
547 | void>::type |
548 | brandes_betweenness_centrality(const Graph& g, CentralityMap centrality |
549 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
550 | { |
551 | detail::graph::brandes_betweenness_centrality_dispatch2( |
552 | g, centrality, dummy_property_map(), get(vertex_index, g)); |
553 | } |
554 | |
555 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap> |
556 | void |
557 | brandes_betweenness_centrality(const Graph& g, CentralityMap centrality, |
558 | EdgeCentralityMap edge_centrality_map |
559 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
560 | { |
561 | detail::graph::brandes_betweenness_centrality_dispatch2( |
562 | g, centrality, edge_centrality_map, get(vertex_index, g)); |
563 | } |
564 | |
565 | /** |
566 | * Converts "absolute" betweenness centrality (as computed by the |
567 | * brandes_betweenness_centrality algorithm) in the centrality map |
568 | * into "relative" centrality. The result is placed back into the |
569 | * given centrality map. |
570 | */ |
571 | template<typename Graph, typename CentralityMap> |
572 | void |
573 | relative_betweenness_centrality(const Graph& g, CentralityMap centrality) |
574 | { |
575 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; |
576 | typedef typename property_traits<CentralityMap>::value_type centrality_type; |
577 | |
578 | typename graph_traits<Graph>::vertices_size_type n = num_vertices(g); |
579 | centrality_type factor = centrality_type(2)/centrality_type(n*n - 3*n + 2); |
580 | vertex_iterator v, v_end; |
581 | for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) { |
582 | put(centrality, *v, factor * get(centrality, *v)); |
583 | } |
584 | } |
585 | |
586 | // Compute the central point dominance of a graph. |
587 | template<typename Graph, typename CentralityMap> |
588 | typename property_traits<CentralityMap>::value_type |
589 | central_point_dominance(const Graph& g, CentralityMap centrality |
590 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
591 | { |
592 | using std::max; |
593 | |
594 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; |
595 | typedef typename property_traits<CentralityMap>::value_type centrality_type; |
596 | |
597 | typename graph_traits<Graph>::vertices_size_type n = num_vertices(g); |
598 | |
599 | // Find max centrality |
600 | centrality_type max_centrality(0); |
601 | vertex_iterator v, v_end; |
602 | for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) { |
603 | max_centrality = (max)(max_centrality, get(centrality, *v)); |
604 | } |
605 | |
606 | // Compute central point dominance |
607 | centrality_type sum(0); |
608 | for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) { |
609 | sum += (max_centrality - get(centrality, *v)); |
610 | } |
611 | return sum/(n-1); |
612 | } |
613 | |
614 | } // end namespace boost |
615 | |
616 | #endif // BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP |
617 | |