Revision d5b7a27f custompackages/graph-parser/src/centrality.h

View differences:

custompackages/graph-parser/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 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

  
343 632
} // end namespace boost
344 633

  
634

  
345 635
#endif //GRAPH_PARSER_CENTRALITY_H

Also available in: Unified diff