Revision 33e5ad95

View differences:

custompackages/graph-parser/src/bi_connected_components.cpp
122 122
    calculate_bc_inter();
123 123

  
124 124
    for (int i = 0; i < num_of_bcc_; ++i) {
125
        // cout << "BC for component " << i << endl;
126 125
        BCCs[i].CalculateBetweennessCentralityHeuristic();
127 126
    }
128 127

  
......
131 130
        // For all points
132 131
        for (string id: BCCs[i].all_vertices_id()) {
133 132
            score = BCCs[i].get_betweenness_centrality(id);
134
            // cout << "XXX score from component << " << i << ", id " << id << " = " << score << endl;
135 133
            bc_score_[id] += score;
136 134
        }
137 135
    }
138 136

  
139
    // // Sum the BC for each sub-component
140
    // for (int i = 0; i < num_of_bcc_; ++i) {
141
    //     // For non articulation points
142
    //     for (string id: BCCs[i].non_art_points_id()) {
143
    //         score = BCCs[i].get_betweenness_centrality(id);
144
    //         bc_score_[id] = score;
145
    //     }
146

  
147
    //     // For articulation points
148
    //     for (string id: BCCs[i].art_points_id()) {
149
    //         score = BCCs[i].get_betweenness_centrality(id);
150
    //         bc_sum_art_points_[id] += score;
151
    //     }
152
    // }
153

  
154 137
    // Update the BC score for articulation points
155 138
    for (string id : all_art_points_id_) {
156
    //     bc_score_[id] = bc_sum_art_points_[id];
157

  
158
        // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
159
        cout << bc_score_[id] << " --> ";
160 139
        bc_score_[id] -= bc_inter_[id];
161
    //     cout << bc_score_[id] << endl;
162 140
    }
163 141

  
164 142
    finalize_betweenness_centrality_heuristic();
......
167 145
}
168 146

  
169 147
// BETWEENNESS CENTRALITY - NORMAL CALCULATION
170
void BiConnectedComponents::CalculateBetweennessCentrality(bool targets_inclusion) {
148
void BiConnectedComponents::CalculateBetweennessCentrality(bool endpoints_inclusion) {
171 149
    initialize_betweenness_centrality();
172 150

  
173 151
    if (gm_.weighted_graph()) { // calculate BC for weighted graph
......
181 159
        BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
182 160
            edge_weight_std_map[edge] = gm_.g_[edge].cost;
183 161
        }
184
        boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_,
185
            targets_inclusion,
162
        boost::brandes_betweenness_centrality_endpoints_inclusion(gm_.g_,
163
            endpoints_inclusion,
186 164
            boost::centrality_map(
187 165
                v_centrality_pmap_).vertex_index_map(
188 166
                gm_.v_index_pmap()).weight_map(
......
190 168
        );
191 169
    }
192 170
    else { // for unweighted graph
193
        boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_,
194
            targets_inclusion,
171
        boost::brandes_betweenness_centrality_endpoints_inclusion(gm_.g_,
172
            endpoints_inclusion,
195 173
            boost::centrality_map(
196 174
                v_centrality_pmap_).vertex_index_map(
197 175
                gm_.v_index_pmap())
......
502 480
            bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id);
503 481
        }
504 482
    }
483

  
484
    if (!gm_.weighted_graph()) {
485
        for (string id : all_art_points_id_) {
486
            bc_inter_[id] /= 2;
487
        }
488
    }
505 489
}
506 490

  
507 491
void BiConnectedComponents::finalize_betweenness_centrality_heuristic() {
custompackages/graph-parser/src/centrality.h
98 98

  
99 99
        // get communication intensity from traffic_matrix
100 100
        // dependency_type communication_intensity = dependency_type(1);
101
        dependency_type communication_intensity = get_traffic_matrix_value(g, traffic_matrix, w, *s);
101
        dependency_type communication_intensity = get_traffic_matrix_value(g, traffic_matrix, w, *s); // denoted as h in the paper
102 102
        put(dependency, w, communication_intensity + get(dependency, w));
103 103

  
104
        update_centrality(centrality, *s, communication_intensity); // the number of times s is a source
105

  
104 106
        dependency_type factor = dependency_type(get(dependency, w))
105 107
          / dependency_type(get(path_count, w));
106 108

  
......
348 350
         typename VertexIndexMap, typename ShortestPaths>
349 351

  
350 352
  void
351
  brandes_betweenness_centrality_targets_inclusion_impl(const Graph& g,
352
                                        bool targets_inclusion,
353
  brandes_betweenness_centrality_endpoints_inclusion_impl(const Graph& g,
354
                                        bool endpoints_inclusion,
353 355
                                        CentralityMap centrality,     // C_B
354 356
                                        EdgeCentralityMap edge_centrality_map,
355 357
                                        IncomingMap incoming, // P
......
386 388
      shortest_paths(g, *s, ordered_vertices, incoming, distance,
387 389
                     path_count, vertex_index);
388 390

  
391
      // cout << ordered_vertices.size() << endl;
392
      update_centrality(centrality, *s, ordered_vertices.size() - 1); // number of times *s is a source
393

  
389 394
      while (!ordered_vertices.empty()) {
390 395
        vertex_descriptor w = ordered_vertices.top();
391 396
        ordered_vertices.pop();
......
407 412
        }
408 413

  
409 414
        if (w != *s) {
410
          if (targets_inclusion) {
415
          if (endpoints_inclusion) {
411 416
            update_centrality(centrality, w, get(dependency, w) + dependency_type(1));
412 417
          }
413 418
          else {
......
434 439
         typename DependencyMap, typename PathCountMap,
435 440
         typename VertexIndexMap>
436 441
void
437
brandes_betweenness_centrality_targets_inclusion(const Graph& g,
438
                               bool targets_inclusion,
442
brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
443
                               bool endpoints_inclusion,
439 444
                               CentralityMap centrality,     // C_B
440 445
                               EdgeCentralityMap edge_centrality_map,
441 446
                               IncomingMap incoming, // P
......
447 452
{
448 453
  detail::graph::brandes_unweighted_shortest_paths shortest_paths;
449 454

  
450
  detail::graph::brandes_betweenness_centrality_targets_inclusion_impl(g,
451
                                                     targets_inclusion,
455
  detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g,
456
                                                     endpoints_inclusion,
452 457
                                                     centrality,
453 458
                                                     edge_centrality_map,
454 459
                                                     incoming, distance,
......
463 468
         typename DependencyMap, typename PathCountMap,
464 469
         typename VertexIndexMap, typename WeightMap>
465 470
void
466
brandes_betweenness_centrality_targets_inclusion(const Graph& g,
467
                               bool targets_inclusion,
471
brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
472
                               bool endpoints_inclusion,
468 473
                               CentralityMap centrality,     // C_B
469 474
                               EdgeCentralityMap edge_centrality_map,
470 475
                               IncomingMap incoming, // P
......
478 483
  detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
479 484
    shortest_paths(weight_map);
480 485

  
481
  detail::graph::brandes_betweenness_centrality_targets_inclusion_impl(g,
482
                                                     targets_inclusion,
486
  detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g,
487
                                                     endpoints_inclusion,
483 488
                                                     centrality,
484 489
                                                     edge_centrality_map,
485 490
                                                     incoming, distance,
......
493 498
           typename CentralityMap, typename EdgeCentralityMap,
494 499
           typename WeightMap, typename VertexIndexMap>
495 500
  void
496
  brandes_betweenness_centrality_targets_inclusion_dispatch2(const Graph& g,
497
                                           bool targets_inclusion,
501
  brandes_betweenness_centrality_endpoints_inclusion_dispatch2(const Graph& g,
502
                                           bool endpoints_inclusion,
498 503
                                           CentralityMap centrality,
499 504
                                           EdgeCentralityMap edge_centrality_map,
500 505
                                           WeightMap weight_map,
......
516 521
    std::vector<centrality_type> dependency(V);
517 522
    std::vector<degree_size_type> path_count(V);
518 523

  
519
    brandes_betweenness_centrality_targets_inclusion(
524
    brandes_betweenness_centrality_endpoints_inclusion(
520 525
      g,
521
      targets_inclusion,
526
      endpoints_inclusion,
522 527
      centrality, edge_centrality_map,
523 528
      make_iterator_property_map(incoming.begin(), vertex_index),
524 529
      make_iterator_property_map(distance.begin(), vertex_index),
......
533 538
           typename CentralityMap, typename EdgeCentralityMap,
534 539
           typename VertexIndexMap>
535 540
  void
536
  brandes_betweenness_centrality_targets_inclusion_dispatch2(const Graph& g,
537
                                           bool targets_inclusion,
541
  brandes_betweenness_centrality_endpoints_inclusion_dispatch2(const Graph& g,
542
                                           bool endpoints_inclusion,
538 543
                                           CentralityMap centrality,
539 544
                                           EdgeCentralityMap edge_centrality_map,
540 545
                                           VertexIndexMap vertex_index)
......
555 560
    std::vector<centrality_type> dependency(V);
556 561
    std::vector<degree_size_type> path_count(V);
557 562

  
558
    brandes_betweenness_centrality_targets_inclusion(
563
    brandes_betweenness_centrality_endpoints_inclusion(
559 564
      g,
560
      targets_inclusion,
565
      endpoints_inclusion,
561 566
      centrality, edge_centrality_map,
562 567
      make_iterator_property_map(incoming.begin(), vertex_index),
563 568
      make_iterator_property_map(distance.begin(), vertex_index),
......
567 572
  }
568 573

  
569 574
  template<typename WeightMap>
570
  struct brandes_betweenness_centrality_targets_inclusion_dispatch1
575
  struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1
571 576
  {
572 577
    template<typename Graph,
573 578
             typename CentralityMap,
574 579
             typename EdgeCentralityMap, typename VertexIndexMap>
575 580
    static void
576 581
    run(const Graph& g,
577
        bool targets_inclusion,
582
        bool endpoints_inclusion,
578 583
        CentralityMap centrality,
579 584
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
580 585
        WeightMap weight_map)
581 586
    {
582
      brandes_betweenness_centrality_targets_inclusion_dispatch2(g,
583
                                               targets_inclusion,
587
      brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g,
588
                                               endpoints_inclusion,
584 589
                                               centrality, edge_centrality_map,
585 590
                                               weight_map, vertex_index);
586 591
    }
587 592
  };
588 593

  
589 594
  template<>
590
  struct brandes_betweenness_centrality_targets_inclusion_dispatch1<param_not_found>
595
  struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1<param_not_found>
591 596
  {
592 597
    template<typename Graph,
593 598
             typename CentralityMap,
594 599
             typename EdgeCentralityMap, typename VertexIndexMap>
595 600
    static void
596 601
    run(const Graph& g,
597
        bool targets_inclusion,
602
        bool endpoints_inclusion,
598 603
        CentralityMap centrality,
599 604
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
600 605
        param_not_found)
601 606
    {
602
      brandes_betweenness_centrality_targets_inclusion_dispatch2(g,
603
                                               targets_inclusion,
607
      brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g,
608
                                               endpoints_inclusion,
604 609
                                               centrality, edge_centrality_map,
605 610
                                               vertex_index);
606 611
    }
......
610 615

  
611 616
template<typename Graph, typename Param, typename Tag, typename Rest>
612 617
void
613
brandes_betweenness_centrality_targets_inclusion(const Graph& g,
614
                               bool targets_inclusion,
618
brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
619
                               bool endpoints_inclusion,
615 620
                               const bgl_named_params<Param,Tag,Rest>& params
616 621
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
617 622
{
618 623
  typedef bgl_named_params<Param,Tag,Rest> named_params;
619 624

  
620 625
  typedef typename get_param_type<edge_weight_t, named_params>::type ew;
621
  detail::graph::brandes_betweenness_centrality_targets_inclusion_dispatch1<ew>::run(
626
  detail::graph::brandes_betweenness_centrality_endpoints_inclusion_dispatch1<ew>::run(
622 627
    g,
623
    targets_inclusion,
628
    endpoints_inclusion,
624 629
    choose_param(get_param(params, vertex_centrality),
625 630
                 dummy_property_map()),
626 631
    choose_param(get_param(params, edge_centrality),
custompackages/graph-parser/src/main.cpp
24 24
    gm.print();
25 25
}
26 26

  
27
void default_run(string filepath, int input_type, bool is_weighted_graph, bool targets_inclusion) {
27
void default_run(string filepath, int input_type, bool is_weighted_graph, bool endpoints_inclusion) {
28 28
    // input_files = [(filepath, input_type)]
29 29
    // input_type = 1 ==> edges file
30 30
    // input_type = 2 ==> simple json file
......
49 49

  
50 50
    // Calculate Betweenness Centrality
51 51
    cout << "Calculate Betweenness Centrality\n";
52
    bcc.CalculateBetweennessCentrality(targets_inclusion);
52
    bcc.CalculateBetweennessCentrality(endpoints_inclusion);
53 53
    // bcc.print();
54 54

  
55 55
    string filename;
......
77 77
    // Example: ./main simple.edges 1 true true
78 78

  
79 79
    bool is_weighted_graph = true;
80
    bool targets_inclusion = true;
80
    bool endpoints_inclusion = true;
81 81
    string filepath;
82 82
    int input_type;
83 83
    string argument;
......
95 95
        if (argc > 4) {
96 96
           argument = string(argv[4]);
97 97
            if (argument.compare("false") == 0) {
98
                targets_inclusion = false;
98
                endpoints_inclusion = false;
99 99
            }
100 100
        }
101 101
    }
102 102

  
103
    default_run(filepath, input_type, is_weighted_graph, targets_inclusion);
103
    default_run(filepath, input_type, is_weighted_graph, endpoints_inclusion);
104 104

  
105 105
    cout << "is weighted graph  = " << is_weighted_graph << endl;
106 106
    return 0;
custompackages/graph-parser/src/plot_BC_comparison.gp
12 12
set ylabel "Betweenness Centrality"
13 13

  
14 14
plot INPUT_FILEPATH using 2 title sprintf('brandes %s (targets inclusion)', SUFFIX) pointtype 5 pointsize 1, \
15
     INPUT_FILEPATH using 3 title sprintf('heuristic %s (not substracted by bc\_inter)', SUFFIX) pointtype 7 pointsize 0.7
15
     INPUT_FILEPATH using 3 title sprintf('heuristic %s (substracted by bc\_inter)', SUFFIX) pointtype 7 pointsize 0.7
custompackages/graph-parser/src/script.sh
1 1
## TUTORIAL:
2 2
## The script take 2 command-line arguments:
3
## $1: input filepath
3
## $1: input folder
4 4
## $2: the type of input file, whether it's *.edges or *.json. Filetype is encoded by integer number 1, 2, 3
5
## $1: specify whether to calculate betweenness centrality as an unweighted graph (false) or weighted graph (true). This argument is for both Heuristic BC and Brandes BC
6
## $2: specify whether to include targets (and only targets, not sources) when calculating betweenness centrality (for the Brandes BC)
5
## $3: specify whether to calculate betweenness centrality as an unweighted graph (false) or weighted graph (true). This argument is for both Heuristic BC and Brandes BC
6
## $4: specify whether to include targets (and only targets, not sources) when calculating betweenness centrality (for the Brandes BC)
7 7

  
8
## If no argument is supplied, then the default is "./script.sh true true"
8
## If no argument is supplied, then the default is "./script.sh ../input/simple.edges 1 true true"
9
## If no argument is supplied, then the default is
10
        # ./script.sh ../input 1 false true
9 11

  
10 12
#########
11 13
## YOU CAN MODIFY THIS PART
12 14
#########
13 15

  
14 16
if [ -z "$1" ]; then
15
    filepath="../input/simple.edges";
17
    inputdir="../input";
16 18
else
17
    filepath="$1";
19
    inputdir="$1";
18 20
fi
19 21

  
20 22
if [ -z "$2" ]; then
......
26 28
# Change the variables to run the Betweenness Centrality for weighted or unweighted graph.
27 29
if [ -z "$3" ] # No argument supplied
28 30
then
29
    WEIGHTED_GRAPH="true"; # 2 possible values: [true | false]
31
    WEIGHTED_GRAPH="false"; # 2 possible values: [true | false]
30 32
else
31 33
    WEIGHTED_GRAPH="$3";
32 34
fi
33 35

  
34 36
if [ -z "$4" ] # No argument supplied
35 37
then
36
   TARGETS_INCLUSION="true"; # 2 possible values: [true | false]
38
   ENDPOINTS_INCLUSION="true"; # 2 possible values: [true | false]
37 39
else
38
    TARGETS_INCLUSION="$4";
40
    ENDPOINTS_INCLUSION="$4";
39 41
fi
40 42

  
41 43
#########
42 44
## TRY TO AVOID MODIFYING ANYTHING BELOW THIS LINE
43 45
#########
44 46
## Compile the source code
47
# rm -f bi_connected_components.o
48
# rm -f sub_component.o
49

  
45 50
make
46 51

  
47 52
## Create output directories if they are not existed
......
55 60
done
56 61

  
57 62
## Running the script
58
./graph-parser $filepath $input_type $WEIGHTED_GRAPH $TARGETS_INCLUSION
63
for file in `ls $inputdir | grep edges`;
64
do
65

  
66
    ./graph-parser ../input/$file $input_type $WEIGHTED_GRAPH $ENDPOINTS_INCLUSION
67
done
68

  
59 69

  
60 70
## Plotting the results
61 71
if [ $WEIGHTED_GRAPH="true" ]
......
67 77
    SUFFIX="unweighted";
68 78
fi
69 79

  
70
## declare an array variables
71
declare -a arr=("simple" "ninux_unweighted_connected" "ninux_30_1" "jsoninfo_topo" "olsr-netjson")
72

  
73
# loop through the array and format the option for gnuplot
74
# gnuplot -e "FILENAME='simple'; SUFFIX='$SUFFIX'" plot_BC_comparison.gp
75
for i in "${arr[@]}"
80
for file in `ls ../output/ | grep out`;
76 81
do
77
    option="FILENAME='"$i"_"$SUFFIX"'; SUFFIX='$SUFFIX'";
82
    filename=${file%.*}
83
    option="FILENAME='$filename'; SUFFIX='$SUFFIX'";
78 84
    gnuplot -e "$option" plot_BC_comparison.gp
79
done
85
done
custompackages/graph-parser/src/simulation.cpp
32 32
    }
33 33
}
34 34

  
35
void calculate_brandes_bc(const GraphManager& gm, bool targets_inclusion) {
35
void calculate_brandes_bc(const GraphManager& gm, bool endpoints_inclusion) {
36 36
    CentralityVec v_centrality_vec = CentralityVec(boost::num_vertices(gm.g_));
37 37
    CentralityPMap v_centrality_pmap = CentralityPMap(v_centrality_vec.begin(), gm.v_index_pmap());;
38 38

  
......
48 48
        BGL_FORALL_EDGES(edge, gm.g_, Graph) {
49 49
            edge_weight_std_map[edge] = gm.g_[edge].cost;
50 50
        }
51
        boost::brandes_betweenness_centrality_targets_inclusion(gm.g_,
52
            targets_inclusion,
51
        boost::brandes_betweenness_centrality_endpoints_inclusion(gm.g_,
52
            endpoints_inclusion,
53 53
            boost::centrality_map(
54 54
                v_centrality_pmap).vertex_index_map(
55 55
                gm.v_index_pmap()).weight_map(
......
57 57
        );
58 58
    }
59 59
    else { // for unweighted graph
60
        boost::brandes_betweenness_centrality_targets_inclusion(gm.g_,
61
            targets_inclusion,
60
        boost::brandes_betweenness_centrality_endpoints_inclusion(gm.g_,
61
            endpoints_inclusion,
62 62
            boost::centrality_map(
63 63
                v_centrality_pmap).vertex_index_map(
64 64
                gm.v_index_pmap())
......
84 84

  
85 85
    // For Brandes BC
86 86
    bc_clock_begin = clock();
87
    bool targets_inclusion = true;
88
    calculate_brandes_bc(gm, targets_inclusion);
87
    bool endpoints_inclusion = true;
88
    calculate_brandes_bc(gm, endpoints_inclusion);
89 89
    bc_clock_end = clock();
90 90

  
91 91
    // For HBC

Also available in: Unified diff