]>
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_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 |