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