root / custompackages / graphparser / src / centrality.h @ d5b7a27f
History  View  Annotate  Download (26.9 KB)
1 
//


2 
// Created by quynh on 12/15/15.

3 
// The code is mainly from boost/graph/betweenness_centrality.

4 
// I modified the code to work with Traffic Matrix.

5 
//

6  
7 
#ifndef GRAPH_PARSER_CENTRALITY_H

8 
#define GRAPH_PARSER_CENTRALITY_H

9  
10 
#include <fstream> 
11 
#include <iostream> 
12 
#include <boost/graph/betweenness_centrality.hpp> 
13 
#include "common.h" 
14  
15 
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 
// std::cout << "Heuristic Betweenness Centrality Implementation\n";

63  
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 breadthfirst 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 
dependency_type communication_intensity = get_traffic_matrix_value(g, traffic_matrix, w, *s); 
102 
put(dependency, w, communication_intensity + get(dependency, w)); 
103  
104 
dependency_type factor = dependency_type(get(dependency, w)) 
105 
/ dependency_type(get(path_count, w)); 
106  
107 
for (incoming_iterator vw = incoming[w].begin();

108 
vw != incoming[w].end(); ++vw) { 
109 
vertex_descriptor v = source(*vw, g); 
110  
111 
dependency_type new_dependency_value = get(dependency, v) + ( 
112 
dependency_type(get(path_count, v)) * factor); 
113 
put(dependency, v, new_dependency_value); 
114 
update_centrality(edge_centrality_map, *vw, factor); 
115 
} 
116  
117 
if (w != *s) {

118 
update_centrality(centrality, w, get(dependency, w)); 
119 
} 
120 
} 
121 
} 
122  
123 
typedef typename graph_traits<Graph>::directed_category directed_category;

124 
const bool is_undirected = 
125 
is_convertible<directed_category*, undirected_tag*>::value; 
126 
if (is_undirected) {

127 
divide_centrality_by_two(vertices(g), centrality); 
128 
divide_centrality_by_two(edges(g), edge_centrality_map); 
129 
} 
130 
} 
131 
} } // end of namespace detail::graph

132  
133 
template<typename Graph, 
134 
typename TrafficMatrix, 
135 
typename CentralityMap, typename EdgeCentralityMap, 
136 
typename IncomingMap, typename DistanceMap, 
137 
typename DependencyMap, typename PathCountMap, 
138 
typename VertexIndexMap> 
139 
void

140 
brandes_betweenness_centrality_heuristic(const Graph& g,

141 
TrafficMatrix traffic_matrix, 
142 
CentralityMap centrality, // C_B

143 
EdgeCentralityMap edge_centrality_map, 
144 
IncomingMap incoming, // P

145 
DistanceMap distance, // d

146 
DependencyMap dependency, // delta

147 
PathCountMap path_count, // sigma

148 
VertexIndexMap vertex_index 
149 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 
150 
{ 
151 
detail::graph::brandes_unweighted_shortest_paths shortest_paths; 
152  
153 
detail::graph::brandes_betweenness_centrality_heuristic_impl(g, 
154 
traffic_matrix, 
155 
centrality, 
156 
edge_centrality_map, 
157 
incoming, distance, 
158 
dependency, path_count, 
159 
vertex_index, 
160 
shortest_paths); 
161 
} 
162  
163 
template<typename Graph, 
164 
typename TrafficMatrix, 
165 
typename CentralityMap, typename EdgeCentralityMap, 
166 
typename IncomingMap, typename DistanceMap, 
167 
typename DependencyMap, typename PathCountMap, 
168 
typename VertexIndexMap, typename WeightMap> 
169 
void

170 
brandes_betweenness_centrality_heuristic(const Graph& g,

171 
TrafficMatrix traffic_matrix, 
172 
CentralityMap centrality, // C_B

173 
EdgeCentralityMap edge_centrality_map, 
174 
IncomingMap incoming, // P

175 
DistanceMap distance, // d

176 
DependencyMap dependency, // delta

177 
PathCountMap path_count, // sigma

178 
VertexIndexMap vertex_index, 
179 
WeightMap weight_map 
180 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 
181 
{ 
182 
detail::graph::brandes_dijkstra_shortest_paths<WeightMap> 
183 
shortest_paths(weight_map); 
184  
185 
detail::graph::brandes_betweenness_centrality_heuristic_impl(g, 
186 
traffic_matrix, 
187 
centrality, 
188 
edge_centrality_map, 
189 
incoming, distance, 
190 
dependency, path_count, 
191 
vertex_index, 
192 
shortest_paths); 
193 
} 
194  
195 
namespace detail { namespace graph { 
196 
template<typename Graph, 
197 
typename TrafficMatrix, 
198 
typename CentralityMap, typename EdgeCentralityMap, 
199 
typename WeightMap, typename VertexIndexMap> 
200 
void

201 
brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,

202 
TrafficMatrix traffic_matrix, 
203 
CentralityMap centrality, 
204 
EdgeCentralityMap edge_centrality_map, 
205 
WeightMap weight_map, 
206 
VertexIndexMap vertex_index) 
207 
{ 
208 
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;

209 
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

210 
typedef typename mpl::if_c<(is_same<CentralityMap,

211 
dummy_property_map>::value), 
212 
EdgeCentralityMap, 
213 
CentralityMap>::type a_centrality_map; 
214 
typedef typename property_traits<a_centrality_map>::value_type

215 
centrality_type; 
216  
217 
typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); 
218  
219 
std::vector<std::vector<edge_descriptor> > incoming(V); 
220 
std::vector<centrality_type> distance(V); 
221 
std::vector<centrality_type> dependency(V); 
222 
std::vector<degree_size_type> path_count(V); 
223  
224 
brandes_betweenness_centrality_heuristic( 
225 
g, 
226 
traffic_matrix, 
227 
centrality, edge_centrality_map, 
228 
make_iterator_property_map(incoming.begin(), vertex_index), 
229 
make_iterator_property_map(distance.begin(), vertex_index), 
230 
make_iterator_property_map(dependency.begin(), vertex_index), 
231 
make_iterator_property_map(path_count.begin(), vertex_index), 
232 
vertex_index, 
233 
weight_map); 
234 
} 
235  
236  
237 
template<typename Graph, 
238 
typename TrafficMatrix, 
239 
typename CentralityMap, typename EdgeCentralityMap, 
240 
typename VertexIndexMap> 
241 
void

242 
brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,

243 
TrafficMatrix traffic_matrix, 
244 
CentralityMap centrality, 
245 
EdgeCentralityMap edge_centrality_map, 
246 
VertexIndexMap vertex_index) 
247 
{ 
248 
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;

249 
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

250 
typedef typename mpl::if_c<(is_same<CentralityMap,

251 
dummy_property_map>::value), 
252 
EdgeCentralityMap, 
253 
CentralityMap>::type a_centrality_map; 
254 
typedef typename property_traits<a_centrality_map>::value_type

255 
centrality_type; 
256  
257 
typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); 
258  
259 
std::vector<std::vector<edge_descriptor> > incoming(V); 
260 
std::vector<centrality_type> distance(V); 
261 
std::vector<centrality_type> dependency(V); 
262 
std::vector<degree_size_type> path_count(V); 
263  
264 
brandes_betweenness_centrality_heuristic( 
265 
g, 
266 
traffic_matrix, 
267 
centrality, edge_centrality_map, 
268 
make_iterator_property_map(incoming.begin(), vertex_index), 
269 
make_iterator_property_map(distance.begin(), vertex_index), 
270 
make_iterator_property_map(dependency.begin(), vertex_index), 
271 
make_iterator_property_map(path_count.begin(), vertex_index), 
272 
vertex_index); 
273 
} 
274  
275 
template<typename WeightMap> 
276 
struct brandes_betweenness_centrality_heuristic_dispatch1

277 
{ 
278 
template<typename Graph, 
279 
typename TrafficMatrix, 
280 
typename CentralityMap, 
281 
typename EdgeCentralityMap, typename VertexIndexMap> 
282 
static void 
283 
run(const Graph& g,

284 
TrafficMatrix traffic_matrix, 
285 
CentralityMap centrality, 
286 
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, 
287 
WeightMap weight_map) 
288 
{ 
289 
brandes_betweenness_centrality_heuristic_dispatch2(g, 
290 
traffic_matrix, 
291 
centrality, edge_centrality_map, 
292 
weight_map, vertex_index); 
293 
} 
294 
}; 
295  
296 
template<> 
297 
struct brandes_betweenness_centrality_heuristic_dispatch1<param_not_found>

298 
{ 
299 
template<typename Graph, 
300 
typename TrafficMatrix, 
301 
typename CentralityMap, 
302 
typename EdgeCentralityMap, typename VertexIndexMap> 
303 
static void 
304 
run(const Graph& g,

305 
TrafficMatrix traffic_matrix, 
306 
CentralityMap centrality, 
307 
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, 
308 
param_not_found) 
309 
{ 
310 
brandes_betweenness_centrality_heuristic_dispatch2(g, 
311 
traffic_matrix, 
312 
centrality, edge_centrality_map, 
313 
vertex_index); 
314 
} 
315 
}; 
316  
317 
} } // end namespace detail::graph

318  
319 
template<typename Graph, typename TrafficMatrix, typename Param, typename Tag, typename Rest> 
320 
void

321 
brandes_betweenness_centrality_heuristic(const Graph& g,

322 
TrafficMatrix traffic_matrix, 
323 
const bgl_named_params<Param,Tag,Rest>& params

324 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 
325 
{ 
326 
typedef bgl_named_params<Param,Tag,Rest> named_params;

327  
328 
typedef typename get_param_type<edge_weight_t, named_params>::type ew;

329 
detail::graph::brandes_betweenness_centrality_heuristic_dispatch1<ew>::run( 
330 
g, 
331 
traffic_matrix, 
332 
choose_param(get_param(params, vertex_centrality), 
333 
dummy_property_map()), 
334 
choose_param(get_param(params, edge_centrality), 
335 
dummy_property_map()), 
336 
choose_const_pmap(get_param(params, vertex_index), g, vertex_index), 
337 
get_param(params, edge_weight)); 
338 
} 
339  
340 
//////////////////////////////////////

341 
// BGL Modification: TARGETS INCLUSION

342 
//////////////////////////////////////

343  
344 
namespace detail { namespace graph { 
345 
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 
346 
typename IncomingMap, typename DistanceMap, 
347 
typename DependencyMap, typename PathCountMap, 
348 
typename VertexIndexMap, typename ShortestPaths> 
349  
350 
void

351 
brandes_betweenness_centrality_targets_inclusion_impl(const Graph& g,

352 
bool targets_inclusion,

353 
CentralityMap centrality, // C_B

354 
EdgeCentralityMap edge_centrality_map, 
355 
IncomingMap incoming, // P

356 
DistanceMap distance, // d

357 
DependencyMap dependency, // delta

358 
PathCountMap path_count, // sigma

359 
VertexIndexMap vertex_index, 
360 
ShortestPaths shortest_paths) 
361 
{ 
362 
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

363 
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

364  
365 
cout << "@@@ Targets Inclusion @@@\n";

366  
367 
// Initialize centrality

368 
init_centrality_map(vertices(g), centrality); 
369 
init_centrality_map(edges(g), edge_centrality_map); 
370  
371 
std::stack<vertex_descriptor> ordered_vertices; 
372 
vertex_iterator s, s_end; 
373 
for (boost::tie(s, s_end) = vertices(g); s != s_end; ++s) {

374 
// Initialize for this iteration

375 
vertex_iterator w, w_end; 
376 
for (boost::tie(w, w_end) = vertices(g); w != w_end; ++w) {

377 
incoming[*w].clear(); 
378 
put(path_count, *w, 0);

379 
put(dependency, *w, 0);

380 
} 
381 
put(path_count, *s, 1);

382  
383 
// Execute the shortest paths algorithm. This will be either

384 
// Dijkstra's algorithm or a customized breadthfirst search,

385 
// depending on whether the graph is weighted or unweighted.

386 
shortest_paths(g, *s, ordered_vertices, incoming, distance, 
387 
path_count, vertex_index); 
388  
389 
while (!ordered_vertices.empty()) {

390 
vertex_descriptor w = ordered_vertices.top(); 
391 
ordered_vertices.pop(); 
392  
393 
typedef typename property_traits<IncomingMap>::value_type

394 
incoming_type; 
395 
typedef typename incoming_type::iterator incoming_iterator;

396 
typedef typename property_traits<DependencyMap>::value_type

397 
dependency_type; 
398  
399 
for (incoming_iterator vw = incoming[w].begin();

400 
vw != incoming[w].end(); ++vw) { 
401 
vertex_descriptor v = source(*vw, g); 
402 
dependency_type factor = dependency_type(get(path_count, v)) 
403 
/ dependency_type(get(path_count, w)); 
404 
factor *= (dependency_type(1) + get(dependency, w));

405 
put(dependency, v, get(dependency, v) + factor); 
406 
update_centrality(edge_centrality_map, *vw, factor); 
407 
} 
408  
409 
if (w != *s) {

410 
if (targets_inclusion) {

411 
update_centrality(centrality, w, get(dependency, w) + dependency_type(1));

412 
} 
413 
else {

414 
update_centrality(centrality, w, get(dependency, w)); 
415 
} 
416 
} 
417 
} 
418 
} 
419  
420 
typedef typename graph_traits<Graph>::directed_category directed_category;

421 
const bool is_undirected = 
422 
is_convertible<directed_category*, undirected_tag*>::value; 
423 
if (is_undirected) {

424 
divide_centrality_by_two(vertices(g), centrality); 
425 
divide_centrality_by_two(edges(g), edge_centrality_map); 
426 
} 
427 
} 
428  
429 
} } // end namespace detail::graph

430  
431 
template<typename Graph, 
432 
typename CentralityMap, typename EdgeCentralityMap, 
433 
typename IncomingMap, typename DistanceMap, 
434 
typename DependencyMap, typename PathCountMap, 
435 
typename VertexIndexMap> 
436 
void

437 
brandes_betweenness_centrality_targets_inclusion(const Graph& g,

438 
bool targets_inclusion,

439 
CentralityMap centrality, // C_B

440 
EdgeCentralityMap edge_centrality_map, 
441 
IncomingMap incoming, // P

442 
DistanceMap distance, // d

443 
DependencyMap dependency, // delta

444 
PathCountMap path_count, // sigma

445 
VertexIndexMap vertex_index 
446 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 
447 
{ 
448 
detail::graph::brandes_unweighted_shortest_paths shortest_paths; 
449  
450 
detail::graph::brandes_betweenness_centrality_targets_inclusion_impl(g, 
451 
targets_inclusion, 
452 
centrality, 
453 
edge_centrality_map, 
454 
incoming, distance, 
455 
dependency, path_count, 
456 
vertex_index, 
457 
shortest_paths); 
458 
} 
459  
460 
template<typename Graph, 
461 
typename CentralityMap, typename EdgeCentralityMap, 
462 
typename IncomingMap, typename DistanceMap, 
463 
typename DependencyMap, typename PathCountMap, 
464 
typename VertexIndexMap, typename WeightMap> 
465 
void

466 
brandes_betweenness_centrality_targets_inclusion(const Graph& g,

467 
bool targets_inclusion,

468 
CentralityMap centrality, // C_B

469 
EdgeCentralityMap edge_centrality_map, 
470 
IncomingMap incoming, // P

471 
DistanceMap distance, // d

472 
DependencyMap dependency, // delta

473 
PathCountMap path_count, // sigma

474 
VertexIndexMap vertex_index, 
475 
WeightMap weight_map 
476 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 
477 
{ 
478 
detail::graph::brandes_dijkstra_shortest_paths<WeightMap> 
479 
shortest_paths(weight_map); 
480  
481 
detail::graph::brandes_betweenness_centrality_targets_inclusion_impl(g, 
482 
targets_inclusion, 
483 
centrality, 
484 
edge_centrality_map, 
485 
incoming, distance, 
486 
dependency, path_count, 
487 
vertex_index, 
488 
shortest_paths); 
489 
} 
490  
491 
namespace detail { namespace graph { 
492 
template<typename Graph, 
493 
typename CentralityMap, typename EdgeCentralityMap, 
494 
typename WeightMap, typename VertexIndexMap> 
495 
void

496 
brandes_betweenness_centrality_targets_inclusion_dispatch2(const Graph& g,

497 
bool targets_inclusion,

498 
CentralityMap centrality, 
499 
EdgeCentralityMap edge_centrality_map, 
500 
WeightMap weight_map, 
501 
VertexIndexMap vertex_index) 
502 
{ 
503 
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;

504 
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

505 
typedef typename mpl::if_c<(is_same<CentralityMap,

506 
dummy_property_map>::value), 
507 
EdgeCentralityMap, 
508 
CentralityMap>::type a_centrality_map; 
509 
typedef typename property_traits<a_centrality_map>::value_type

510 
centrality_type; 
511  
512 
typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); 
513  
514 
std::vector<std::vector<edge_descriptor> > incoming(V); 
515 
std::vector<centrality_type> distance(V); 
516 
std::vector<centrality_type> dependency(V); 
517 
std::vector<degree_size_type> path_count(V); 
518  
519 
brandes_betweenness_centrality_targets_inclusion( 
520 
g, 
521 
targets_inclusion, 
522 
centrality, edge_centrality_map, 
523 
make_iterator_property_map(incoming.begin(), vertex_index), 
524 
make_iterator_property_map(distance.begin(), vertex_index), 
525 
make_iterator_property_map(dependency.begin(), vertex_index), 
526 
make_iterator_property_map(path_count.begin(), vertex_index), 
527 
vertex_index, 
528 
weight_map); 
529 
} 
530  
531  
532 
template<typename Graph, 
533 
typename CentralityMap, typename EdgeCentralityMap, 
534 
typename VertexIndexMap> 
535 
void

536 
brandes_betweenness_centrality_targets_inclusion_dispatch2(const Graph& g,

537 
bool targets_inclusion,

538 
CentralityMap centrality, 
539 
EdgeCentralityMap edge_centrality_map, 
540 
VertexIndexMap vertex_index) 
541 
{ 
542 
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;

543 
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

544 
typedef typename mpl::if_c<(is_same<CentralityMap,

545 
dummy_property_map>::value), 
546 
EdgeCentralityMap, 
547 
CentralityMap>::type a_centrality_map; 
548 
typedef typename property_traits<a_centrality_map>::value_type

549 
centrality_type; 
550  
551 
typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); 
552  
553 
std::vector<std::vector<edge_descriptor> > incoming(V); 
554 
std::vector<centrality_type> distance(V); 
555 
std::vector<centrality_type> dependency(V); 
556 
std::vector<degree_size_type> path_count(V); 
557  
558 
brandes_betweenness_centrality_targets_inclusion( 
559 
g, 
560 
targets_inclusion, 
561 
centrality, edge_centrality_map, 
562 
make_iterator_property_map(incoming.begin(), vertex_index), 
563 
make_iterator_property_map(distance.begin(), vertex_index), 
564 
make_iterator_property_map(dependency.begin(), vertex_index), 
565 
make_iterator_property_map(path_count.begin(), vertex_index), 
566 
vertex_index); 
567 
} 
568  
569 
template<typename WeightMap> 
570 
struct brandes_betweenness_centrality_targets_inclusion_dispatch1

571 
{ 
572 
template<typename Graph, 
573 
typename CentralityMap, 
574 
typename EdgeCentralityMap, typename VertexIndexMap> 
575 
static void 
576 
run(const Graph& g,

577 
bool targets_inclusion,

578 
CentralityMap centrality, 
579 
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, 
580 
WeightMap weight_map) 
581 
{ 
582 
brandes_betweenness_centrality_targets_inclusion_dispatch2(g, 
583 
targets_inclusion, 
584 
centrality, edge_centrality_map, 
585 
weight_map, vertex_index); 
586 
} 
587 
}; 
588  
589 
template<> 
590 
struct brandes_betweenness_centrality_targets_inclusion_dispatch1<param_not_found>

591 
{ 
592 
template<typename Graph, 
593 
typename CentralityMap, 
594 
typename EdgeCentralityMap, typename VertexIndexMap> 
595 
static void 
596 
run(const Graph& g,

597 
bool targets_inclusion,

598 
CentralityMap centrality, 
599 
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, 
600 
param_not_found) 
601 
{ 
602 
brandes_betweenness_centrality_targets_inclusion_dispatch2(g, 
603 
targets_inclusion, 
604 
centrality, edge_centrality_map, 
605 
vertex_index); 
606 
} 
607 
}; 
608  
609 
} } // end namespace detail::graph

610  
611 
template<typename Graph, typename Param, typename Tag, typename Rest> 
612 
void

613 
brandes_betweenness_centrality_targets_inclusion(const Graph& g,

614 
bool targets_inclusion,

615 
const bgl_named_params<Param,Tag,Rest>& params

616 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 
617 
{ 
618 
typedef bgl_named_params<Param,Tag,Rest> named_params;

619  
620 
typedef typename get_param_type<edge_weight_t, named_params>::type ew;

621 
detail::graph::brandes_betweenness_centrality_targets_inclusion_dispatch1<ew>::run( 
622 
g, 
623 
targets_inclusion, 
624 
choose_param(get_param(params, vertex_centrality), 
625 
dummy_property_map()), 
626 
choose_param(get_param(params, edge_centrality), 
627 
dummy_property_map()), 
628 
choose_const_pmap(get_param(params, vertex_index), g, vertex_index), 
629 
get_param(params, edge_weight)); 
630 
} 
631  
632 
} // end namespace boost

633  
634  
635 
#endif //GRAPH_PARSER_CENTRALITY_H 