## root / custompackages / graph-parser / src / centrality.h @ d5b7a27f

History | View | Annotate | Download (26.9 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 | 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 | d5b7a27f | Quynh PX Nguyen | ```
//////////////////////////////////////
``` |

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 breadth-first 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 | 162e1bda | Quynh PX Nguyen | ```
} // end namespace boost
``` |

633 | c6961065 | Quynh PX Nguyen | |

634 | d5b7a27f | Quynh PX Nguyen | |

635 | c6961065 | Quynh PX Nguyen | #endif //GRAPH_PARSER_CENTRALITY_H |