root / custompackages / graph-parser / src / centrality.h @ 33e5ad95
History | View | Annotate | Download (27.2 KB)
| 1 | c6961065 | Quynh PX Nguyen | //
|
|---|---|---|---|
| 2 | // Created by quynh on 12/15/15.
|
||
| 3 | 162e1bda | Quynh PX Nguyen | // The code is mainly from boost/graph/betweenness_centrality.
|
| 4 | // I modified the code to work with Traffic Matrix.
|
||
| 5 | c6961065 | Quynh PX Nguyen | //
|
| 6 | |||
| 7 | #ifndef GRAPH_PARSER_CENTRALITY_H
|
||
| 8 | #define GRAPH_PARSER_CENTRALITY_H
|
||
| 9 | |||
| 10 | #include <fstream> |
||
| 11 | 162e1bda | Quynh PX Nguyen | #include <iostream> |
| 12 | c6961065 | Quynh PX Nguyen | #include <boost/graph/betweenness_centrality.hpp> |
| 13 | #include "common.h" |
||
| 14 | |||
| 15 | 162e1bda | Quynh PX Nguyen | namespace boost {
|
| 16 | |||
| 17 | namespace detail { namespace graph {
|
||
| 18 | |||
| 19 | template<typename Graph, typename TrafficMatrix, |
||
| 20 | typename VertexDescriptor> |
||
| 21 | int get_traffic_matrix_value(const Graph& g, |
||
| 22 | TrafficMatrix traffic_matrix, |
||
| 23 | VertexDescriptor v1, |
||
| 24 | VertexDescriptor v2) {
|
||
| 25 | string name_1 = g[v1].id; |
||
| 26 | string name_2 = g[v2].id; |
||
| 27 | std::pair<std::string, std::string> p; |
||
| 28 | if (name_1.compare(name_2) <= 0) |
||
| 29 | {
|
||
| 30 | p = std::pair<std::string, std::string>(name_1, name_2); |
||
| 31 | } |
||
| 32 | else {
|
||
| 33 | p = std::pair<std::string, std::string>(name_2, name_1); |
||
| 34 | } |
||
| 35 | |||
| 36 | // TODO: how to return the default value 1 for traffic_matrix.
|
||
| 37 | // If we are using std::map, then find() will be sufficient.
|
||
| 38 | // But we are using the PropertyMap from boost...
|
||
| 39 | // I don't think that there will be the case that p doesn't belong to traffic_matrix
|
||
| 40 | // But it might result in a bug if p does not exist in traffic_matrix
|
||
| 41 | int value = boost::get(traffic_matrix, p);
|
||
| 42 | return value;
|
||
| 43 | } |
||
| 44 | |||
| 45 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
||
| 46 | typename TrafficMatrix, |
||
| 47 | typename IncomingMap, typename DistanceMap, |
||
| 48 | typename DependencyMap, typename PathCountMap, |
||
| 49 | typename VertexIndexMap, typename ShortestPaths> |
||
| 50 | void
|
||
| 51 | brandes_betweenness_centrality_heuristic_impl(const Graph& g,
|
||
| 52 | TrafficMatrix traffic_matrix, |
||
| 53 | CentralityMap centrality, // C_B
|
||
| 54 | EdgeCentralityMap edge_centrality_map, |
||
| 55 | IncomingMap incoming, // P
|
||
| 56 | DistanceMap distance, // d
|
||
| 57 | DependencyMap dependency, // delta
|
||
| 58 | PathCountMap path_count, // sigma
|
||
| 59 | VertexIndexMap vertex_index, |
||
| 60 | ShortestPaths shortest_paths) |
||
| 61 | {
|
||
| 62 | e263e3c7 | Quynh PX Nguyen | // std::cout << "Heuristic Betweenness Centrality Implementation\n";
|
| 63 | 162e1bda | Quynh PX Nguyen | |
| 64 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
|
||
| 65 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
|
||
| 66 | |||
| 67 | // Initialize centrality
|
||
| 68 | init_centrality_map(vertices(g), centrality); |
||
| 69 | init_centrality_map(edges(g), edge_centrality_map); |
||
| 70 | |||
| 71 | std::stack<vertex_descriptor> ordered_vertices; |
||
| 72 | vertex_iterator s, s_end; |
||
| 73 | for (boost::tie(s, s_end) = vertices(g); s != s_end; ++s) {
|
||
| 74 | // Initialize for this iteration
|
||
| 75 | vertex_iterator w, w_end; |
||
| 76 | for (boost::tie(w, w_end) = vertices(g); w != w_end; ++w) {
|
||
| 77 | incoming[*w].clear(); |
||
| 78 | put(path_count, *w, 0);
|
||
| 79 | put(dependency, *w, 0);
|
||
| 80 | } |
||
| 81 | put(path_count, *s, 1);
|
||
| 82 | |||
| 83 | // Execute the shortest paths algorithm. This will be either
|
||
| 84 | // Dijkstra's algorithm or a customized breadth-first search,
|
||
| 85 | // depending on whether the graph is weighted or unweighted.
|
||
| 86 | shortest_paths(g, *s, ordered_vertices, incoming, distance, |
||
| 87 | path_count, vertex_index); |
||
| 88 | |||
| 89 | while (!ordered_vertices.empty()) {
|
||
| 90 | vertex_descriptor w = ordered_vertices.top(); |
||
| 91 | ordered_vertices.pop(); |
||
| 92 | |||
| 93 | typedef typename property_traits<IncomingMap>::value_type
|
||
| 94 | incoming_type; |
||
| 95 | typedef typename incoming_type::iterator incoming_iterator;
|
||
| 96 | typedef typename property_traits<DependencyMap>::value_type
|
||
| 97 | dependency_type; |
||
| 98 | |||
| 99 | // get communication intensity from traffic_matrix
|
||
| 100 | // dependency_type communication_intensity = dependency_type(1);
|
||
| 101 | 33e5ad95 | Quynh PX Nguyen | dependency_type communication_intensity = get_traffic_matrix_value(g, traffic_matrix, w, *s); // denoted as h in the paper
|
| 102 | 162e1bda | Quynh PX Nguyen | put(dependency, w, communication_intensity + get(dependency, w)); |
| 103 | |||
| 104 | 33e5ad95 | Quynh PX Nguyen | update_centrality(centrality, *s, communication_intensity); // the number of times s is a source
|
| 105 | |||
| 106 | 162e1bda | Quynh PX Nguyen | dependency_type factor = dependency_type(get(dependency, w)) |
| 107 | / dependency_type(get(path_count, w)); |
||
| 108 | |||
| 109 | for (incoming_iterator vw = incoming[w].begin();
|
||
| 110 | vw != incoming[w].end(); ++vw) {
|
||
| 111 | vertex_descriptor v = source(*vw, g); |
||
| 112 | |||
| 113 | dependency_type new_dependency_value = get(dependency, v) + ( |
||
| 114 | dependency_type(get(path_count, v)) * factor); |
||
| 115 | put(dependency, v, new_dependency_value); |
||
| 116 | update_centrality(edge_centrality_map, *vw, factor); |
||
| 117 | } |
||
| 118 | |||
| 119 | if (w != *s) {
|
||
| 120 | update_centrality(centrality, w, get(dependency, w)); |
||
| 121 | } |
||
| 122 | } |
||
| 123 | } |
||
| 124 | |||
| 125 | typedef typename graph_traits<Graph>::directed_category directed_category;
|
||
| 126 | const bool is_undirected = |
||
| 127 | is_convertible<directed_category*, undirected_tag*>::value; |
||
| 128 | if (is_undirected) {
|
||
| 129 | divide_centrality_by_two(vertices(g), centrality); |
||
| 130 | divide_centrality_by_two(edges(g), edge_centrality_map); |
||
| 131 | } |
||
| 132 | } |
||
| 133 | } } // end of namespace detail::graph
|
||
| 134 | |||
| 135 | template<typename Graph, |
||
| 136 | typename TrafficMatrix, |
||
| 137 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 138 | typename IncomingMap, typename DistanceMap, |
||
| 139 | typename DependencyMap, typename PathCountMap, |
||
| 140 | typename VertexIndexMap> |
||
| 141 | void
|
||
| 142 | brandes_betweenness_centrality_heuristic(const Graph& g,
|
||
| 143 | TrafficMatrix traffic_matrix, |
||
| 144 | CentralityMap centrality, // C_B
|
||
| 145 | EdgeCentralityMap edge_centrality_map, |
||
| 146 | IncomingMap incoming, // P
|
||
| 147 | DistanceMap distance, // d
|
||
| 148 | DependencyMap dependency, // delta
|
||
| 149 | PathCountMap path_count, // sigma
|
||
| 150 | VertexIndexMap vertex_index |
||
| 151 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
||
| 152 | {
|
||
| 153 | detail::graph::brandes_unweighted_shortest_paths shortest_paths; |
||
| 154 | |||
| 155 | detail::graph::brandes_betweenness_centrality_heuristic_impl(g, |
||
| 156 | traffic_matrix, |
||
| 157 | centrality, |
||
| 158 | edge_centrality_map, |
||
| 159 | incoming, distance, |
||
| 160 | dependency, path_count, |
||
| 161 | vertex_index, |
||
| 162 | shortest_paths); |
||
| 163 | } |
||
| 164 | |||
| 165 | template<typename Graph, |
||
| 166 | typename TrafficMatrix, |
||
| 167 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 168 | typename IncomingMap, typename DistanceMap, |
||
| 169 | typename DependencyMap, typename PathCountMap, |
||
| 170 | typename VertexIndexMap, typename WeightMap> |
||
| 171 | void
|
||
| 172 | brandes_betweenness_centrality_heuristic(const Graph& g,
|
||
| 173 | TrafficMatrix traffic_matrix, |
||
| 174 | CentralityMap centrality, // C_B
|
||
| 175 | EdgeCentralityMap edge_centrality_map, |
||
| 176 | IncomingMap incoming, // P
|
||
| 177 | DistanceMap distance, // d
|
||
| 178 | DependencyMap dependency, // delta
|
||
| 179 | PathCountMap path_count, // sigma
|
||
| 180 | VertexIndexMap vertex_index, |
||
| 181 | WeightMap weight_map |
||
| 182 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
||
| 183 | {
|
||
| 184 | detail::graph::brandes_dijkstra_shortest_paths<WeightMap> |
||
| 185 | shortest_paths(weight_map); |
||
| 186 | |||
| 187 | detail::graph::brandes_betweenness_centrality_heuristic_impl(g, |
||
| 188 | traffic_matrix, |
||
| 189 | centrality, |
||
| 190 | edge_centrality_map, |
||
| 191 | incoming, distance, |
||
| 192 | dependency, path_count, |
||
| 193 | vertex_index, |
||
| 194 | shortest_paths); |
||
| 195 | } |
||
| 196 | |||
| 197 | namespace detail { namespace graph {
|
||
| 198 | template<typename Graph, |
||
| 199 | typename TrafficMatrix, |
||
| 200 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 201 | typename WeightMap, typename VertexIndexMap> |
||
| 202 | void
|
||
| 203 | brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,
|
||
| 204 | TrafficMatrix traffic_matrix, |
||
| 205 | CentralityMap centrality, |
||
| 206 | EdgeCentralityMap edge_centrality_map, |
||
| 207 | WeightMap weight_map, |
||
| 208 | VertexIndexMap vertex_index) |
||
| 209 | {
|
||
| 210 | typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
|
||
| 211 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
|
||
| 212 | typedef typename mpl::if_c<(is_same<CentralityMap,
|
||
| 213 | dummy_property_map>::value), |
||
| 214 | EdgeCentralityMap, |
||
| 215 | CentralityMap>::type a_centrality_map; |
||
| 216 | typedef typename property_traits<a_centrality_map>::value_type
|
||
| 217 | centrality_type; |
||
| 218 | |||
| 219 | typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); |
||
| 220 | |||
| 221 | std::vector<std::vector<edge_descriptor> > incoming(V); |
||
| 222 | std::vector<centrality_type> distance(V); |
||
| 223 | std::vector<centrality_type> dependency(V); |
||
| 224 | std::vector<degree_size_type> path_count(V); |
||
| 225 | |||
| 226 | brandes_betweenness_centrality_heuristic( |
||
| 227 | g, |
||
| 228 | traffic_matrix, |
||
| 229 | centrality, edge_centrality_map, |
||
| 230 | make_iterator_property_map(incoming.begin(), vertex_index), |
||
| 231 | make_iterator_property_map(distance.begin(), vertex_index), |
||
| 232 | make_iterator_property_map(dependency.begin(), vertex_index), |
||
| 233 | make_iterator_property_map(path_count.begin(), vertex_index), |
||
| 234 | vertex_index, |
||
| 235 | weight_map); |
||
| 236 | } |
||
| 237 | |||
| 238 | |||
| 239 | template<typename Graph, |
||
| 240 | typename TrafficMatrix, |
||
| 241 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 242 | typename VertexIndexMap> |
||
| 243 | void
|
||
| 244 | brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,
|
||
| 245 | TrafficMatrix traffic_matrix, |
||
| 246 | CentralityMap centrality, |
||
| 247 | EdgeCentralityMap edge_centrality_map, |
||
| 248 | VertexIndexMap vertex_index) |
||
| 249 | {
|
||
| 250 | typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
|
||
| 251 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
|
||
| 252 | typedef typename mpl::if_c<(is_same<CentralityMap,
|
||
| 253 | dummy_property_map>::value), |
||
| 254 | EdgeCentralityMap, |
||
| 255 | CentralityMap>::type a_centrality_map; |
||
| 256 | typedef typename property_traits<a_centrality_map>::value_type
|
||
| 257 | centrality_type; |
||
| 258 | |||
| 259 | typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); |
||
| 260 | |||
| 261 | std::vector<std::vector<edge_descriptor> > incoming(V); |
||
| 262 | std::vector<centrality_type> distance(V); |
||
| 263 | std::vector<centrality_type> dependency(V); |
||
| 264 | std::vector<degree_size_type> path_count(V); |
||
| 265 | |||
| 266 | brandes_betweenness_centrality_heuristic( |
||
| 267 | g, |
||
| 268 | traffic_matrix, |
||
| 269 | centrality, edge_centrality_map, |
||
| 270 | make_iterator_property_map(incoming.begin(), vertex_index), |
||
| 271 | make_iterator_property_map(distance.begin(), vertex_index), |
||
| 272 | make_iterator_property_map(dependency.begin(), vertex_index), |
||
| 273 | make_iterator_property_map(path_count.begin(), vertex_index), |
||
| 274 | vertex_index); |
||
| 275 | } |
||
| 276 | |||
| 277 | template<typename WeightMap> |
||
| 278 | struct brandes_betweenness_centrality_heuristic_dispatch1
|
||
| 279 | {
|
||
| 280 | template<typename Graph, |
||
| 281 | typename TrafficMatrix, |
||
| 282 | typename CentralityMap, |
||
| 283 | typename EdgeCentralityMap, typename VertexIndexMap> |
||
| 284 | static void |
||
| 285 | run(const Graph& g,
|
||
| 286 | TrafficMatrix traffic_matrix, |
||
| 287 | CentralityMap centrality, |
||
| 288 | EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
||
| 289 | WeightMap weight_map) |
||
| 290 | {
|
||
| 291 | brandes_betweenness_centrality_heuristic_dispatch2(g, |
||
| 292 | traffic_matrix, |
||
| 293 | centrality, edge_centrality_map, |
||
| 294 | weight_map, vertex_index); |
||
| 295 | } |
||
| 296 | }; |
||
| 297 | |||
| 298 | template<> |
||
| 299 | struct brandes_betweenness_centrality_heuristic_dispatch1<param_not_found>
|
||
| 300 | {
|
||
| 301 | template<typename Graph, |
||
| 302 | typename TrafficMatrix, |
||
| 303 | typename CentralityMap, |
||
| 304 | typename EdgeCentralityMap, typename VertexIndexMap> |
||
| 305 | static void |
||
| 306 | run(const Graph& g,
|
||
| 307 | TrafficMatrix traffic_matrix, |
||
| 308 | CentralityMap centrality, |
||
| 309 | EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
||
| 310 | param_not_found) |
||
| 311 | {
|
||
| 312 | brandes_betweenness_centrality_heuristic_dispatch2(g, |
||
| 313 | traffic_matrix, |
||
| 314 | centrality, edge_centrality_map, |
||
| 315 | vertex_index); |
||
| 316 | } |
||
| 317 | }; |
||
| 318 | |||
| 319 | } } // end namespace detail::graph
|
||
| 320 | |||
| 321 | template<typename Graph, typename TrafficMatrix, typename Param, typename Tag, typename Rest> |
||
| 322 | void
|
||
| 323 | brandes_betweenness_centrality_heuristic(const Graph& g,
|
||
| 324 | TrafficMatrix traffic_matrix, |
||
| 325 | const bgl_named_params<Param,Tag,Rest>& params
|
||
| 326 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
||
| 327 | {
|
||
| 328 | typedef bgl_named_params<Param,Tag,Rest> named_params;
|
||
| 329 | |||
| 330 | typedef typename get_param_type<edge_weight_t, named_params>::type ew;
|
||
| 331 | detail::graph::brandes_betweenness_centrality_heuristic_dispatch1<ew>::run( |
||
| 332 | g, |
||
| 333 | traffic_matrix, |
||
| 334 | choose_param(get_param(params, vertex_centrality), |
||
| 335 | dummy_property_map()), |
||
| 336 | choose_param(get_param(params, edge_centrality), |
||
| 337 | dummy_property_map()), |
||
| 338 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
||
| 339 | get_param(params, edge_weight)); |
||
| 340 | } |
||
| 341 | |||
| 342 | d5b7a27f | Quynh PX Nguyen | //////////////////////////////////////
|
| 343 | // BGL Modification: TARGETS INCLUSION
|
||
| 344 | //////////////////////////////////////
|
||
| 345 | |||
| 346 | namespace detail { namespace graph {
|
||
| 347 | template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, |
||
| 348 | typename IncomingMap, typename DistanceMap, |
||
| 349 | typename DependencyMap, typename PathCountMap, |
||
| 350 | typename VertexIndexMap, typename ShortestPaths> |
||
| 351 | |||
| 352 | void
|
||
| 353 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion_impl(const Graph& g,
|
| 354 | bool endpoints_inclusion,
|
||
| 355 | d5b7a27f | Quynh PX Nguyen | CentralityMap centrality, // C_B
|
| 356 | EdgeCentralityMap edge_centrality_map, |
||
| 357 | IncomingMap incoming, // P
|
||
| 358 | DistanceMap distance, // d
|
||
| 359 | DependencyMap dependency, // delta
|
||
| 360 | PathCountMap path_count, // sigma
|
||
| 361 | VertexIndexMap vertex_index, |
||
| 362 | ShortestPaths shortest_paths) |
||
| 363 | {
|
||
| 364 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
|
||
| 365 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
|
||
| 366 | |||
| 367 | cout << "@@@ Targets Inclusion @@@\n";
|
||
| 368 | |||
| 369 | // Initialize centrality
|
||
| 370 | init_centrality_map(vertices(g), centrality); |
||
| 371 | init_centrality_map(edges(g), edge_centrality_map); |
||
| 372 | |||
| 373 | std::stack<vertex_descriptor> ordered_vertices; |
||
| 374 | vertex_iterator s, s_end; |
||
| 375 | for (boost::tie(s, s_end) = vertices(g); s != s_end; ++s) {
|
||
| 376 | // Initialize for this iteration
|
||
| 377 | vertex_iterator w, w_end; |
||
| 378 | for (boost::tie(w, w_end) = vertices(g); w != w_end; ++w) {
|
||
| 379 | incoming[*w].clear(); |
||
| 380 | put(path_count, *w, 0);
|
||
| 381 | put(dependency, *w, 0);
|
||
| 382 | } |
||
| 383 | put(path_count, *s, 1);
|
||
| 384 | |||
| 385 | // Execute the shortest paths algorithm. This will be either
|
||
| 386 | // Dijkstra's algorithm or a customized breadth-first search,
|
||
| 387 | // depending on whether the graph is weighted or unweighted.
|
||
| 388 | shortest_paths(g, *s, ordered_vertices, incoming, distance, |
||
| 389 | path_count, vertex_index); |
||
| 390 | |||
| 391 | 33e5ad95 | Quynh PX Nguyen | // cout << ordered_vertices.size() << endl;
|
| 392 | update_centrality(centrality, *s, ordered_vertices.size() - 1); // number of times *s is a source |
||
| 393 | |||
| 394 | d5b7a27f | Quynh PX Nguyen | while (!ordered_vertices.empty()) {
|
| 395 | vertex_descriptor w = ordered_vertices.top(); |
||
| 396 | ordered_vertices.pop(); |
||
| 397 | |||
| 398 | typedef typename property_traits<IncomingMap>::value_type
|
||
| 399 | incoming_type; |
||
| 400 | typedef typename incoming_type::iterator incoming_iterator;
|
||
| 401 | typedef typename property_traits<DependencyMap>::value_type
|
||
| 402 | dependency_type; |
||
| 403 | |||
| 404 | for (incoming_iterator vw = incoming[w].begin();
|
||
| 405 | vw != incoming[w].end(); ++vw) {
|
||
| 406 | vertex_descriptor v = source(*vw, g); |
||
| 407 | dependency_type factor = dependency_type(get(path_count, v)) |
||
| 408 | / dependency_type(get(path_count, w)); |
||
| 409 | factor *= (dependency_type(1) + get(dependency, w));
|
||
| 410 | put(dependency, v, get(dependency, v) + factor); |
||
| 411 | update_centrality(edge_centrality_map, *vw, factor); |
||
| 412 | } |
||
| 413 | |||
| 414 | if (w != *s) {
|
||
| 415 | 33e5ad95 | Quynh PX Nguyen | if (endpoints_inclusion) {
|
| 416 | d5b7a27f | Quynh PX Nguyen | update_centrality(centrality, w, get(dependency, w) + dependency_type(1));
|
| 417 | } |
||
| 418 | else {
|
||
| 419 | update_centrality(centrality, w, get(dependency, w)); |
||
| 420 | } |
||
| 421 | } |
||
| 422 | } |
||
| 423 | } |
||
| 424 | |||
| 425 | typedef typename graph_traits<Graph>::directed_category directed_category;
|
||
| 426 | const bool is_undirected = |
||
| 427 | is_convertible<directed_category*, undirected_tag*>::value; |
||
| 428 | if (is_undirected) {
|
||
| 429 | divide_centrality_by_two(vertices(g), centrality); |
||
| 430 | divide_centrality_by_two(edges(g), edge_centrality_map); |
||
| 431 | } |
||
| 432 | } |
||
| 433 | |||
| 434 | } } // end namespace detail::graph
|
||
| 435 | |||
| 436 | template<typename Graph, |
||
| 437 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 438 | typename IncomingMap, typename DistanceMap, |
||
| 439 | typename DependencyMap, typename PathCountMap, |
||
| 440 | typename VertexIndexMap> |
||
| 441 | void
|
||
| 442 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
|
| 443 | bool endpoints_inclusion,
|
||
| 444 | d5b7a27f | Quynh PX Nguyen | CentralityMap centrality, // C_B
|
| 445 | EdgeCentralityMap edge_centrality_map, |
||
| 446 | IncomingMap incoming, // P
|
||
| 447 | DistanceMap distance, // d
|
||
| 448 | DependencyMap dependency, // delta
|
||
| 449 | PathCountMap path_count, // sigma
|
||
| 450 | VertexIndexMap vertex_index |
||
| 451 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
||
| 452 | {
|
||
| 453 | detail::graph::brandes_unweighted_shortest_paths shortest_paths; |
||
| 454 | |||
| 455 | 33e5ad95 | Quynh PX Nguyen | detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g, |
| 456 | endpoints_inclusion, |
||
| 457 | d5b7a27f | Quynh PX Nguyen | centrality, |
| 458 | edge_centrality_map, |
||
| 459 | incoming, distance, |
||
| 460 | dependency, path_count, |
||
| 461 | vertex_index, |
||
| 462 | shortest_paths); |
||
| 463 | } |
||
| 464 | |||
| 465 | template<typename Graph, |
||
| 466 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 467 | typename IncomingMap, typename DistanceMap, |
||
| 468 | typename DependencyMap, typename PathCountMap, |
||
| 469 | typename VertexIndexMap, typename WeightMap> |
||
| 470 | void
|
||
| 471 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
|
| 472 | bool endpoints_inclusion,
|
||
| 473 | d5b7a27f | Quynh PX Nguyen | CentralityMap centrality, // C_B
|
| 474 | EdgeCentralityMap edge_centrality_map, |
||
| 475 | IncomingMap incoming, // P
|
||
| 476 | DistanceMap distance, // d
|
||
| 477 | DependencyMap dependency, // delta
|
||
| 478 | PathCountMap path_count, // sigma
|
||
| 479 | VertexIndexMap vertex_index, |
||
| 480 | WeightMap weight_map |
||
| 481 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
||
| 482 | {
|
||
| 483 | detail::graph::brandes_dijkstra_shortest_paths<WeightMap> |
||
| 484 | shortest_paths(weight_map); |
||
| 485 | |||
| 486 | 33e5ad95 | Quynh PX Nguyen | detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g, |
| 487 | endpoints_inclusion, |
||
| 488 | d5b7a27f | Quynh PX Nguyen | centrality, |
| 489 | edge_centrality_map, |
||
| 490 | incoming, distance, |
||
| 491 | dependency, path_count, |
||
| 492 | vertex_index, |
||
| 493 | shortest_paths); |
||
| 494 | } |
||
| 495 | |||
| 496 | namespace detail { namespace graph {
|
||
| 497 | template<typename Graph, |
||
| 498 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 499 | typename WeightMap, typename VertexIndexMap> |
||
| 500 | void
|
||
| 501 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion_dispatch2(const Graph& g,
|
| 502 | bool endpoints_inclusion,
|
||
| 503 | d5b7a27f | Quynh PX Nguyen | CentralityMap centrality, |
| 504 | EdgeCentralityMap edge_centrality_map, |
||
| 505 | WeightMap weight_map, |
||
| 506 | VertexIndexMap vertex_index) |
||
| 507 | {
|
||
| 508 | typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
|
||
| 509 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
|
||
| 510 | typedef typename mpl::if_c<(is_same<CentralityMap,
|
||
| 511 | dummy_property_map>::value), |
||
| 512 | EdgeCentralityMap, |
||
| 513 | CentralityMap>::type a_centrality_map; |
||
| 514 | typedef typename property_traits<a_centrality_map>::value_type
|
||
| 515 | centrality_type; |
||
| 516 | |||
| 517 | typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); |
||
| 518 | |||
| 519 | std::vector<std::vector<edge_descriptor> > incoming(V); |
||
| 520 | std::vector<centrality_type> distance(V); |
||
| 521 | std::vector<centrality_type> dependency(V); |
||
| 522 | std::vector<degree_size_type> path_count(V); |
||
| 523 | |||
| 524 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion( |
| 525 | d5b7a27f | Quynh PX Nguyen | g, |
| 526 | 33e5ad95 | Quynh PX Nguyen | endpoints_inclusion, |
| 527 | d5b7a27f | Quynh PX Nguyen | centrality, edge_centrality_map, |
| 528 | make_iterator_property_map(incoming.begin(), vertex_index), |
||
| 529 | make_iterator_property_map(distance.begin(), vertex_index), |
||
| 530 | make_iterator_property_map(dependency.begin(), vertex_index), |
||
| 531 | make_iterator_property_map(path_count.begin(), vertex_index), |
||
| 532 | vertex_index, |
||
| 533 | weight_map); |
||
| 534 | } |
||
| 535 | |||
| 536 | |||
| 537 | template<typename Graph, |
||
| 538 | typename CentralityMap, typename EdgeCentralityMap, |
||
| 539 | typename VertexIndexMap> |
||
| 540 | void
|
||
| 541 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion_dispatch2(const Graph& g,
|
| 542 | bool endpoints_inclusion,
|
||
| 543 | d5b7a27f | Quynh PX Nguyen | CentralityMap centrality, |
| 544 | EdgeCentralityMap edge_centrality_map, |
||
| 545 | VertexIndexMap vertex_index) |
||
| 546 | {
|
||
| 547 | typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
|
||
| 548 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
|
||
| 549 | typedef typename mpl::if_c<(is_same<CentralityMap,
|
||
| 550 | dummy_property_map>::value), |
||
| 551 | EdgeCentralityMap, |
||
| 552 | CentralityMap>::type a_centrality_map; |
||
| 553 | typedef typename property_traits<a_centrality_map>::value_type
|
||
| 554 | centrality_type; |
||
| 555 | |||
| 556 | typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); |
||
| 557 | |||
| 558 | std::vector<std::vector<edge_descriptor> > incoming(V); |
||
| 559 | std::vector<centrality_type> distance(V); |
||
| 560 | std::vector<centrality_type> dependency(V); |
||
| 561 | std::vector<degree_size_type> path_count(V); |
||
| 562 | |||
| 563 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion( |
| 564 | d5b7a27f | Quynh PX Nguyen | g, |
| 565 | 33e5ad95 | Quynh PX Nguyen | endpoints_inclusion, |
| 566 | d5b7a27f | Quynh PX Nguyen | centrality, edge_centrality_map, |
| 567 | make_iterator_property_map(incoming.begin(), vertex_index), |
||
| 568 | make_iterator_property_map(distance.begin(), vertex_index), |
||
| 569 | make_iterator_property_map(dependency.begin(), vertex_index), |
||
| 570 | make_iterator_property_map(path_count.begin(), vertex_index), |
||
| 571 | vertex_index); |
||
| 572 | } |
||
| 573 | |||
| 574 | template<typename WeightMap> |
||
| 575 | 33e5ad95 | Quynh PX Nguyen | struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1
|
| 576 | d5b7a27f | Quynh PX Nguyen | {
|
| 577 | template<typename Graph, |
||
| 578 | typename CentralityMap, |
||
| 579 | typename EdgeCentralityMap, typename VertexIndexMap> |
||
| 580 | static void |
||
| 581 | run(const Graph& g,
|
||
| 582 | 33e5ad95 | Quynh PX Nguyen | bool endpoints_inclusion,
|
| 583 | d5b7a27f | Quynh PX Nguyen | CentralityMap centrality, |
| 584 | EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
||
| 585 | WeightMap weight_map) |
||
| 586 | {
|
||
| 587 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g, |
| 588 | endpoints_inclusion, |
||
| 589 | d5b7a27f | Quynh PX Nguyen | centrality, edge_centrality_map, |
| 590 | weight_map, vertex_index); |
||
| 591 | } |
||
| 592 | }; |
||
| 593 | |||
| 594 | template<> |
||
| 595 | 33e5ad95 | Quynh PX Nguyen | struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1<param_not_found>
|
| 596 | d5b7a27f | Quynh PX Nguyen | {
|
| 597 | template<typename Graph, |
||
| 598 | typename CentralityMap, |
||
| 599 | typename EdgeCentralityMap, typename VertexIndexMap> |
||
| 600 | static void |
||
| 601 | run(const Graph& g,
|
||
| 602 | 33e5ad95 | Quynh PX Nguyen | bool endpoints_inclusion,
|
| 603 | d5b7a27f | Quynh PX Nguyen | CentralityMap centrality, |
| 604 | EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
||
| 605 | param_not_found) |
||
| 606 | {
|
||
| 607 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g, |
| 608 | endpoints_inclusion, |
||
| 609 | d5b7a27f | Quynh PX Nguyen | centrality, edge_centrality_map, |
| 610 | vertex_index); |
||
| 611 | } |
||
| 612 | }; |
||
| 613 | |||
| 614 | } } // end namespace detail::graph
|
||
| 615 | |||
| 616 | template<typename Graph, typename Param, typename Tag, typename Rest> |
||
| 617 | void
|
||
| 618 | 33e5ad95 | Quynh PX Nguyen | brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
|
| 619 | bool endpoints_inclusion,
|
||
| 620 | d5b7a27f | Quynh PX Nguyen | const bgl_named_params<Param,Tag,Rest>& params
|
| 621 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) |
||
| 622 | {
|
||
| 623 | typedef bgl_named_params<Param,Tag,Rest> named_params;
|
||
| 624 | |||
| 625 | typedef typename get_param_type<edge_weight_t, named_params>::type ew;
|
||
| 626 | 33e5ad95 | Quynh PX Nguyen | detail::graph::brandes_betweenness_centrality_endpoints_inclusion_dispatch1<ew>::run( |
| 627 | d5b7a27f | Quynh PX Nguyen | g, |
| 628 | 33e5ad95 | Quynh PX Nguyen | endpoints_inclusion, |
| 629 | d5b7a27f | Quynh PX Nguyen | choose_param(get_param(params, vertex_centrality), |
| 630 | dummy_property_map()), |
||
| 631 | choose_param(get_param(params, edge_centrality), |
||
| 632 | dummy_property_map()), |
||
| 633 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
||
| 634 | get_param(params, edge_weight)); |
||
| 635 | } |
||
| 636 | |||
| 637 | 162e1bda | Quynh PX Nguyen | } // end namespace boost
|
| 638 | c6961065 | Quynh PX Nguyen | |
| 639 | d5b7a27f | Quynh PX Nguyen | |
| 640 | c6961065 | Quynh PX Nguyen | #endif //GRAPH_PARSER_CENTRALITY_H |