root / custompackages / graph-parser / src / centrality.h @ 33e5ad95
History | View | Annotate | Download (27.2 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 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 |
dependency_type communication_intensity = get_traffic_matrix_value(g, traffic_matrix, w, *s); // denoted as h in the paper
|
102 |
put(dependency, w, communication_intensity + get(dependency, w)); |
103 |
|
104 |
update_centrality(centrality, *s, communication_intensity); // the number of times s is a source
|
105 |
|
106 |
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 |
//////////////////////////////////////
|
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 |
brandes_betweenness_centrality_endpoints_inclusion_impl(const Graph& g,
|
354 |
bool endpoints_inclusion,
|
355 |
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 |
// cout << ordered_vertices.size() << endl;
|
392 |
update_centrality(centrality, *s, ordered_vertices.size() - 1); // number of times *s is a source |
393 |
|
394 |
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 |
if (endpoints_inclusion) {
|
416 |
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 |
brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
|
443 |
bool endpoints_inclusion,
|
444 |
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 |
detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g, |
456 |
endpoints_inclusion, |
457 |
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 |
brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
|
472 |
bool endpoints_inclusion,
|
473 |
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 |
detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g, |
487 |
endpoints_inclusion, |
488 |
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 |
brandes_betweenness_centrality_endpoints_inclusion_dispatch2(const Graph& g,
|
502 |
bool endpoints_inclusion,
|
503 |
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 |
brandes_betweenness_centrality_endpoints_inclusion( |
525 |
g, |
526 |
endpoints_inclusion, |
527 |
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 |
brandes_betweenness_centrality_endpoints_inclusion_dispatch2(const Graph& g,
|
542 |
bool endpoints_inclusion,
|
543 |
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 |
brandes_betweenness_centrality_endpoints_inclusion( |
564 |
g, |
565 |
endpoints_inclusion, |
566 |
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 |
struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1
|
576 |
{ |
577 |
template<typename Graph, |
578 |
typename CentralityMap, |
579 |
typename EdgeCentralityMap, typename VertexIndexMap> |
580 |
static void |
581 |
run(const Graph& g,
|
582 |
bool endpoints_inclusion,
|
583 |
CentralityMap centrality, |
584 |
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
585 |
WeightMap weight_map) |
586 |
{ |
587 |
brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g, |
588 |
endpoints_inclusion, |
589 |
centrality, edge_centrality_map, |
590 |
weight_map, vertex_index); |
591 |
} |
592 |
}; |
593 |
|
594 |
template<> |
595 |
struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1<param_not_found>
|
596 |
{ |
597 |
template<typename Graph, |
598 |
typename CentralityMap, |
599 |
typename EdgeCentralityMap, typename VertexIndexMap> |
600 |
static void |
601 |
run(const Graph& g,
|
602 |
bool endpoints_inclusion,
|
603 |
CentralityMap centrality, |
604 |
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, |
605 |
param_not_found) |
606 |
{ |
607 |
brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g, |
608 |
endpoints_inclusion, |
609 |
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 |
brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
|
619 |
bool endpoints_inclusion,
|
620 |
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 |
detail::graph::brandes_betweenness_centrality_endpoints_inclusion_dispatch1<ew>::run( |
627 |
g, |
628 |
endpoints_inclusion, |
629 |
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 |
} // end namespace boost
|
638 |
|
639 |
|
640 |
#endif //GRAPH_PARSER_CENTRALITY_H |