1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/betweenness_centrality.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,599 @@
1.4 +// Copyright 2004 The Trustees of Indiana University.
1.5 +
1.6 +// Distributed under the Boost Software License, Version 1.0.
1.7 +// (See accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// Authors: Douglas Gregor
1.11 +// Andrew Lumsdaine
1.12 +#ifndef BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
1.13 +#define BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
1.14 +
1.15 +#include <stack>
1.16 +#include <vector>
1.17 +#include <boost/graph/dijkstra_shortest_paths.hpp>
1.18 +#include <boost/graph/breadth_first_search.hpp>
1.19 +#include <boost/graph/relax.hpp>
1.20 +#include <boost/graph/graph_traits.hpp>
1.21 +#include <boost/tuple/tuple.hpp>
1.22 +#include <boost/type_traits/is_convertible.hpp>
1.23 +#include <boost/type_traits/is_same.hpp>
1.24 +#include <boost/mpl/if.hpp>
1.25 +#include <boost/property_map.hpp>
1.26 +#include <boost/graph/named_function_params.hpp>
1.27 +#include <algorithm>
1.28 +
1.29 +namespace boost {
1.30 +
1.31 +namespace detail { namespace graph {
1.32 +
1.33 + /**
1.34 + * Customized visitor passed to Dijkstra's algorithm by Brandes'
1.35 + * betweenness centrality algorithm. This visitor is responsible for
1.36 + * keeping track of the order in which vertices are discovered, the
1.37 + * predecessors on the shortest path(s) to a vertex, and the number
1.38 + * of shortest paths.
1.39 + */
1.40 + template<typename Graph, typename WeightMap, typename IncomingMap,
1.41 + typename DistanceMap, typename PathCountMap>
1.42 + struct brandes_dijkstra_visitor : public bfs_visitor<>
1.43 + {
1.44 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.45 + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
1.46 +
1.47 + brandes_dijkstra_visitor(std::stack<vertex_descriptor>& ordered_vertices,
1.48 + WeightMap weight,
1.49 + IncomingMap incoming,
1.50 + DistanceMap distance,
1.51 + PathCountMap path_count)
1.52 + : ordered_vertices(ordered_vertices), weight(weight),
1.53 + incoming(incoming), distance(distance),
1.54 + path_count(path_count)
1.55 + { }
1.56 +
1.57 + /**
1.58 + * Whenever an edge e = (v, w) is relaxed, the incoming edge list
1.59 + * for w is set to {(v, w)} and the shortest path count of w is set to
1.60 + * the number of paths that reach {v}.
1.61 + */
1.62 + void edge_relaxed(edge_descriptor e, const Graph& g)
1.63 + {
1.64 + vertex_descriptor v = source(e, g), w = target(e, g);
1.65 + incoming[w].clear();
1.66 + incoming[w].push_back(e);
1.67 + put(path_count, w, get(path_count, v));
1.68 + }
1.69 +
1.70 + /**
1.71 + * If an edge e = (v, w) was not relaxed, it may still be the case
1.72 + * that we've found more equally-short paths, so include {(v, w)} in the
1.73 + * incoming edges of w and add all of the shortest paths to v to the
1.74 + * shortest path count of w.
1.75 + */
1.76 + void edge_not_relaxed(edge_descriptor e, const Graph& g)
1.77 + {
1.78 + typedef typename property_traits<WeightMap>::value_type weight_type;
1.79 + typedef typename property_traits<DistanceMap>::value_type distance_type;
1.80 + vertex_descriptor v = source(e, g), w = target(e, g);
1.81 + distance_type d_v = get(distance, v), d_w = get(distance, w);
1.82 + weight_type w_e = get(weight, e);
1.83 +
1.84 + closed_plus<distance_type> combine;
1.85 + if (d_w == combine(d_v, w_e)) {
1.86 + put(path_count, w, get(path_count, w) + get(path_count, v));
1.87 + incoming[w].push_back(e);
1.88 + }
1.89 + }
1.90 +
1.91 + /// Keep track of vertices as they are reached
1.92 + void examine_vertex(vertex_descriptor w, const Graph&)
1.93 + {
1.94 + ordered_vertices.push(w);
1.95 + }
1.96 +
1.97 + private:
1.98 + std::stack<vertex_descriptor>& ordered_vertices;
1.99 + WeightMap weight;
1.100 + IncomingMap incoming;
1.101 + DistanceMap distance;
1.102 + PathCountMap path_count;
1.103 + };
1.104 +
1.105 + /**
1.106 + * Function object that calls Dijkstra's shortest paths algorithm
1.107 + * using the Dijkstra visitor for the Brandes betweenness centrality
1.108 + * algorithm.
1.109 + */
1.110 + template<typename WeightMap>
1.111 + struct brandes_dijkstra_shortest_paths
1.112 + {
1.113 + brandes_dijkstra_shortest_paths(WeightMap weight_map)
1.114 + : weight_map(weight_map) { }
1.115 +
1.116 + template<typename Graph, typename IncomingMap, typename DistanceMap,
1.117 + typename PathCountMap, typename VertexIndexMap>
1.118 + void
1.119 + operator()(Graph& g,
1.120 + typename graph_traits<Graph>::vertex_descriptor s,
1.121 + std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov,
1.122 + IncomingMap incoming,
1.123 + DistanceMap distance,
1.124 + PathCountMap path_count,
1.125 + VertexIndexMap vertex_index)
1.126 + {
1.127 + typedef brandes_dijkstra_visitor<Graph, WeightMap, IncomingMap,
1.128 + DistanceMap, PathCountMap> visitor_type;
1.129 + visitor_type visitor(ov, weight_map, incoming, distance, path_count);
1.130 +
1.131 + dijkstra_shortest_paths(g, s,
1.132 + boost::weight_map(weight_map)
1.133 + .vertex_index_map(vertex_index)
1.134 + .distance_map(distance)
1.135 + .visitor(visitor));
1.136 + }
1.137 +
1.138 + private:
1.139 + WeightMap weight_map;
1.140 + };
1.141 +
1.142 + /**
1.143 + * Function object that invokes breadth-first search for the
1.144 + * unweighted form of the Brandes betweenness centrality algorithm.
1.145 + */
1.146 + struct brandes_unweighted_shortest_paths
1.147 + {
1.148 + /**
1.149 + * Customized visitor passed to breadth-first search, which
1.150 + * records predecessor and the number of shortest paths to each
1.151 + * vertex.
1.152 + */
1.153 + template<typename Graph, typename IncomingMap, typename DistanceMap,
1.154 + typename PathCountMap>
1.155 + struct visitor_type : public bfs_visitor<>
1.156 + {
1.157 + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
1.158 + typedef typename graph_traits<Graph>::vertex_descriptor
1.159 + vertex_descriptor;
1.160 +
1.161 + visitor_type(IncomingMap incoming, DistanceMap distance,
1.162 + PathCountMap path_count,
1.163 + std::stack<vertex_descriptor>& ordered_vertices)
1.164 + : incoming(incoming), distance(distance),
1.165 + path_count(path_count), ordered_vertices(ordered_vertices) { }
1.166 +
1.167 + /// Keep track of vertices as they are reached
1.168 + void examine_vertex(vertex_descriptor v, Graph&)
1.169 + {
1.170 + ordered_vertices.push(v);
1.171 + }
1.172 +
1.173 + /**
1.174 + * Whenever an edge e = (v, w) is labelled a tree edge, the
1.175 + * incoming edge list for w is set to {(v, w)} and the shortest
1.176 + * path count of w is set to the number of paths that reach {v}.
1.177 + */
1.178 + void tree_edge(edge_descriptor e, Graph& g)
1.179 + {
1.180 + vertex_descriptor v = source(e, g);
1.181 + vertex_descriptor w = target(e, g);
1.182 + put(distance, w, get(distance, v) + 1);
1.183 +
1.184 + put(path_count, w, get(path_count, v));
1.185 + incoming[w].push_back(e);
1.186 + }
1.187 +
1.188 + /**
1.189 + * If an edge e = (v, w) is not a tree edge, it may still be the
1.190 + * case that we've found more equally-short paths, so include (v, w)
1.191 + * in the incoming edge list of w and add all of the shortest
1.192 + * paths to v to the shortest path count of w.
1.193 + */
1.194 + void non_tree_edge(edge_descriptor e, Graph& g)
1.195 + {
1.196 + vertex_descriptor v = source(e, g);
1.197 + vertex_descriptor w = target(e, g);
1.198 + if (get(distance, w) == get(distance, v) + 1) {
1.199 + put(path_count, w, get(path_count, w) + get(path_count, v));
1.200 + incoming[w].push_back(e);
1.201 + }
1.202 + }
1.203 +
1.204 + private:
1.205 + IncomingMap incoming;
1.206 + DistanceMap distance;
1.207 + PathCountMap path_count;
1.208 + std::stack<vertex_descriptor>& ordered_vertices;
1.209 + };
1.210 +
1.211 + template<typename Graph, typename IncomingMap, typename DistanceMap,
1.212 + typename PathCountMap, typename VertexIndexMap>
1.213 + void
1.214 + operator()(Graph& g,
1.215 + typename graph_traits<Graph>::vertex_descriptor s,
1.216 + std::stack<typename graph_traits<Graph>::vertex_descriptor>& ov,
1.217 + IncomingMap incoming,
1.218 + DistanceMap distance,
1.219 + PathCountMap path_count,
1.220 + VertexIndexMap vertex_index)
1.221 + {
1.222 + typedef typename graph_traits<Graph>::vertex_descriptor
1.223 + vertex_descriptor;
1.224 +
1.225 + visitor_type<Graph, IncomingMap, DistanceMap, PathCountMap>
1.226 + visitor(incoming, distance, path_count, ov);
1.227 +
1.228 + std::vector<default_color_type>
1.229 + colors(num_vertices(g), color_traits<default_color_type>::white());
1.230 + boost::queue<vertex_descriptor> Q;
1.231 + breadth_first_visit(g, s, Q, visitor,
1.232 + make_iterator_property_map(colors.begin(),
1.233 + vertex_index));
1.234 + }
1.235 + };
1.236 +
1.237 + // When the edge centrality map is a dummy property map, no
1.238 + // initialization is needed.
1.239 + template<typename Iter>
1.240 + inline void
1.241 + init_centrality_map(std::pair<Iter, Iter>, dummy_property_map) { }
1.242 +
1.243 + // When we have a real edge centrality map, initialize all of the
1.244 + // centralities to zero.
1.245 + template<typename Iter, typename Centrality>
1.246 + void
1.247 + init_centrality_map(std::pair<Iter, Iter> keys, Centrality centrality_map)
1.248 + {
1.249 + typedef typename property_traits<Centrality>::value_type
1.250 + centrality_type;
1.251 + while (keys.first != keys.second) {
1.252 + put(centrality_map, *keys.first, centrality_type(0));
1.253 + ++keys.first;
1.254 + }
1.255 + }
1.256 +
1.257 + // When the edge centrality map is a dummy property map, no update
1.258 + // is performed.
1.259 + template<typename Key, typename T>
1.260 + inline void
1.261 + update_centrality(dummy_property_map, const Key&, const T&) { }
1.262 +
1.263 + // When we have a real edge centrality map, add the value to the map
1.264 + template<typename CentralityMap, typename Key, typename T>
1.265 + inline void
1.266 + update_centrality(CentralityMap centrality_map, Key k, const T& x)
1.267 + { put(centrality_map, k, get(centrality_map, k) + x); }
1.268 +
1.269 + template<typename Iter>
1.270 + inline void
1.271 + divide_centrality_by_two(std::pair<Iter, Iter>, dummy_property_map) {}
1.272 +
1.273 + template<typename Iter, typename CentralityMap>
1.274 + inline void
1.275 + divide_centrality_by_two(std::pair<Iter, Iter> keys,
1.276 + CentralityMap centrality_map)
1.277 + {
1.278 + typename property_traits<CentralityMap>::value_type two(2);
1.279 + while (keys.first != keys.second) {
1.280 + put(centrality_map, *keys.first, get(centrality_map, *keys.first) / two);
1.281 + ++keys.first;
1.282 + }
1.283 + }
1.284 +
1.285 + template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
1.286 + typename IncomingMap, typename DistanceMap,
1.287 + typename DependencyMap, typename PathCountMap,
1.288 + typename VertexIndexMap, typename ShortestPaths>
1.289 + void
1.290 + brandes_betweenness_centrality_impl(const Graph& g,
1.291 + CentralityMap centrality, // C_B
1.292 + EdgeCentralityMap edge_centrality_map,
1.293 + IncomingMap incoming, // P
1.294 + DistanceMap distance, // d
1.295 + DependencyMap dependency, // delta
1.296 + PathCountMap path_count, // sigma
1.297 + VertexIndexMap vertex_index,
1.298 + ShortestPaths shortest_paths)
1.299 + {
1.300 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.301 + typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
1.302 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.303 +
1.304 + // Initialize centrality
1.305 + init_centrality_map(vertices(g), centrality);
1.306 + init_centrality_map(edges(g), edge_centrality_map);
1.307 +
1.308 + std::stack<vertex_descriptor> ordered_vertices;
1.309 + vertex_iterator s, s_end;
1.310 + for (tie(s, s_end) = vertices(g); s != s_end; ++s) {
1.311 + // Initialize for this iteration
1.312 + vertex_iterator w, w_end;
1.313 + for (tie(w, w_end) = vertices(g); w != w_end; ++w) {
1.314 + incoming[*w].clear();
1.315 + put(path_count, *w, 0);
1.316 + put(dependency, *w, 0);
1.317 + }
1.318 + put(path_count, *s, 1);
1.319 +
1.320 + // Execute the shortest paths algorithm. This will be either
1.321 + // Dijkstra's algorithm or a customized breadth-first search,
1.322 + // depending on whether the graph is weighted or unweighted.
1.323 + shortest_paths(g, *s, ordered_vertices, incoming, distance,
1.324 + path_count, vertex_index);
1.325 +
1.326 + while (!ordered_vertices.empty()) {
1.327 + vertex_descriptor w = ordered_vertices.top();
1.328 + ordered_vertices.pop();
1.329 +
1.330 + typedef typename property_traits<IncomingMap>::value_type
1.331 + incoming_type;
1.332 + typedef typename incoming_type::iterator incoming_iterator;
1.333 + typedef typename property_traits<DependencyMap>::value_type
1.334 + dependency_type;
1.335 +
1.336 + for (incoming_iterator vw = incoming[w].begin();
1.337 + vw != incoming[w].end(); ++vw) {
1.338 + vertex_descriptor v = source(*vw, g);
1.339 + dependency_type factor = dependency_type(get(path_count, v))
1.340 + / dependency_type(get(path_count, w));
1.341 + factor *= (dependency_type(1) + get(dependency, w));
1.342 + put(dependency, v, get(dependency, v) + factor);
1.343 + update_centrality(edge_centrality_map, *vw, factor);
1.344 + }
1.345 +
1.346 + if (w != *s) {
1.347 + update_centrality(centrality, w, get(dependency, w));
1.348 + }
1.349 + }
1.350 + }
1.351 +
1.352 + typedef typename graph_traits<Graph>::directed_category directed_category;
1.353 + const bool is_undirected =
1.354 + is_convertible<directed_category*, undirected_tag*>::value;
1.355 + if (is_undirected) {
1.356 + divide_centrality_by_two(vertices(g), centrality);
1.357 + divide_centrality_by_two(edges(g), edge_centrality_map);
1.358 + }
1.359 + }
1.360 +
1.361 +} } // end namespace detail::graph
1.362 +
1.363 +template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
1.364 + typename IncomingMap, typename DistanceMap,
1.365 + typename DependencyMap, typename PathCountMap,
1.366 + typename VertexIndexMap>
1.367 +void
1.368 +brandes_betweenness_centrality(const Graph& g,
1.369 + CentralityMap centrality, // C_B
1.370 + EdgeCentralityMap edge_centrality_map,
1.371 + IncomingMap incoming, // P
1.372 + DistanceMap distance, // d
1.373 + DependencyMap dependency, // delta
1.374 + PathCountMap path_count, // sigma
1.375 + VertexIndexMap vertex_index)
1.376 +{
1.377 + detail::graph::brandes_unweighted_shortest_paths shortest_paths;
1.378 +
1.379 + detail::graph::brandes_betweenness_centrality_impl(g, centrality,
1.380 + edge_centrality_map,
1.381 + incoming, distance,
1.382 + dependency, path_count,
1.383 + vertex_index,
1.384 + shortest_paths);
1.385 +}
1.386 +
1.387 +template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
1.388 + typename IncomingMap, typename DistanceMap,
1.389 + typename DependencyMap, typename PathCountMap,
1.390 + typename VertexIndexMap, typename WeightMap>
1.391 +void
1.392 +brandes_betweenness_centrality(const Graph& g,
1.393 + CentralityMap centrality, // C_B
1.394 + EdgeCentralityMap edge_centrality_map,
1.395 + IncomingMap incoming, // P
1.396 + DistanceMap distance, // d
1.397 + DependencyMap dependency, // delta
1.398 + PathCountMap path_count, // sigma
1.399 + VertexIndexMap vertex_index,
1.400 + WeightMap weight_map)
1.401 +{
1.402 + detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
1.403 + shortest_paths(weight_map);
1.404 +
1.405 + detail::graph::brandes_betweenness_centrality_impl(g, centrality,
1.406 + edge_centrality_map,
1.407 + incoming, distance,
1.408 + dependency, path_count,
1.409 + vertex_index,
1.410 + shortest_paths);
1.411 +}
1.412 +
1.413 +namespace detail { namespace graph {
1.414 + template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
1.415 + typename WeightMap, typename VertexIndexMap>
1.416 + void
1.417 + brandes_betweenness_centrality_dispatch2(const Graph& g,
1.418 + CentralityMap centrality,
1.419 + EdgeCentralityMap edge_centrality_map,
1.420 + WeightMap weight_map,
1.421 + VertexIndexMap vertex_index)
1.422 + {
1.423 + typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
1.424 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.425 + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
1.426 + typedef typename mpl::if_c<(is_same<CentralityMap,
1.427 + dummy_property_map>::value),
1.428 + EdgeCentralityMap,
1.429 + CentralityMap>::type a_centrality_map;
1.430 + typedef typename property_traits<a_centrality_map>::value_type
1.431 + centrality_type;
1.432 +
1.433 + typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
1.434 +
1.435 + std::vector<std::vector<edge_descriptor> > incoming(V);
1.436 + std::vector<centrality_type> distance(V);
1.437 + std::vector<centrality_type> dependency(V);
1.438 + std::vector<degree_size_type> path_count(V);
1.439 +
1.440 + brandes_betweenness_centrality(
1.441 + g, centrality, edge_centrality_map,
1.442 + make_iterator_property_map(incoming.begin(), vertex_index),
1.443 + make_iterator_property_map(distance.begin(), vertex_index),
1.444 + make_iterator_property_map(dependency.begin(), vertex_index),
1.445 + make_iterator_property_map(path_count.begin(), vertex_index),
1.446 + vertex_index,
1.447 + weight_map);
1.448 + }
1.449 +
1.450 +
1.451 + template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
1.452 + typename VertexIndexMap>
1.453 + void
1.454 + brandes_betweenness_centrality_dispatch2(const Graph& g,
1.455 + CentralityMap centrality,
1.456 + EdgeCentralityMap edge_centrality_map,
1.457 + VertexIndexMap vertex_index)
1.458 + {
1.459 + typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
1.460 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.461 + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
1.462 + typedef typename mpl::if_c<(is_same<CentralityMap,
1.463 + dummy_property_map>::value),
1.464 + EdgeCentralityMap,
1.465 + CentralityMap>::type a_centrality_map;
1.466 + typedef typename property_traits<a_centrality_map>::value_type
1.467 + centrality_type;
1.468 +
1.469 + typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
1.470 +
1.471 + std::vector<std::vector<edge_descriptor> > incoming(V);
1.472 + std::vector<centrality_type> distance(V);
1.473 + std::vector<centrality_type> dependency(V);
1.474 + std::vector<degree_size_type> path_count(V);
1.475 +
1.476 + brandes_betweenness_centrality(
1.477 + g, centrality, edge_centrality_map,
1.478 + make_iterator_property_map(incoming.begin(), vertex_index),
1.479 + make_iterator_property_map(distance.begin(), vertex_index),
1.480 + make_iterator_property_map(dependency.begin(), vertex_index),
1.481 + make_iterator_property_map(path_count.begin(), vertex_index),
1.482 + vertex_index);
1.483 + }
1.484 +
1.485 + template<typename WeightMap>
1.486 + struct brandes_betweenness_centrality_dispatch1
1.487 + {
1.488 + template<typename Graph, typename CentralityMap,
1.489 + typename EdgeCentralityMap, typename VertexIndexMap>
1.490 + static void
1.491 + run(const Graph& g, CentralityMap centrality,
1.492 + EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
1.493 + WeightMap weight_map)
1.494 + {
1.495 + brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map,
1.496 + weight_map, vertex_index);
1.497 + }
1.498 + };
1.499 +
1.500 + template<>
1.501 + struct brandes_betweenness_centrality_dispatch1<error_property_not_found>
1.502 + {
1.503 + template<typename Graph, typename CentralityMap,
1.504 + typename EdgeCentralityMap, typename VertexIndexMap>
1.505 + static void
1.506 + run(const Graph& g, CentralityMap centrality,
1.507 + EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
1.508 + error_property_not_found)
1.509 + {
1.510 + brandes_betweenness_centrality_dispatch2(g, centrality, edge_centrality_map,
1.511 + vertex_index);
1.512 + }
1.513 + };
1.514 +
1.515 +} } // end namespace detail::graph
1.516 +
1.517 +template<typename Graph, typename Param, typename Tag, typename Rest>
1.518 +void
1.519 +brandes_betweenness_centrality(const Graph& g,
1.520 + const bgl_named_params<Param,Tag,Rest>& params)
1.521 +{
1.522 + typedef bgl_named_params<Param,Tag,Rest> named_params;
1.523 +
1.524 + typedef typename property_value<named_params, edge_weight_t>::type ew;
1.525 + detail::graph::brandes_betweenness_centrality_dispatch1<ew>::run(
1.526 + g,
1.527 + choose_param(get_param(params, vertex_centrality),
1.528 + dummy_property_map()),
1.529 + choose_param(get_param(params, edge_centrality),
1.530 + dummy_property_map()),
1.531 + choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
1.532 + get_param(params, edge_weight));
1.533 +}
1.534 +
1.535 +template<typename Graph, typename CentralityMap>
1.536 +void
1.537 +brandes_betweenness_centrality(const Graph& g, CentralityMap centrality)
1.538 +{
1.539 + detail::graph::brandes_betweenness_centrality_dispatch2(
1.540 + g, centrality, dummy_property_map(), get(vertex_index, g));
1.541 +}
1.542 +
1.543 +template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
1.544 +void
1.545 +brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
1.546 + EdgeCentralityMap edge_centrality_map)
1.547 +{
1.548 + detail::graph::brandes_betweenness_centrality_dispatch2(
1.549 + g, centrality, edge_centrality_map, get(vertex_index, g));
1.550 +}
1.551 +
1.552 +/**
1.553 + * Converts "absolute" betweenness centrality (as computed by the
1.554 + * brandes_betweenness_centrality algorithm) in the centrality map
1.555 + * into "relative" centrality. The result is placed back into the
1.556 + * given centrality map.
1.557 + */
1.558 +template<typename Graph, typename CentralityMap>
1.559 +void
1.560 +relative_betweenness_centrality(const Graph& g, CentralityMap centrality)
1.561 +{
1.562 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.563 + typedef typename property_traits<CentralityMap>::value_type centrality_type;
1.564 +
1.565 + typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
1.566 + centrality_type factor = centrality_type(2)/centrality_type(n*n - 3*n + 2);
1.567 + vertex_iterator v, v_end;
1.568 + for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
1.569 + put(centrality, *v, factor * get(centrality, *v));
1.570 + }
1.571 +}
1.572 +
1.573 +// Compute the central point dominance of a graph.
1.574 +template<typename Graph, typename CentralityMap>
1.575 +typename property_traits<CentralityMap>::value_type
1.576 +central_point_dominance(const Graph& g, CentralityMap centrality)
1.577 +{
1.578 + using std::max;
1.579 +
1.580 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.581 + typedef typename property_traits<CentralityMap>::value_type centrality_type;
1.582 +
1.583 + typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
1.584 +
1.585 + // Find max centrality
1.586 + centrality_type max_centrality(0);
1.587 + vertex_iterator v, v_end;
1.588 + for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
1.589 + max_centrality = (max)(max_centrality, get(centrality, *v));
1.590 + }
1.591 +
1.592 + // Compute central point dominance
1.593 + centrality_type sum(0);
1.594 + for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
1.595 + sum += (max_centrality - get(centrality, *v));
1.596 + }
1.597 + return sum/(n-1);
1.598 +}
1.599 +
1.600 +} // end namespace boost
1.601 +
1.602 +#endif // BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP