Revision d5b7a27f custompackages/graphparser/src/centrality.h
custompackages/graphparser/src/centrality.h  

128  128 
divide_centrality_by_two(edges(g), edge_centrality_map); 
129  129 
} 
130  130 
} 
131  
132  
133  
134  131 
} } // end of namespace detail::graph 
135  132  
136  133 
template<typename Graph, 
...  ...  
340  337 
get_param(params, edge_weight)); 
341  338 
} 
342  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  
343  632 
} // end namespace boost 
344  633  
634  
345  635 
#endif //GRAPH_PARSER_CENTRALITY_H 
Also available in: Unified diff