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 |