Revision 162e1bda

View differences:

custompackages/graph-parser/src/bi_connected_components.cpp
18 18
    // Set some variables
19 19
    num_of_vertices_ = boost::num_vertices(gm_.g_);
20 20

  
21
    component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0);
21
    component_vec_ = ComponentVec(boost::num_edges(gm_.g_), -1);
22 22
    component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap());
23 23
}
24 24

  
......
44 44
    return bc_score_;
45 45
}
46 46

  
47
/* SUB-COMPONENT */
48
void BiConnectedComponents::FindBiConnectedComponents() {
49
    cout << "Running FindBiConnectedComponents" << endl;
50

  
51
    boost::biconnected_components(gm_.g_, component_map_,
52
                                  back_inserter(art_points_),
53
                                  boost::vertex_index_map(gm_.v_index_pmap()));
47
NameToDoubleMap const& BiConnectedComponents::bc_relative_score() const {
48
    return bc_relative_score_;
49
}
54 50

  
55
    // Set some variables
56
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
51
// AUTO RUN
52
void BiConnectedComponents::run() {
53
    /* Auto run all the necessary functions
54
    */
55
    FindBiConnectedComponents();
57 56

  
58
    // Process the result from boost::biconnected_components
59
    BCCs = Component_t(num_of_bcc());
60
    CreateSubComponents();
57
    cout << "All Sub Components:\n\n";
58
    for (int i = 0; i < num_of_bcc_; ++i) {
59
        cout << "    " << i << endl;
60
        outops::operator<<(cout, BCCs[i].all_vertices_id());
61
    }
61 62

  
62
    // Calculate Link Weight
63
    cout << "Calculate Link Weight\n";
63
    // Calculate Link Weight + Link Weight Reversed
64
    cout << "Calculate Link Weight + Link Weight Reversed\n";
64 65
    CalculateLinkWeight();
66
    CalculateLinkWeightReversed();
67
    verify_link_weight();
65 68

  
66 69
    // Calculate Traffic Matrix
67 70
    cout << "Calculate Traffic Matrix\n";
68 71
    CalculateTrafficMatrix();
69 72

  
73
    // Calculate Betweenness Centrality Heuristic
74
    cout << "Calculate Betweenness Centrality Heuristic\n";
75
    CalculateBetweennessCentralityHeuristic();
76

  
70 77
    // Calculate Betweenness Centrality
71 78
    cout << "Calculate Betweenness Centrality\n";
72 79
    CalculateBetweennessCentrality();
73

  
74
    // Print all the sub components
75
    print();
76 80
}
77 81

  
78
void BiConnectedComponents::CreateSubComponents() {
79
    // Generating subgraph for each sub-component
80
    BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
81
        int comp_index = boost::get(component_map_, edge);
82
        Router r1 = gm_.g_[boost::source(edge, gm_.g_)];
83
        Router r2 = gm_.g_[boost::target(edge, gm_.g_)];
84
        Link l = gm_.g_[edge];
85
        BCCs[comp_index].AddEdge(r1, r2, l);
86
    }
82
// SUB-COMPONENT
83
void BiConnectedComponents::FindBiConnectedComponents() {
84
    cout << "Running FindBiConnectedComponents" << endl;
87 85

  
88
    // Finalizing each sub components
89
    for (int i = 0; i < num_of_bcc(); ++i) {
90
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
91
    }
86
    boost::biconnected_components(gm_.g_, component_map_,
87
                                  back_inserter(art_points_),
88
                                  boost::vertex_index_map(gm_.v_index_pmap()));
89

  
90
    // Set some variables
91
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
92

  
93
    cout << "\nArticulation points:\n";
94
    outops::operator<<(cout, all_art_points_id_);
95

  
96
    // Process the result from boost::biconnected_components
97
    cout << "Create Sub Components\n";
98
    BCCs = Component_t(num_of_bcc());
99
    CreateSubComponents();
92 100
}
93 101

  
94
/* LINK WEIGHT */
102
// LINK WEIGHT
95 103
void BiConnectedComponents::CalculateLinkWeight() {
96 104
    initialize_weight();
97 105
    initialize_queue();
......
113 121
    }
114 122
}
115 123

  
116
/* TRAFFIC MATRIX */
124
void BiConnectedComponents::CalculateLinkWeightReversed() {
125
    for (int i = 0; i < num_of_bcc_; ++i) {
126
        BCCs[i].calculate_weight_reversed(num_of_vertices_);
127
    }
128
}
129

  
130
// TRAFFIC MATRIX
117 131
void BiConnectedComponents::CalculateTrafficMatrix() {
118 132
    for (int i = 0; i < num_of_bcc_; ++i) {
119 133
        BCCs[i].CalculateTrafficMatrix();
120 134
    }
121 135
}
122 136

  
123
/* BETWEENNESS CENTRALITY */
124
void BiConnectedComponents::CalculateBetweennessCentrality() {
125
    cout << "BETWEENNESS CENTRALITY\n";
137
// BETWEENNESS CENTRALITY HEURISTIC
138
void BiConnectedComponents::CalculateBetweennessCentralityHeuristic() {
139
    cout << "BETWEENNESS CENTRALITY HEURISTIC\n";
126 140

  
127
    initialize_betweenness_centrality();
141
    initialize_betweenness_centrality_heuristic();
142
    calculate_bc_inter();
128 143

  
129 144
    for (int i = 0; i < num_of_bcc_; ++i) {
130 145
        cout << "BC for component " << i << endl;
131
        BCCs[i].CalculateBetweennessCentrality();
146
        BCCs[i].CalculateBetweennessCentralityHeuristic();
132 147
    }
133 148

  
134 149
    double score;
135
    // Sum the BC for each sub-component
136 150
    for (int i = 0; i < num_of_bcc_; ++i) {
137
        // For non articulation points
138
        for (string id: BCCs[i].non_art_points_id()) {
151
        // For all points
152
        for (string id: BCCs[i].all_vertices_id()) {
139 153
            score = BCCs[i].get_betweenness_centrality(id);
140
            cout << "id = " << id << ", score = " << score << endl;
141
            bc_score_[id] = score;
142
        }
143

  
144
        // For articulation points
145
        for (string id: BCCs[i].art_points_id()) {
146
            score = BCCs[i].get_betweenness_centrality(id);
147
            bc_sum_art_points_[id] += score;
154
            cout << "XXX score from component << " << i << ", id " << id << " = " << score << endl;
155
            bc_score_[id] += score;
148 156
        }
149 157
    }
150 158

  
151
    // Update the BC score for articulation points
159
    // // Sum the BC for each sub-component
160
    // for (int i = 0; i < num_of_bcc_; ++i) {
161
    //     // For non articulation points
162
    //     for (string id: BCCs[i].non_art_points_id()) {
163
    //         score = BCCs[i].get_betweenness_centrality(id);
164
    //         bc_score_[id] = score;
165
    //     }
166

  
167
    //     // For articulation points
168
    //     for (string id: BCCs[i].art_points_id()) {
169
    //         score = BCCs[i].get_betweenness_centrality(id);
170
    //         bc_sum_art_points_[id] += score;
171
    //     }
172
    // }
173

  
174
    // // Update the BC score for articulation points
152 175
    for (string id : all_art_points_id_) {
153
        bc_score_[id] = bc_sum_art_points_[id];
176
    //     bc_score_[id] = bc_sum_art_points_[id];
154 177

  
155 178
        // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
156
        // bc_score_[id] = bc_sum_art_points_[id] - bc_inter_[id];
179
        cout << bc_score_[id] << " --> ";
180
        bc_score_[id] -= bc_inter_[id];
181
        cout << bc_score_[id] << endl;
157 182
    }
158 183

  
184
    finalize_betweenness_centrality_heuristic();
185

  
159 186
    cout << "DONE WITH BETWEENNESS CENTRALITY\n";
160 187
}
161 188

  
162
void BiConnectedComponents::initialize_betweenness_centrality() {
163
    // Initialize bc_inter_ to be 0
164
    for (string id: all_art_points_id_) {
165
        bc_inter_[id] = 0;
166
    }
189
// BETWEENNESS CENTRALITY - NORMAL CALCULATION
190
void BiConnectedComponents::CalculateBetweennessCentrality() {
191
    initialize_betweenness_centrality();
167 192

  
168
    StringSet all_vertices_id;
169
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id);
193
    boost::brandes_betweenness_centrality(gm_.g_,
194
        boost::centrality_map(
195
            v_centrality_pmap_).vertex_index_map(
196
            gm_.v_index_pmap())
197
    );
170 198

  
171
    // Initialize bc_sum_, bc_score_ to be 0
172
    for (string id: all_vertices_id) {
173
        bc_sum_art_points_[id] = 0;
174
        bc_score_[id] = 0;
199
    boost::relative_betweenness_centrality(gm_.g_, v_centrality_pmap_);
200
}
201

  
202

  
203
// HELPERS FOR OUTPUTTING RESULT
204
void BiConnectedComponents::print_all_sub_components() {
205
    for (int i = 0; i < num_of_bcc(); ++i) {
206
        // cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout
207
        BCCs[i].print();
175 208
    }
176 209
}
177 210

  
178
void BiConnectedComponents::calculate_bc_inter() {
179
    for (int i = 0; i < num_of_bcc_; ++i) {
180
        for (string id : BCCs[i].art_points_id()) {
181
            bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id);
182
        }
211
void BiConnectedComponents::print_betweenness_centrality() {
212
    BGL_FORALL_VERTICES(v, gm_.g_, Graph) {
213
        double bc_score = boost::get(v_centrality_pmap_, v);
214
        cout << gm_.g_[v].id << ": " << bc_score << endl;
183 215
    }
184 216
}
185 217

  
186
/* HELPERS FOR OUTPUTTING RESULT */
218
void BiConnectedComponents::print_betweenness_centrality_heuristic() {
219
    outops::operator<< <double>(cout, bc_relative_score_);
220
}
221

  
222
void BiConnectedComponents::write_all_betweenness_centrality(string filepath) {
223
    /* Write the heuristic and the normal version of betweenness centrality
224
    1st column: brandes_betweenness_centrality
225
    2nd column: heuristic_betweenness_centrality
226
    */
187 227

  
188
void BiConnectedComponents::print() {
189
    for (int i = 0; i < num_of_bcc(); ++i) {
190
        // cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout
191
        BCCs[i].print();
228
    vector<pair<string, double> > mapcopy(bc_relative_score_.begin(), bc_relative_score_.end());
229
    std::sort(mapcopy.begin(), mapcopy.end(), less_second<string, double>());
230

  
231
    ofstream outFile(filepath.c_str());
232

  
233
    Viter vi, ve;
234
    size_t i = 0;
235
    if (outFile.is_open()) {
236
        for(auto id_bc_score_pair : mapcopy) {
237
            string id = id_bc_score_pair.first;
238
            double heuristic_bc_score = id_bc_score_pair.second;
239

  
240
            int index = gm_.get_index_from_id(id);
241
            double bc_score = v_centrality_vec_.at(index);
242

  
243
            outFile << id << "\t" << bc_score << "\t" << heuristic_bc_score << endl;
244
        }
245
        // for (boost::tie(vi, ve) = boost::vertices(gm_.g_); vi != ve; ++vi) {
246
        //     string id = gm_.g_[*vi].id;
247
        //     outFile << id << "\t" << bc_relative_score_[id] << "\t" << v_centrality_vec_.at(i) << endl;
248
        //     ++i;
249
        // }
192 250
    }
251
    outFile.close();
252
    cout << "Finish writing brandes and heurisic BC score to file " << filepath << endl;
253
}
254

  
255
void BiConnectedComponents::print() {
256
    cout << "\n\nBi-Connected Components\n\n";
257
    cout << gm_;
258

  
259
    cout << "\nArticulation points:\n";
260
    outops::operator<<(cout, all_art_points_id_);
261

  
262
    cout << "\nHeuristic Betweenness Centrality Score:\n";
263
    outops::operator<< <double>(cout, bc_score_);
264

  
265
    cout << "\nHeuristic Betweenness Centrality Relative Score:\n";
266
    outops::operator<< <double>(cout, bc_relative_score_);
267

  
268
    cout << "\nNormal Betweenness Centrality Score:\n";
269
    print_betweenness_centrality();
270

  
271
    cout << "Special debugging case\n";
272
    BCCs[71].print();
193 273
}
194 274

  
195 275
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
196
    cout << "MARK\n";
197 276
    cout << "\n\nBi-Connected Components\n\n";
198 277
    cout << rhs.gm_;
199 278

  
200 279
    cout << "\nArticulation points:\n";
201 280
    outops::operator<<(cout, rhs.all_art_points_id());
202 281

  
203
    cout << "\nBetweenness Centrality Score:\n";
282
    cout << "\nHeuristic Betweenness Centrality Score:\n";
204 283
    outops::operator<< <double>(cout, rhs.bc_score());
205
    return os;
206 284

  
207
    // TODO: output the result of BCC
208
    // Test the biconnected components
209
    // Eiter ei, ei_end;
210
    // size_t i = 0;
211
    // for (boost::tie(ei, ei_end) = boost::edges(gm_.g_); ei != ei_end; ++ei) {
212
    //     string source = gm_.g_[(*ei).m_source].id;
213
    //     string target = gm_.g_[(*ei).m_target].id;
214
    //     edges_size_type comp = component_vec_.at(i);
215
    //     cout << source << " " << target << " " << comp << endl;
216
    //     ++i;
217
    // }
285
    cout << "\nHeuristic Betweenness Centrality Relative Score:\n";
286
    outops::operator<< <double>(cout, rhs.bc_relative_score());
287

  
288
    return os;
218 289
}
219 290

  
220 291
/******************************
221 292
* Private functions
222 293
******************************/
294
// SUB-COMPONENT
295
void BiConnectedComponents::CreateSubComponents() {
296
    // Generating subgraph for each sub-component
297
    BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
298
        Vertex source = boost::source(edge, gm_.g_);
299
        Vertex target = boost::target(edge, gm_.g_);
300

  
301
        int comp_index = boost::get(component_map_, edge);
302
        cout << comp_index << endl;
303
        if (comp_index == -1) {
304
            cout << "ERROR: edge ";
305
            graphext::print_edge(gm_.g_, edge);
306
            cout << "not belonging to subcomponent\n";
307
        }
308
        else {
309
            Router r1 = gm_.g_[source];
310
            Router r2 = gm_.g_[target];
311
            Link l = gm_.g_[edge];
312
            BCCs[comp_index].AddEdge(r1, r2, l);
313
        }
314
    }
315

  
316
    // Finalizing each sub components
317
    for (int i = 0; i < num_of_bcc(); ++i) {
318
        BCCs[i].FinalizeSubComponent(all_art_points_id_);
319
    }
320
}
223 321

  
224
/* LINK WEIGHT */
322
// LINK WEIGHT
225 323
void BiConnectedComponents::initialize_weight() {
226 324
    for (int i = 0; i < num_of_bcc_; ++i) {
227 325
        BCCs[i].initialize_weight();
......
230 328

  
231 329
void BiConnectedComponents::initialize_queue() {
232 330
    for (int i = 0; i < num_of_bcc_; ++i) {
331
        if (BCCs[i].vertex_exists("43")) {
332
            cout << "### 43 ###\n";
333
            outops::operator<<(cout, BCCs[i].all_vertices_id());
334
        }
233 335
        if (BCCs[i].art_points_id().size() == 1) {
234 336
            string vertex_id = *(BCCs[i].art_points_id().begin());
235 337
            string type = "component_vertex_pair";
......
238 340
                .vertex_id = vertex_id,
239 341
                .type = type,
240 342
            };
241

  
343
            cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";
242 344
            Q.push(elem);
243 345
        }
244 346
    }
......
255 357
        }
256 358
    }
257 359
    int link_weight = size;
360

  
361
    int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);
362
    if (old_link_weight != -1) {
363
        if (link_weight != old_link_weight) {
364
            cout << "ERROR in Link Weight for vertex " << vertex_id << old_link_weight << " | " << link_weight << endl;
365
        }
366
    }
367

  
258 368
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
259 369
    find_unknown_weight_wrt_art_point(vertex_id);
260 370
}
......
262 372
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) {
263 373
    int count = 0;
264 374
    int comp_index = -1;
375
    cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n";
376

  
265 377
    for (int i = 0; i < num_of_bcc_; ++i) {
266 378
        if (BCCs[i].vertex_exists(vertex_id)) {
267 379
            if (BCCs[i].get_weight_map(vertex_id) == -1) {
380
                cout << "     comp_index = " << i << endl;
268 381
                ++count;
269 382
                comp_index = i;
270 383
            }
......
281 394
            .type = "vertex_component_pair"
282 395
        };
283 396

  
284
        // cout << "Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
397
        cout << "        Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
285 398
        Q.push(elem);
286 399
    }
287 400
}
......
301 414
    }
302 415

  
303 416
    int link_weight = num_of_vertices_ - 1 - size;
417

  
418
    int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);
419
    if (old_link_weight != -1) {
420
        if (link_weight != old_link_weight) {
421
            cout << "ERROR in Link Weight for vertex " << vertex_id << old_link_weight << " | " << link_weight << endl;
422
        }
423
    }
424

  
304 425
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
305 426
    find_unknown_weight_wrt_component(comp_index);
306 427
}
......
322 443
            .vertex_id = vertex_id,
323 444
            .type = "component_vertex_pair",
324 445
        };
325
        // cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
446
        cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
326 447
        Q.push(elem);
327 448
    }
449
}
450

  
451
bool BiConnectedComponents::verify_link_weight() {
452
    // Returns True if there is no negative value in Link Weight
453
    bool result = true;
454

  
455
    for (int i = 0; i < num_of_bcc_; ++i) {
456
        for (string id : BCCs[i].art_points_id()) {
457
            if (BCCs[i].get_weight_map(id) == -1) {
458
                cout << "ERROR Link Weight for vertex " << id << " = " << -1 << endl;
459
                result = false;
460
            }
461
        }
462
    }
463
}
464

  
465
// BETWEENNESS CENTRALITY - HEURISTIC
466
void BiConnectedComponents::initialize_betweenness_centrality_heuristic() {
467
    // Initialize bc_inter_ to be 0
468
    for (string id: all_art_points_id_) {
469
        bc_inter_[id] = 0;
470
    }
471

  
472
    StringSet all_vertices_id;
473
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id);
474

  
475
    // Initialize bc_sum_, bc_score_ to be 0
476
    for (string id: all_vertices_id) {
477
        bc_sum_art_points_[id] = 0;
478
        bc_score_[id] = 0;
479
    }
480
}
481

  
482
void BiConnectedComponents::calculate_bc_inter() {
483
    for (int i = 0; i < num_of_bcc_; ++i) {
484
        for (string id : BCCs[i].art_points_id()) {
485
            bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id);
486
        }
487
    }
488
}
489

  
490
void BiConnectedComponents::finalize_betweenness_centrality_heuristic() {
491
    // Divide the bc_score_ by some factor
492
    int n = num_of_vertices();
493
    double factor = 2.0 / (n*n - 3*n + 2);
494
    NameToDoubleMap::iterator iter;
495
    for (iter = bc_score_.begin(); iter != bc_score_.end(); ++iter) {
496
        double old_value = iter->second;
497
        bc_relative_score_[iter->first] = old_value * factor;
498
    }
499
}
500

  
501
// BETWEENNESS CENTRALITY
502
void BiConnectedComponents::initialize_betweenness_centrality() {
503
    v_centrality_vec_ = CentralityVec(num_of_vertices());
504
    v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap());
328 505
}
custompackages/graph-parser/src/bi_connected_components.h
42 42
    int const num_of_vertices() const;
43 43
    StringSet const& all_art_points_id() const;
44 44
    NameToDoubleMap const& bc_score() const;
45
    NameToDoubleMap const& bc_relative_score() const;
46

  
47
    // Auto run
48
    void run();
45 49

  
46 50
    // SUB-COMPONENT
47 51
    void FindBiConnectedComponents();
48
    void CreateSubComponents();
49 52

  
50 53
    // LINK WEIGHT - calculation for all sub-components
51 54
    void CalculateLinkWeight();
55
    void CalculateLinkWeightReversed();
52 56

  
53 57
    // TRAFFIC MATRIX - calculation for all sub-components
54 58
    void CalculateTrafficMatrix();
55 59

  
60
    // BETWEENNESS CENTRALITY HEURISTIC
61
    void CalculateBetweennessCentralityHeuristic();
62

  
56 63
    // BETWEENNESS CENTRALITY
57 64
    void CalculateBetweennessCentrality();
58
    void initialize_betweenness_centrality();
59
    void calculate_bc_inter();
60
    void finalize_betweenness_centrality();
61 65

  
62 66
    // HELPERS FOR OUTPUTTING RESULT
67
    void print_all_sub_components();
68

  
69
    void print_betweenness_centrality();
70
    void print_betweenness_centrality_heuristic();
71

  
72
    void write_all_betweenness_centrality(string filepath);
73

  
63 74
    void print();
64 75
    friend std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs);
65 76

  
......
70 81
    Component_t BCCs;
71 82

  
72 83
private:
84
    // SUB-COMPONENT
85
    void CreateSubComponents();
86

  
73 87
    // LINK WEIGHT - calculation for all sub-components
74 88
    void initialize_weight();
75 89
    void initialize_queue();
......
77 91
    void process_vertex_component_pair(int comp_index, string vertex_id);
78 92
    void find_unknown_weight_wrt_art_point(string vertex_id);
79 93
    void find_unknown_weight_wrt_component(int comp_index);
94
    bool verify_link_weight();
95

  
96
    // BETWEENNESS CENTRALITY HEURISTIC
97
    void initialize_betweenness_centrality_heuristic();
98
    void calculate_bc_inter();
99
    void finalize_betweenness_centrality_heuristic();
100

  
101
    // BETWEENNESS CENTRALITY
102
    void initialize_betweenness_centrality();
80 103

  
81 104
    // Private variables
82 105
    ComponentVec component_vec_;
......
90 113
    std::queue<QueueElem> Q;
91 114

  
92 115
    // bc_score_ will be updated gradually, first with the score for non art points, and then the score for art points
116
    // Betweenness Centrality Heuristic
93 117
    NameToDoubleMap bc_score_;
118
    NameToDoubleMap bc_relative_score_;
94 119
    NameToDoubleMap bc_sum_art_points_; // summing all the bc score for articulation points
95 120
    NameToDoubleMap bc_inter_;
121

  
122
    // Betweenness Centrality - standard calculation
123
    CentralityVec v_centrality_vec_;
124
    CentralityPMap v_centrality_pmap_;
96 125
};
97 126

  
98 127
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H
custompackages/graph-parser/src/centrality.cpp
1
//
2
// Created by quynh on 12/15/15.
3
//
4

  
5
#include "centrality.h"
6

  
7
void simpleBetweennessCentrality(const Graph &g, string fileSuffix) {
8
    // One way to create centrality_map
9
    //    boost::shared_array_property_map<double, boost::property_map<Graph, vertex_index_t>::const_type>
10
    //            centrality_map(num_vertices(g), get(boost::vertex_index, g));
11

  
12

  
13
    // Define VertexCentralityMap
14
//    typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;
15
//    VertexIndexMap v_index = get(boost::vertex_index, g);
16
//    // Constructs a container with n elements. Each element is a copy of val.
17
//    std::vector< double > v_centrality_vec(boost::num_vertices(g), 0.0);
18
//    // Create the external property map
19
//    boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
20
//            v_centrality_map(v_centrality_vec.begin(), v_index);
21
//
22
//    brandes_betweenness_centrality( g, v_centrality_map);
23

  
24

  
25
    // Nov 20, 2015
26
    // http://stackoverflow.com/questions/15432104/how-to-create-a-propertymap-for-a-boost-graph-using-lists-as-vertex-container
27

  
28
    StdVertexIndexMap v_index_std_map;
29
    VertexIndexMap v_index_map(v_index_std_map);
30

  
31
    // Populate the indexMap
32
    Viter vi, ve; // vertex_iterator, vertex_iterator_end
33
    size_t i = 0;
34
    for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
35
        boost::put(v_index_map, *vi, i);
36
        ++i;
37
    }
38

  
39
    typedef std::vector<double> CentralityVec;
40
    CentralityVec v_centrality_vec(boost::num_vertices(g), 0);
41

  
42
    typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexMap> CentralityMap;
43
    CentralityMap v_centrality_map(v_centrality_vec.begin(), v_index_map);
44

  
45
    // Nov 26, try out the normal call to centrality().This version is not working.
46
//    brandes_betweenness_centrality( g, boost::centrality_map(v_centrality_map));
47

  
48
    // http://stackoverflow.com/questions/30263594/adding-a-vertex-index-to-lists-graph-on-the-fly-for-betweenness-centrality
49
    // Use named-parameter
50
    brandes_betweenness_centrality(g, boost::centrality_map(v_centrality_map).vertex_index_map(v_index_map));
51
    relative_betweenness_centrality(g, v_centrality_map);
52

  
53

  
54
    // Print result of v_centrality_map to console
55
    cout << "Vertex betweenness" << endl;
56
    i = 0;
57
    for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
58
        cout << g[*vi].id << "\t" << v_centrality_vec.at(i) << endl;
59
        ++i;
60
    }
61

  
62
    // Write result of v_centrality_map to file.
63
    writeBetweennessCentrality(g, v_centrality_vec, fileSuffix);
64

  
65
}
66

  
67

  
68
void writeBetweennessCentrality(const Graph &g, std::vector<double> v_centrality_vec, string fileSuffix) {
69
    cout << "XXX Writing to File";
70
    string filePath = "../output/boost_" + fileSuffix + ".csv";
71
    ofstream outFile(filePath.c_str());
72

  
73
    Viter vi, ve;
74
    size_t i = 0;
75
    if (outFile.is_open()) {
76
        for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) {
77
            outFile << g[*vi].id << ", " << v_centrality_vec.at(i) << endl;
78
            ++i;
79
        }
80
    }
81
    outFile.close();
82

  
83
    cout << "XXX Writing to File 2";
84
}
custompackages/graph-parser/src/centrality.h
1 1
//
2 2
// Created by quynh on 12/15/15.
3
// The code is mainly from boost/graph/betweenness_centrality.
4
// I modified the code to work with Traffic Matrix.
3 5
//
4 6

  
5 7
#ifndef GRAPH_PARSER_CENTRALITY_H
6 8
#define GRAPH_PARSER_CENTRALITY_H
7 9

  
8 10
#include <fstream>
11
#include <iostream>
9 12
#include <boost/graph/betweenness_centrality.hpp>
10 13
#include "common.h"
11 14

  
12
void simpleBetweennessCentrality(const Graph &g, string fileSuffix);
13
void writeBetweennessCentrality(const Graph &g, std::vector<double> v_centrality_vec, string fileSuffix);
15
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
    std::cout << "Heuristic Betweenness Centrality Implementation\n";
63

  
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

  
132

  
133

  
134
} } // end of namespace detail::graph
135

  
136
template<typename Graph,
137
         typename TrafficMatrix,
138
         typename CentralityMap, typename EdgeCentralityMap,
139
         typename IncomingMap, typename DistanceMap,
140
         typename DependencyMap, typename PathCountMap,
141
         typename VertexIndexMap>
142
void
143
brandes_betweenness_centrality_heuristic(const Graph& g,
144
                               TrafficMatrix traffic_matrix,
145
                               CentralityMap centrality,     // C_B
146
                               EdgeCentralityMap edge_centrality_map,
147
                               IncomingMap incoming, // P
148
                               DistanceMap distance,         // d
149
                               DependencyMap dependency,     // delta
150
                               PathCountMap path_count,      // sigma
151
                               VertexIndexMap vertex_index
152
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
153
{
154
  detail::graph::brandes_unweighted_shortest_paths shortest_paths;
155

  
156
  detail::graph::brandes_betweenness_centrality_heuristic_impl(g,
157
                                                     traffic_matrix,
158
                                                     centrality,
159
                                                     edge_centrality_map,
160
                                                     incoming, distance,
161
                                                     dependency, path_count,
162
                                                     vertex_index,
163
                                                     shortest_paths);
164
}
165

  
166
template<typename Graph,
167
         typename TrafficMatrix,
168
         typename CentralityMap, typename EdgeCentralityMap,
169
         typename IncomingMap, typename DistanceMap,
170
         typename DependencyMap, typename PathCountMap,
171
         typename VertexIndexMap, typename WeightMap>
172
void
173
brandes_betweenness_centrality_heuristic(const Graph& g,
174
                               TrafficMatrix traffic_matrix,
175
                               CentralityMap centrality,     // C_B
176
                               EdgeCentralityMap edge_centrality_map,
177
                               IncomingMap incoming, // P
178
                               DistanceMap distance,         // d
179
                               DependencyMap dependency,     // delta
180
                               PathCountMap path_count,      // sigma
181
                               VertexIndexMap vertex_index,
182
                               WeightMap weight_map
183
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
184
{
185
  detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
186
    shortest_paths(weight_map);
187

  
188
  detail::graph::brandes_betweenness_centrality_heuristic_impl(g,
189
                                                     traffic_matrix,
190
                                                     centrality,
191
                                                     edge_centrality_map,
192
                                                     incoming, distance,
193
                                                     dependency, path_count,
194
                                                     vertex_index,
195
                                                     shortest_paths);
196
}
197

  
198
namespace detail { namespace graph {
199
  template<typename Graph,
200
           typename TrafficMatrix,
201
           typename CentralityMap, typename EdgeCentralityMap,
202
           typename WeightMap, typename VertexIndexMap>
203
  void
204
  brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,
205
                                           TrafficMatrix traffic_matrix,
206
                                           CentralityMap centrality,
207
                                           EdgeCentralityMap edge_centrality_map,
208
                                           WeightMap weight_map,
209
                                           VertexIndexMap vertex_index)
210
  {
211
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
212
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
213
    typedef typename mpl::if_c<(is_same<CentralityMap,
214
                                        dummy_property_map>::value),
215
                                         EdgeCentralityMap,
216
                               CentralityMap>::type a_centrality_map;
217
    typedef typename property_traits<a_centrality_map>::value_type
218
      centrality_type;
219

  
220
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
221

  
222
    std::vector<std::vector<edge_descriptor> > incoming(V);
223
    std::vector<centrality_type> distance(V);
224
    std::vector<centrality_type> dependency(V);
225
    std::vector<degree_size_type> path_count(V);
226

  
227
    brandes_betweenness_centrality_heuristic(
228
      g,
229
      traffic_matrix,
230
      centrality, edge_centrality_map,
231
      make_iterator_property_map(incoming.begin(), vertex_index),
232
      make_iterator_property_map(distance.begin(), vertex_index),
233
      make_iterator_property_map(dependency.begin(), vertex_index),
234
      make_iterator_property_map(path_count.begin(), vertex_index),
235
      vertex_index,
236
      weight_map);
237
  }
238

  
239

  
240
  template<typename Graph,
241
           typename TrafficMatrix,
242
           typename CentralityMap, typename EdgeCentralityMap,
243
           typename VertexIndexMap>
244
  void
245
  brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,
246
                                           TrafficMatrix traffic_matrix,
247
                                           CentralityMap centrality,
248
                                           EdgeCentralityMap edge_centrality_map,
249
                                           VertexIndexMap vertex_index)
250
  {
251
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
252
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
253
    typedef typename mpl::if_c<(is_same<CentralityMap,
254
                                        dummy_property_map>::value),
255
                                         EdgeCentralityMap,
256
                               CentralityMap>::type a_centrality_map;
257
    typedef typename property_traits<a_centrality_map>::value_type
258
      centrality_type;
259

  
260
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
261

  
262
    std::vector<std::vector<edge_descriptor> > incoming(V);
263
    std::vector<centrality_type> distance(V);
264
    std::vector<centrality_type> dependency(V);
265
    std::vector<degree_size_type> path_count(V);
266

  
267
    brandes_betweenness_centrality_heuristic(
268
      g,
269
      traffic_matrix,
270
      centrality, edge_centrality_map,
271
      make_iterator_property_map(incoming.begin(), vertex_index),
272
      make_iterator_property_map(distance.begin(), vertex_index),
273
      make_iterator_property_map(dependency.begin(), vertex_index),
274
      make_iterator_property_map(path_count.begin(), vertex_index),
275
      vertex_index);
276
  }
277

  
278
  template<typename WeightMap>
279
  struct brandes_betweenness_centrality_heuristic_dispatch1
280
  {
281
    template<typename Graph,
282
             typename TrafficMatrix,
283
             typename CentralityMap,
284
             typename EdgeCentralityMap, typename VertexIndexMap>
285
    static void
286
    run(const Graph& g,
287
        TrafficMatrix traffic_matrix,
288
        CentralityMap centrality,
289
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
290
        WeightMap weight_map)
291
    {
292
      brandes_betweenness_centrality_heuristic_dispatch2(g,
293
                                               traffic_matrix,
294
                                               centrality, edge_centrality_map,
295
                                               weight_map, vertex_index);
296
    }
297
  };
298

  
299
  template<>
300
  struct brandes_betweenness_centrality_heuristic_dispatch1<param_not_found>
301
  {
302
    template<typename Graph,
303
             typename TrafficMatrix,
304
             typename CentralityMap,
305
             typename EdgeCentralityMap, typename VertexIndexMap>
306
    static void
307
    run(const Graph& g,
308
        TrafficMatrix traffic_matrix,
309
        CentralityMap centrality,
310
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
311
        param_not_found)
312
    {
313
      brandes_betweenness_centrality_heuristic_dispatch2(g,
314
                                               traffic_matrix,
315
                                               centrality, edge_centrality_map,
316
                                               vertex_index);
317
    }
318
  };
319

  
320
} } // end namespace detail::graph
321

  
322
template<typename Graph, typename TrafficMatrix, typename Param, typename Tag, typename Rest>
323
void
324
brandes_betweenness_centrality_heuristic(const Graph& g,
325
                               TrafficMatrix traffic_matrix,
326
                               const bgl_named_params<Param,Tag,Rest>& params
327
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
328
{
329
  typedef bgl_named_params<Param,Tag,Rest> named_params;
330

  
331
  typedef typename get_param_type<edge_weight_t, named_params>::type ew;
332
  detail::graph::brandes_betweenness_centrality_heuristic_dispatch1<ew>::run(
333
    g,
334
    traffic_matrix,
335
    choose_param(get_param(params, vertex_centrality),
336
                 dummy_property_map()),
337
    choose_param(get_param(params, edge_centrality),
338
                 dummy_property_map()),
339
    choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
340
    get_param(params, edge_weight));
341
}
342

  
343
} // end namespace boost
14 344

  
15 345
#endif //GRAPH_PARSER_CENTRALITY_H
custompackages/graph-parser/src/graph_manager.cpp
38 38

  
39 39
    string s1 = vp1.id;
40 40
    string s2 = vp2.id;
41
    Vertex v1;
42
    Vertex v2;
43 41

  
44
    try {
45
        v1 = get_vertex_from_id(s1);
42
    if (s1 != s2) { // do not add self-loop into the graph
43
        Vertex v1;
44
        Vertex v2;
45

  
46
        try {
47
            v1 = get_vertex_from_id(s1);
48
        }
49
        catch (exception& e) {
50
            v1 = boost::add_vertex(vp1, g_);
51
            v_id_vertex_map_[s1] = v1;
52
            update_v_index_pmap(v1);
53
        }
54
        try {
55
            v2 = get_vertex_from_id(s2);
56
        }
57
        catch (exception& e) {
58
            v2 = boost::add_vertex(vp2, g_);
59
            v_id_vertex_map_[s2] = v2;
60
            update_v_index_pmap(v2);
61
        }
62

  
63
        Edge e;
64
        bool inserted;
65
        boost::tie(e, inserted) = boost::add_edge(v1, v2, ep, g_);
66
        update_e_index_pmap(e);
46 67
    }
47
    catch (exception& e) {
48
        v1 = boost::add_vertex(vp1, g_);
49
        v_id_vertex_map_[s1] = v1;
50
        update_v_index_pmap(v1);
51
    }
52
    try {
53
        v2 = get_vertex_from_id(s2);
54
    }
55
    catch (exception& e) {
56
        v2 = boost::add_vertex(vp2, g_);
57
        v_id_vertex_map_[s2] = v2;
58
        update_v_index_pmap(v2);
59
    }
60

  
61
    Edge e;
62
    bool inserted;
63
    boost::tie(e, inserted) = boost::add_edge(v1, v2, ep, g_);
64
    update_e_index_pmap(e);
65 68
}
66 69

  
67 70
void GraphManager::ResetVerticesAndEdgesIndexMap() {
custompackages/graph-parser/src/main.cpp
5 5
#include "bi_connected_components.h"
6 6
#include "graph_manager.h"
7 7

  
8

  
9
void handleSimpleGraph() {
10
    /* I don't understand the output. Why there are 8 vertices?
11
        Simple graph
12
        0
13
        1
14
        2
15
        3
16
        4
17
        5
18
        6
19
        7
20
        8
21
    */
22
    typedef boost::adjacency_list<> G;
23
    G a;
24
    {
25
        boost::graph_traits<G>::vertex_descriptor v, u, t;
26
        u = vertex(1, a);
27
        v = vertex(8, a);
28
        // t = vertex(5, a);
29
        add_edge(u, v, a);
30
        // add_edge(u, t, a);
31
    }
32

  
33
    std::set<typename boost::graph_traits<G>::vertex_descriptor> av;
34
    cout << "Simple graph" << endl;
35
    BGL_FORALL_VERTICES_T(v, a, G) {
36
        cout << v << endl;
37
    }
38
}
39
void handleSimpleInput(string filePath) {
40
    // Read the input.edges
41
    Graph g;
42
    readEdgeFile(filePath, g);
43

  
44
    cout << "Finish creating graph" << endl;
45

  
46
    simpleBetweennessCentrality(g, "edge_list");
47
}
48

  
49
void handleJsonInput(string filePath) {
50
    Graph g;
51
    readJson(filePath, g);
52
    outops::operator<<(cout, g);
53

  
54
    // Applying the betweenness centrality
55
    simpleBetweennessCentrality(g, "json_olsr");
56

  
57
    cout << "Done with Betweenness Centrality" << endl;
58
}
59

  
60
void handleComplexJsonInput(string filePath) {
61
    Graph g;
62
    readComplexJson(filePath, g);
63
    outops::operator<<(cout, g);
64

  
65
    // Applying the betweenness centrality
66
    simpleBetweennessCentrality(g, "json_topology");
67

  
68
    cout << "Done with Betweenness Centrality" << endl;
69
}
70

  
71
void testHeuristic(string filePath) {
8
void testHeuristic(string filepath) {
72 9
    GraphManager gm;
73
    readEdgeFileGraphManager(filePath, gm);
74
    gm.print();
10
    readEdgeFileGraphManager(filepath, gm);
75 11
    BiConnectedComponents bcc = BiConnectedComponents(gm);
76
    cout << bcc;
12
    bcc.run();
13
    bcc.print();
14

  
15
    bcc.write_all_betweenness_centrality("../output/simple.edges");
77 16
    cout << "DONE" << endl;
78 17
}
79 18

  
80
void testGraphManager(string filePath) {
19
void testGraphManager(string filepath) {
81 20
    GraphManager gm;
82
    readEdgeFileGraphManager(filePath, gm);
21
    readEdgeFileGraphManager(filepath, gm);
83 22
    gm.print();
84 23
}
85 24

  
86
int main(int, char *[]) {
87
//    string edgeFilePath = "../input/ninux_30_1.edges";
88
//    testHeuristic(edgeFilePath);
89
//    handleSimpleInput(edgeFilePath);
90
//
91
//    string jsonFilePath = "../input/olsr-netjson.json";
92
//    handleJsonInput(jsonFilePath);
93
//
94
//    string complexJsonFilePath = "../input/jsoninfo_topo.json";
95
//    handleComplexJsonInput(complexJsonFilePath);
25
void default_run() {
26
    // input_files = [(filepath, input_type)]
27
    // input_type = 1 ==> edges file
28
    // input_type = 2 ==> simple json file
29
    // input_type = 3 ==> complex json file
30

  
31
    std::list< std::tuple<string, int> > input_files;
32
    // input_files.push_back(std::make_tuple("../input/ninux_unweighted_connected.edges", 1));
33
    // input_files.push_back(std::make_tuple("../input/simple.edges", 1));
34
    input_files.push_back(std::make_tuple("../input/ninux_30_1.edges", 1));
35
    // input_files.push_back(std::make_tuple("../input/olsr-netjson.json", 2));
36
    // input_files.push_back(std::make_tuple("../input/jsoninfo_topo.json", 3));
37

  
38
    for (auto input : input_files) {
39
        string filepath = std::get<0>(input);
40
        int input_type = std::get<1>(input);
41
        GraphManager gm;
42
        if (input_type == 1) {
43
            readEdgeFileGraphManager(filepath, gm);
44
        }
45
        else if (input_type == 2) {
46
            readJsonGraphManager(filepath, gm);
47
        }
48
        else if (input_type == 3) {
49
            readComplexJsonGraphManager(filepath, gm);
50
        }
51

  
52
        cout << gm;
53

  
54
        BiConnectedComponents bcc = BiConnectedComponents(gm);
55
        bcc.run();
56
        // bcc.print();
57
        string filename = helper::get_file_name(filepath);
58
        string out_filepath = "../output/" + filename + ".out";;
59
        bcc.write_all_betweenness_centrality(out_filepath);
60
    }
61
}
96 62

  
97
    // string simpleGraphFilePath = "../input/simple.edges";
98
    // testGraphManager(simpleGraphFilePath);
63
void old_main_code() {
64
    string simpleGraphfilepath = "../input/simple.edges";
65
    testGraphManager(simpleGraphfilepath);
99 66

  
100
    string simpleGraphFilePath = "../input/simple.edges";
101
    testHeuristic(simpleGraphFilePath);
67
    testHeuristic(simpleGraphfilepath);
68
}
69

  
70
int main(int, char *[]) {
71
    default_run();
102 72

  
103 73
    return 0;
104 74
}
custompackages/graph-parser/src/parser.cpp
4 4

  
5 5
#include "parser.h"
6 6

  
7
template<typename NameVertexMap>
8
void addLinkToGraph(string s1, string s2, double cost, Graph &g, NameVertexMap &routers) {
9
    // TODO: change routers --> routers_map
10

  
11
    Vertex v1, v2;
12
    Edge e;
13

  
14
    typename NameVertexMap::iterator pos;
15
    bool inserted;
16

  
17
    boost::tie(pos, inserted) = routers.insert(std::make_pair(s1, Vertex()));
18
    if (inserted) {
19
        v1 = boost::add_vertex(g);
20
        routers[s1] = v1;
21
        pos->second = v1;
22
        g[v1].id = s1;
23
        g[v1].label = s1;
24
    } else {
25
        v1 = pos->second;
26
    }
27

  
28
    boost::tie(pos, inserted) = routers.insert(std::make_pair(s2, Vertex()));
29
    if (inserted) {
30
        v2 = boost::add_vertex(g);
31
        routers[s2] = v2;
32
        pos->second = v2;
33
        g[v2].id = s2;
34
        g[v2].label = s2;
35
    } else {
36
        v2 = pos->second;
37
    }
38

  
39
    // Add edge (aka. link) connecting 2 vertices
40
    boost::tie(e, inserted) = boost::add_edge(v1, v2, g);
41
    if (inserted) {
42
        g[e].cost = cost;
43
    }
44
}
45

  
46
void readEdgeFile(string filePath, Graph &g) {
7
void readEdgeFileGraphManager(string filepath, GraphManager &gm) {
47 8
    // NameVertexMap is to keep track of which router has already been added
48
    typedef std::map<std::string, Vertex> NameVertexMap;
49
    NameVertexMap routers;
50

  
51
    ifstream inFile(filePath.c_str());
9
    ifstream inFile(filepath.c_str());
52 10

  
53 11
    vector<string> strs;
54 12
    for (string line; getline(inFile, line); /**/) {
55
        boost::split(strs, line, boost::is_any_of(" "));
13
        boost::split(strs, line, boost::is_any_of(" "), boost::token_compress_on);
56 14

  
57 15
        // Cast vector<string> to array<string, 3>
58 16
        // TODO: this is really crude way to do it.
......
60 18
        if (strs.size() == 3) {
61 19
            string source = strs[0];
62 20
            string target = strs[1];
21

  
22
            GraphManager::VertexProperties vp1 = GraphManager::VertexProperties(source, source);
23
            GraphManager::VertexProperties vp2 = GraphManager::VertexProperties(target, target);
24

  
63 25
            // TODO: use atof as a way around the error: ‘stof’ was not declared in this scope
64 26
            // double cost = stof(strs[2]);
65 27
            double cost = atof(strs[2].c_str());
66 28

  
67
            addLinkToGraph(source, target, cost, g, routers);
68

  
29
            GraphManager::EdgeProperties ep = GraphManager::EdgeProperties(cost);
30
            gm.AddEdge(vp1, vp2, ep);
69 31
        }
70 32
    }
33
    gm.ResetVerticesAndEdgesIndexMap();
71 34
    inFile.close();
72 35
}
73 36

  
74
void readJson(string filePath, Graph &g) {
37
void readJsonGraphManager(string filepath, GraphManager &gm) {
75 38
    boost::property_tree::ptree pt;
76
    boost::property_tree::read_json(filePath, pt);
77

  
78
    // NameVertexMap is to keep track of which router has already been added
79
    typedef std::map<std::string, Vertex> NameVertexMap;
80
    NameVertexMap routers;
39
    boost::property_tree::read_json(filepath, pt);
81 40

  
82 41
    BOOST_FOREACH(const boost::property_tree::ptree::value_type &v, pt.get_child("links")) {
83
        cout << "X" << endl;
84 42
        cout << v.second.get_value<std::string>() << " ";
85 43
        string source = v.second.get_child("source").get_value<std::string>();
86 44
        string target = v.second.get_child("target").get_value<std::string>();
87 45
        double cost = v.second.get_child("cost").get_value<double>();
88 46

  
89

  
90
        addLinkToGraph(source, target, cost, g, routers);
47
        GraphManager::VertexProperties vp1 = GraphManager::VertexProperties(source, source);
48
        GraphManager::VertexProperties vp2 = GraphManager::VertexProperties(target, target);
49
        GraphManager::EdgeProperties ep = GraphManager::EdgeProperties(cost);
50
        gm.AddEdge(vp1, vp2, ep);
91 51
    }
92 52
}
93 53

  
94
void readComplexJson(string filePath, Graph &g) {
54
void readComplexJsonGraphManager(string filepath, GraphManager &gm) {
95 55
    boost::property_tree::ptree pt;
96
    boost::property_tree::read_json(filePath, pt);
97

  
98
    // NameVertexMap is to keep track of which router has already been added
99
    typedef std::map<std::string, Vertex> NameVertexMap;
100
    NameVertexMap routers;
56
    boost::property_tree::read_json(filepath, pt);
101 57

  
102 58
    BOOST_FOREACH(const boost::property_tree::ptree::value_type &v, pt.get_child("topology")) {
103
        cout << "X" << endl;
104 59
        cout << v.second.get_value<std::string>() << " ";
105 60
        string source = v.second.get_child("lastHopIP").get_value<std::string>();
106 61
        string target = v.second.get_child("destinationIP").get_value<std::string>();
107 62
        double cost = v.second.get_child("neighborLinkQuality").get_value<double>();
108 63

  
109
        addLinkToGraph(source, target, cost, g, routers);
64
        GraphManager::VertexProperties vp1 = GraphManager::VertexProperties(source, source);
65
        GraphManager::VertexProperties vp2 = GraphManager::VertexProperties(target, target);
66
        GraphManager::EdgeProperties ep = GraphManager::EdgeProperties(cost);
67
        gm.AddEdge(vp1, vp2, ep);
110 68
    }
111 69
}
112

  
113
void readEdgeFileGraphManager(string filePath, GraphManager &gm) {
114
    // NameVertexMap is to keep track of which router has already been added
115
    ifstream inFile(filePath.c_str());
116

  
117
    vector<string> strs;
118
    for (string line; getline(inFile, line); /**/) {
119
        boost::split(strs, line, boost::is_any_of(" "));
120

  
121
        // Cast vector<string> to array<string, 3>
122
        // TODO: this is really crude way to do it.
123
        // TODO: how to copy some element of vector to array
124
        if (strs.size() == 3) {
125
            string source = strs[0];
126
            string target = strs[1];
127

  
128
            GraphManager::VertexProperties vp1 = GraphManager::VertexProperties(source, source);
129
            GraphManager::VertexProperties vp2 = GraphManager::VertexProperties(target, target);
130

  
131
            // TODO: use atof as a way around the error: ‘stof’ was not declared in this scope
132
            // double cost = stof(strs[2]);
133
            double cost = atof(strs[2].c_str());
134

  
135
            GraphManager::EdgeProperties ep = GraphManager::EdgeProperties(cost);
136

  
137
            gm.AddEdge(vp1, vp2, ep);
138
        }
139
    }
140
    gm.ResetVerticesAndEdgesIndexMap();
141
    inFile.close();
142
}
custompackages/graph-parser/src/parser.h
11 11
#include "common.h"
12 12
#include "graph_manager.h"
13 13

  
14
template<typename NameVertexMap>
15
void addLinkToGraph(string s1, string s2, double cost, Graph &g, NameVertexMap &routers);
16

  
17
void readEdgeFile(string filePath, Graph &g);
18
void readJson(string filePath, Graph &g);
19
void readComplexJson(string filePath, Graph &g);
20

  
21
void readEdgeFileGraphManager(string filePath, GraphManager& gm);
14
void readEdgeFileGraphManager(string filepath, GraphManager& gm);
15
void readJsonGraphManager(string filepath, GraphManager & gm);
16
void readComplexJsonGraphManager(string filepath, GraphManager& gm);
22 17

  
23 18
#endif //GRAPH_PARSER_PARSER_H
24 19

  
custompackages/graph-parser/src/plot_BC_comparison.gp
1
set term postscript enhanced color
2
set terminal postscript eps
3

  
4
if (!exists("FILENAME")) FILENAME='simple.edges.out'
5
INPUT_FILEPATH = sprintf("../output/%s", FILENAME)
6
set output sprintf("../output/visualization/%s.eps", FILENAME)
7
set title "Centrality for edge_list"
8
set xlabel "Router (each integer corresponds to one router)"
9
set ylabel "Betweenness Centrality"
10

  
11
plot INPUT_FILEPATH using 2 title 'brandes (no inclusion of endpoints)' pointtype 7 pointsize 0.7, \
12
     INPUT_FILEPATH using 3 title 'heuristic (substracted by bc\_inter)' pointtype 5 pointsize 1
custompackages/graph-parser/src/script.sh
1 1
make
2 2
../bin/main
3

  
4
# visualization
5
echo "Start plotting";
6
gnuplot -e "FILENAME='simple.edges.out'" plot_BC_comparison.gp
7
gnuplot -e "FILENAME='ninux_unweighted_connected.edges.out'" plot_BC_comparison.gp
8
gnuplot -e "FILENAME='ninux_30_1.edges.out'" plot_BC_comparison.gp
9
gnuplot -e "FILENAME='jsoninfo_topo.json.out'" plot_BC_comparison.gp
10
gnuplot -e "FILENAME='olsr-netjson.json.out'" plot_BC_comparison.gp
11
echo "Done with plotting"
custompackages/graph-parser/src/sub_component.cpp
4 4

  
5 5
#include "sub_component.h"
6 6

  
7

  
8 7
SubComponent::SubComponent() {
9 8
    // do nothing
10 9
}
......
35 34
    return weight_reversed_map_;
36 35
}
37 36

  
... This diff was truncated because it exceeds the maximum size that can be displayed.

Also available in: Unified diff