## root / custompackages / graph-parser / src / bi_connected_components.cpp @ 6575aa2e

History | View | Annotate | Download (17 KB)

1 | ee0dd796 | Quynh PX Nguyen | ```
//
``` |
---|---|---|---|

2 | ```
// Created by quynh on 1/9/16.
``` |
||

3 | ```
//
``` |
||

4 | |||

5 | #include "bi_connected_components.h" |
||

6 | using namespace std; |
||

7 | |||

8 | cb770240 | Quynh PX Nguyen | ```
/******************************
``` |

9 | ```
* Public functions
``` |
||

10 | ```
******************************/
``` |
||

11 | d5b7a27f | Quynh PX Nguyen | BiConnectedComponents::BiConnectedComponents(GraphManager &gm) : gm_(gm) { |

12 | ee0dd796 | Quynh PX Nguyen | init(); |

13 | } |
||

14 | |||

15 | ```
void BiConnectedComponents::init() {
``` |
||

16 | cb770240 | Quynh PX Nguyen | ```
// Set some variables
``` |

17 | num_of_vertices_ = boost::num_vertices(gm_.g_); |
||

18 | ee0dd796 | Quynh PX Nguyen | |

19 | 162e1bda | Quynh PX Nguyen | ```
component_vec_ = ComponentVec(boost::num_edges(gm_.g_), -1);
``` |

20 | 437fd680 | Quynh PX Nguyen | component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap()); |

21 | ee0dd796 | Quynh PX Nguyen | } |

22 | |||

23 | cb770240 | Quynh PX Nguyen | ```
/* GETTER */
``` |

24 | 437fd680 | Quynh PX Nguyen | int const BiConnectedComponents::num_of_bcc() { |

25 | ```
return num_of_bcc_;
``` |
||

26 | } |
||

27 | |||

28 | int const BiConnectedComponents::num_of_vertices() const { |
||

29 | ```
return num_of_vertices_;
``` |
||

30 | } |
||

31 | |||

32 | cb770240 | Quynh PX Nguyen | StringSet const& BiConnectedComponents::all_art_points_id() const { |

33 | ```
return all_art_points_id_;
``` |
||

34 | } |
||

35 | ee0dd796 | Quynh PX Nguyen | |

36 | 437fd680 | Quynh PX Nguyen | NameToDoubleMap const& BiConnectedComponents::bc_score() const { |

37 | ```
return bc_score_;
``` |
||

38 | } |
||

39 | |||

40 | 162e1bda | Quynh PX Nguyen | NameToDoubleMap const& BiConnectedComponents::bc_relative_score() const { |

41 | ```
return bc_relative_score_;
``` |
||

42 | } |
||

43 | ee0dd796 | Quynh PX Nguyen | |

44 | 162e1bda | Quynh PX Nguyen | ```
// AUTO RUN
``` |

45 | ```
void BiConnectedComponents::run() {
``` |
||

46 | ```
/* Auto run all the necessary functions
``` |
||

47 | ```
*/
``` |
||

48 | d5b7a27f | Quynh PX Nguyen | ```
cout << "Running FindBiConnectedComponents" << endl;
``` |

49 | 162e1bda | Quynh PX Nguyen | FindBiConnectedComponents(); |

50 | ee0dd796 | Quynh PX Nguyen | |

51 | 162e1bda | Quynh PX Nguyen | ```
// Calculate Link Weight + Link Weight Reversed
``` |

52 | ```
cout << "Calculate Link Weight + Link Weight Reversed\n";
``` |
||

53 | cb770240 | Quynh PX Nguyen | CalculateLinkWeight(); |

54 | 162e1bda | Quynh PX Nguyen | CalculateLinkWeightReversed(); |

55 | verify_link_weight(); |
||

56 | ee0dd796 | Quynh PX Nguyen | |

57 | cb770240 | Quynh PX Nguyen | ```
// Calculate Traffic Matrix
``` |

58 | ```
cout << "Calculate Traffic Matrix\n";
``` |
||

59 | CalculateTrafficMatrix(); |
||

60 | ee0dd796 | Quynh PX Nguyen | |

61 | 162e1bda | Quynh PX Nguyen | ```
// Calculate Betweenness Centrality Heuristic
``` |

62 | ```
cout << "Calculate Betweenness Centrality Heuristic\n";
``` |
||

63 | CalculateBetweennessCentralityHeuristic(); |
||

64 | cb770240 | Quynh PX Nguyen | } |

65 | |||

66 | 162e1bda | Quynh PX Nguyen | ```
// SUB-COMPONENT
``` |

67 | ```
void BiConnectedComponents::FindBiConnectedComponents() {
``` |
||

68 | boost::biconnected_components(gm_.g_, component_map_, |
||

69 | back_inserter(art_points_), |
||

70 | boost::vertex_index_map(gm_.v_index_pmap())); |
||

71 | |||

72 | e263e3c7 | Quynh PX Nguyen | ```
// Set some necessary variables
``` |

73 | 162e1bda | Quynh PX Nguyen | graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_); |

74 | e263e3c7 | Quynh PX Nguyen | reset_num_of_bcc(); |

75 | ```
cout << "Total # of components: " << num_of_bcc_ << endl;
``` |
||

76 | 162e1bda | Quynh PX Nguyen | |

77 | ```
// Process the result from boost::biconnected_components
``` |
||

78 | ```
cout << "Create Sub Components\n";
``` |
||

79 | CreateSubComponents(); |
||

80 | ee0dd796 | Quynh PX Nguyen | } |

81 | |||

82 | 162e1bda | Quynh PX Nguyen | ```
// LINK WEIGHT
``` |

83 | cb770240 | Quynh PX Nguyen | ```
void BiConnectedComponents::CalculateLinkWeight() {
``` |

84 | initialize_weight(); |
||

85 | initialize_queue(); |
||

86 | |||

87 | ```
while (!Q.empty()) {
``` |
||

88 | QueueElem elem = Q.front(); |
||

89 | Q.pop(); |
||

90 | ```
int comp_index = elem.component_index;
``` |
||

91 | ```
string vertex_id = elem.vertex_id;
``` |
||

92 | |||

93 | if (elem.type == "component_vertex_pair") { |
||

94 | ```
// cout << "component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
``` |
||

95 | process_component_vertex_pair(comp_index, vertex_id); |
||

96 | } |
||

97 | else if (elem.type == "vertex_component_pair") { |
||

98 | ```
// cout << "vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
``` |
||

99 | process_vertex_component_pair(comp_index, vertex_id); |
||

100 | } |
||

101 | ee0dd796 | Quynh PX Nguyen | } |

102 | } |
||

103 | |||

104 | 162e1bda | Quynh PX Nguyen | ```
void BiConnectedComponents::CalculateLinkWeightReversed() {
``` |

105 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

106 | BCCs[i].calculate_weight_reversed(num_of_vertices_); |
||

107 | } |
||

108 | } |
||

109 | |||

110 | ```
// TRAFFIC MATRIX
``` |
||

111 | cb770240 | Quynh PX Nguyen | ```
void BiConnectedComponents::CalculateTrafficMatrix() {
``` |

112 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

113 | BCCs[i].CalculateTrafficMatrix(); |
||

114 | } |
||

115 | } |
||

116 | |||

117 | 162e1bda | Quynh PX Nguyen | ```
// BETWEENNESS CENTRALITY HEURISTIC
``` |

118 | ```
void BiConnectedComponents::CalculateBetweennessCentralityHeuristic() {
``` |
||

119 | ```
cout << "BETWEENNESS CENTRALITY HEURISTIC\n";
``` |
||

120 | 437fd680 | Quynh PX Nguyen | |

121 | 162e1bda | Quynh PX Nguyen | initialize_betweenness_centrality_heuristic(); |

122 | calculate_bc_inter(); |
||

123 | 437fd680 | Quynh PX Nguyen | |

124 | 20756421 | Quynh PX Nguyen | for (int i = 0; i < num_of_bcc_; ++i) { |

125 | e263e3c7 | Quynh PX Nguyen | ```
// cout << "BC for component " << i << endl;
``` |

126 | 162e1bda | Quynh PX Nguyen | BCCs[i].CalculateBetweennessCentralityHeuristic(); |

127 | 20756421 | Quynh PX Nguyen | } |

128 | 437fd680 | Quynh PX Nguyen | |

129 | ```
double score;
``` |
||

130 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

131 | 162e1bda | Quynh PX Nguyen | ```
// For all points
``` |

132 | for (string id: BCCs[i].all_vertices_id()) { |
||

133 | 437fd680 | Quynh PX Nguyen | score = BCCs[i].get_betweenness_centrality(id); |

134 | e263e3c7 | Quynh PX Nguyen | ```
// cout << "XXX score from component << " << i << ", id " << id << " = " << score << endl;
``` |

135 | 162e1bda | Quynh PX Nguyen | bc_score_[id] += score; |

136 | 437fd680 | Quynh PX Nguyen | } |

137 | } |
||

138 | |||

139 | 162e1bda | Quynh PX Nguyen | ```
// // 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 | e263e3c7 | Quynh PX Nguyen | ```
// Update the BC score for articulation points
``` |

155 | 6575aa2e | Quynh PX Nguyen | for (string id : all_art_points_id_) { |

156 | ```
// bc_score_[id] = bc_sum_art_points_[id];
``` |
||

157 | 437fd680 | Quynh PX Nguyen | |

158 | 6575aa2e | Quynh PX Nguyen | ```
// TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
``` |

159 | ```
cout << bc_score_[id] << " --> ";
``` |
||

160 | bc_score_[id] -= bc_inter_[id]; |
||

161 | e263e3c7 | Quynh PX Nguyen | ```
// cout << bc_score_[id] << endl;
``` |

162 | 6575aa2e | Quynh PX Nguyen | } |

163 | 437fd680 | Quynh PX Nguyen | |

164 | 162e1bda | Quynh PX Nguyen | finalize_betweenness_centrality_heuristic(); |

165 | |||

166 | 437fd680 | Quynh PX Nguyen | ```
cout << "DONE WITH BETWEENNESS CENTRALITY\n";
``` |

167 | 20756421 | Quynh PX Nguyen | } |

168 | |||

169 | 162e1bda | Quynh PX Nguyen | ```
// BETWEENNESS CENTRALITY - NORMAL CALCULATION
``` |

170 | d5b7a27f | Quynh PX Nguyen | void BiConnectedComponents::CalculateBetweennessCentrality(bool targets_inclusion) { |

171 | 162e1bda | Quynh PX Nguyen | initialize_betweenness_centrality(); |

172 | ee0dd796 | Quynh PX Nguyen | |

173 | d5b7a27f | Quynh PX Nguyen | if (gm_.weighted_graph()) { // calculate BC for weighted graph |

174 | ```
cout << "======= BCC - BC for weighted graph ======\n";
``` |
||

175 | |||

176 | e263e3c7 | Quynh PX Nguyen | typedef map<Edge, double> EdgeWeightStdMap; |

177 | ```
typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap;
``` |
||

178 | EdgeIndexStdMap edge_weight_std_map; |
||

179 | EdgeWeightPMap edge_weight_pmap = EdgeWeightPMap(edge_weight_std_map); |
||

180 | |||

181 | BGL_FORALL_EDGES(edge, gm_.g_, Graph) { |
||

182 | edge_weight_std_map[edge] = gm_.g_[edge].cost; |
||

183 | } |
||

184 | d5b7a27f | Quynh PX Nguyen | boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_, |

185 | targets_inclusion, |
||

186 | e263e3c7 | Quynh PX Nguyen | boost::centrality_map( |

187 | v_centrality_pmap_).vertex_index_map( |
||

188 | gm_.v_index_pmap()).weight_map( |
||

189 | edge_weight_pmap) |
||

190 | ); |
||

191 | } |
||

192 | else { // for unweighted graph |
||

193 | d5b7a27f | Quynh PX Nguyen | boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_, |

194 | targets_inclusion, |
||

195 | e263e3c7 | Quynh PX Nguyen | boost::centrality_map( |

196 | v_centrality_pmap_).vertex_index_map( |
||

197 | gm_.v_index_pmap()) |
||

198 | ); |
||

199 | } |
||

200 | 437fd680 | Quynh PX Nguyen | |

201 | 162e1bda | Quynh PX Nguyen | boost::relative_betweenness_centrality(gm_.g_, v_centrality_pmap_); |

202 | } |
||

203 | |||

204 | ```
// HELPERS FOR OUTPUTTING RESULT
``` |
||

205 | ```
void BiConnectedComponents::print_all_sub_components() {
``` |
||

206 | e263e3c7 | Quynh PX Nguyen | for (int i = 0; i < num_of_bcc_; ++i) { |

207 | 162e1bda | Quynh PX Nguyen | ```
// cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout
``` |

208 | BCCs[i].print(); |
||

209 | 437fd680 | Quynh PX Nguyen | } |

210 | } |
||

211 | |||

212 | d5b7a27f | Quynh PX Nguyen | ```
void BiConnectedComponents::print_biconnected_components() {
``` |

213 | ```
cout << "\nArticulation points:\n";
``` |
||

214 | ```
outops::operator<<(cout, all_art_points_id_);
``` |
||

215 | |||

216 | ```
cout << "All Sub Components:\n\n";
``` |
||

217 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

218 | ```
cout << " " << i << endl;
``` |
||

219 | ```
outops::operator<<(cout, BCCs[i].all_vertices_id());
``` |
||

220 | } |
||

221 | } |
||

222 | |||

223 | 162e1bda | Quynh PX Nguyen | ```
void BiConnectedComponents::print_betweenness_centrality() {
``` |

224 | BGL_FORALL_VERTICES(v, gm_.g_, Graph) { |
||

225 | ```
double bc_score = boost::get(v_centrality_pmap_, v);
``` |
||

226 | ```
cout << gm_.g_[v].id << ": " << bc_score << endl;
``` |
||

227 | 437fd680 | Quynh PX Nguyen | } |

228 | ee0dd796 | Quynh PX Nguyen | } |

229 | |||

230 | 162e1bda | Quynh PX Nguyen | ```
void BiConnectedComponents::print_betweenness_centrality_heuristic() {
``` |

231 | outops::operator<< <double>(cout, bc_relative_score_); |
||

232 | } |
||

233 | |||

234 | void BiConnectedComponents::write_all_betweenness_centrality(string filepath) { |
||

235 | ```
/* Write the heuristic and the normal version of betweenness centrality
``` |
||

236 | ```
1st column: brandes_betweenness_centrality
``` |
||

237 | ```
2nd column: heuristic_betweenness_centrality
``` |
||

238 | ```
*/
``` |
||

239 | 437fd680 | Quynh PX Nguyen | |

240 | 162e1bda | Quynh PX Nguyen | vector<pair<string, double> > mapcopy(bc_relative_score_.begin(), bc_relative_score_.end()); |

241 | std::sort(mapcopy.begin(), mapcopy.end(), less_second<string, double>()); |
||

242 | |||

243 | ofstream outFile(filepath.c_str()); |
||

244 | |||

245 | Viter vi, ve; |
||

246 | ```
size_t i = 0;
``` |
||

247 | ```
if (outFile.is_open()) {
``` |
||

248 | for(auto id_bc_score_pair : mapcopy) { |
||

249 | ```
string id = id_bc_score_pair.first;
``` |
||

250 | ```
double heuristic_bc_score = id_bc_score_pair.second;
``` |
||

251 | |||

252 | ```
int index = gm_.get_index_from_id(id);
``` |
||

253 | ```
double bc_score = v_centrality_vec_.at(index);
``` |
||

254 | |||

255 | d5b7a27f | Quynh PX Nguyen | outFile << id << "\t" << setprecision(4) << fixed << bc_score << "\t" << heuristic_bc_score << endl; |

256 | 162e1bda | Quynh PX Nguyen | } |

257 | ```
// for (boost::tie(vi, ve) = boost::vertices(gm_.g_); vi != ve; ++vi) {
``` |
||

258 | ```
// string id = gm_.g_[*vi].id;
``` |
||

259 | ```
// outFile << id << "\t" << bc_relative_score_[id] << "\t" << v_centrality_vec_.at(i) << endl;
``` |
||

260 | ```
// ++i;
``` |
||

261 | ```
// }
``` |
||

262 | cb770240 | Quynh PX Nguyen | } |

263 | 162e1bda | Quynh PX Nguyen | outFile.close(); |

264 | ```
cout << "Finish writing brandes and heurisic BC score to file " << filepath << endl;
``` |
||

265 | } |
||

266 | |||

267 | ```
void BiConnectedComponents::print() {
``` |
||

268 | ```
cout << "\n\nBi-Connected Components\n\n";
``` |
||

269 | cout << gm_; |
||

270 | |||

271 | d5b7a27f | Quynh PX Nguyen | print_biconnected_components(); |

272 | e263e3c7 | Quynh PX Nguyen | |

273 | 162e1bda | Quynh PX Nguyen | ```
cout << "\nHeuristic Betweenness Centrality Score:\n";
``` |

274 | outops::operator<< <double>(cout, bc_score_); |
||

275 | |||

276 | ```
cout << "\nHeuristic Betweenness Centrality Relative Score:\n";
``` |
||

277 | outops::operator<< <double>(cout, bc_relative_score_); |
||

278 | |||

279 | ```
cout << "\nNormal Betweenness Centrality Score:\n";
``` |
||

280 | print_betweenness_centrality(); |
||

281 | cb770240 | Quynh PX Nguyen | } |

282 | ee0dd796 | Quynh PX Nguyen | |

283 | cb770240 | Quynh PX Nguyen | std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) { |

284 | ```
cout << "\n\nBi-Connected Components\n\n";
``` |
||

285 | cout << rhs.gm_; |
||

286 | ee0dd796 | Quynh PX Nguyen | |

287 | cb770240 | Quynh PX Nguyen | ```
cout << "\nArticulation points:\n";
``` |

288 | ```
outops::operator<<(cout, rhs.all_art_points_id());
``` |
||

289 | 437fd680 | Quynh PX Nguyen | |

290 | 162e1bda | Quynh PX Nguyen | ```
cout << "\nHeuristic Betweenness Centrality Score:\n";
``` |

291 | 437fd680 | Quynh PX Nguyen | outops::operator<< <double>(cout, rhs.bc_score()); |

292 | ee0dd796 | Quynh PX Nguyen | |

293 | 162e1bda | Quynh PX Nguyen | ```
cout << "\nHeuristic Betweenness Centrality Relative Score:\n";
``` |

294 | outops::operator<< <double>(cout, rhs.bc_relative_score()); |
||

295 | |||

296 | ```
return os;
``` |
||

297 | ee0dd796 | Quynh PX Nguyen | } |

298 | |||

299 | cb770240 | Quynh PX Nguyen | ```
/******************************
``` |

300 | ```
* Private functions
``` |
||

301 | ```
******************************/
``` |
||

302 | 162e1bda | Quynh PX Nguyen | ```
// SUB-COMPONENT
``` |

303 | e263e3c7 | Quynh PX Nguyen | ```
void BiConnectedComponents::reset_num_of_bcc() {
``` |

304 | ```
num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
``` |
||

305 | } |
||

306 | |||

307 | 162e1bda | Quynh PX Nguyen | ```
void BiConnectedComponents::CreateSubComponents() {
``` |

308 | d5b7a27f | Quynh PX Nguyen | for (int i = 0; i < num_of_bcc_; ++i) { |

309 | BCCs.push_back(SubComponent(gm_.weighted_graph())); |
||

310 | } |
||

311 | |||

312 | 162e1bda | Quynh PX Nguyen | ```
// Generating subgraph for each sub-component
``` |

313 | BGL_FORALL_EDGES(edge, gm_.g_, Graph) { |
||

314 | Vertex source = boost::source(edge, gm_.g_); |
||

315 | Vertex target = boost::target(edge, gm_.g_); |
||

316 | |||

317 | ```
int comp_index = boost::get(component_map_, edge);
``` |
||

318 | e263e3c7 | Quynh PX Nguyen | ```
cout << comp_index << " ";
``` |

319 | |||

320 | 162e1bda | Quynh PX Nguyen | if (comp_index == -1) { |

321 | ```
cout << "ERROR: edge ";
``` |
||

322 | graphext::print_edge(gm_.g_, edge); |
||

323 | ```
cout << "not belonging to subcomponent\n";
``` |
||

324 | } |
||

325 | ```
else {
``` |
||

326 | Router r1 = gm_.g_[source]; |
||

327 | Router r2 = gm_.g_[target]; |
||

328 | Link l = gm_.g_[edge]; |
||

329 | e263e3c7 | Quynh PX Nguyen | if (r1 != r2) { // Do not add self-loop edge |

330 | BCCs[comp_index].AddEdge(r1, r2, l); |
||

331 | } |
||

332 | 162e1bda | Quynh PX Nguyen | } |

333 | } |
||

334 | |||

335 | ```
// Finalizing each sub components
``` |
||

336 | e263e3c7 | Quynh PX Nguyen | for (int i = 0; i < num_of_bcc_; ++i) { |

337 | 162e1bda | Quynh PX Nguyen | BCCs[i].FinalizeSubComponent(all_art_points_id_); |

338 | } |
||

339 | } |
||

340 | ee0dd796 | Quynh PX Nguyen | |

341 | 162e1bda | Quynh PX Nguyen | ```
// LINK WEIGHT
``` |

342 | cb770240 | Quynh PX Nguyen | ```
void BiConnectedComponents::initialize_weight() {
``` |

343 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

344 | BCCs[i].initialize_weight(); |
||

345 | ee0dd796 | Quynh PX Nguyen | } |

346 | } |
||

347 | |||

348 | cb770240 | Quynh PX Nguyen | ```
void BiConnectedComponents::initialize_queue() {
``` |

349 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

350 | if (BCCs[i].art_points_id().size() == 1) { |
||

351 | ```
string vertex_id = *(BCCs[i].art_points_id().begin());
``` |
||

352 | string type = "component_vertex_pair"; |
||

353 | QueueElem elem = { |
||

354 | .component_index = i, |
||

355 | .vertex_id = vertex_id, |
||

356 | .type = type, |
||

357 | }; |
||

358 | d5b7a27f | Quynh PX Nguyen | ```
// cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";
``` |

359 | cb770240 | Quynh PX Nguyen | Q.push(elem); |

360 | } |
||

361 | ee0dd796 | Quynh PX Nguyen | } |

362 | } |
||

363 | |||

364 | cb770240 | Quynh PX Nguyen | void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) { |

365 | int size = BCCs[comp_index].num_of_vertices() - 1; |
||

366 | for (string s : BCCs[comp_index].art_points_id()) { |
||

367 | if (s.compare(vertex_id) != 0) { |
||

368 | ```
int weight = BCCs[comp_index].get_weight_map(s);
``` |
||

369 | if (weight != -1) { |
||

370 | ```
size += num_of_vertices_ - weight - 1;
``` |
||

371 | ee0dd796 | Quynh PX Nguyen | } |

372 | } |
||

373 | } |
||

374 | cb770240 | Quynh PX Nguyen | ```
int link_weight = size;
``` |

375 | 162e1bda | Quynh PX Nguyen | |

376 | ```
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);
``` |
||

377 | if (old_link_weight != -1) { |
||

378 | ```
if (link_weight != old_link_weight) {
``` |
||

379 | e263e3c7 | Quynh PX Nguyen | cout << "ERROR in Link Weight for comp " << comp_index << " | vertex " << vertex_id << old_link_weight << " | " << link_weight << endl; |

380 | 162e1bda | Quynh PX Nguyen | } |

381 | } |
||

382 | |||

383 | cb770240 | Quynh PX Nguyen | BCCs[comp_index].update_weight_map(vertex_id, link_weight); |

384 | d5b7a27f | Quynh PX Nguyen | ```
// cout << " update weight for comp " << comp_index << " | vertex " << vertex_id << " = " << link_weight << endl;
``` |

385 | cb770240 | Quynh PX Nguyen | find_unknown_weight_wrt_art_point(vertex_id); |

386 | ee0dd796 | Quynh PX Nguyen | } |

387 | |||

388 | cb770240 | Quynh PX Nguyen | void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) { |

389 | int count = 0; |
||

390 | int comp_index = -1; |
||

391 | e263e3c7 | Quynh PX Nguyen | ```
// cout << "find_unknown_weight_wrt_art_point " << vertex_id << "\n";
``` |

392 | 162e1bda | Quynh PX Nguyen | |

393 | cb770240 | Quynh PX Nguyen | for (int i = 0; i < num_of_bcc_; ++i) { |

394 | ```
if (BCCs[i].vertex_exists(vertex_id)) {
``` |
||

395 | if (BCCs[i].get_weight_map(vertex_id) == -1) { |
||

396 | e263e3c7 | Quynh PX Nguyen | ```
// cout << " comp_index = " << i << endl;
``` |

397 | cb770240 | Quynh PX Nguyen | ++count; |

398 | comp_index = i; |
||

399 | } |
||

400 | ee0dd796 | Quynh PX Nguyen | |

401 | cb770240 | Quynh PX Nguyen | if (count > 1) break; |

402 | ee0dd796 | Quynh PX Nguyen | } |

403 | } |
||

404 | |||

405 | cb770240 | Quynh PX Nguyen | if (count == 1) { |

406 | ```
// Add new element to QueueElem
``` |
||

407 | QueueElem elem = { |
||

408 | .component_index = comp_index, |
||

409 | .vertex_id = vertex_id, |
||

410 | ```
.type = "vertex_component_pair"
``` |
||

411 | }; |
||

412 | ee0dd796 | Quynh PX Nguyen | |

413 | e263e3c7 | Quynh PX Nguyen | ```
// cout << " Add vertex_component_pair: " << comp_index << " - " << vertex_id << endl;
``` |

414 | cb770240 | Quynh PX Nguyen | Q.push(elem); |

415 | ee0dd796 | Quynh PX Nguyen | } |

416 | } |
||

417 | |||

418 | cb770240 | Quynh PX Nguyen | void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) { |

419 | int size = 0; |
||

420 | ee0dd796 | Quynh PX Nguyen | |

421 | cb770240 | Quynh PX Nguyen | for (int i = 0; i < num_of_bcc_; ++i) { |

422 | ```
if (i != comp_index) {
``` |
||

423 | ```
if (BCCs[i].vertex_exists(vertex_id)) {
``` |
||

424 | ```
int weight = BCCs[i].get_weight_map(vertex_id);
``` |
||

425 | if (weight != -1) { |
||

426 | size += weight; |
||

427 | } |
||

428 | } |
||

429 | } |
||

430 | } |
||

431 | ee0dd796 | Quynh PX Nguyen | |

432 | cb770240 | Quynh PX Nguyen | int link_weight = num_of_vertices_ - 1 - size; |

433 | 162e1bda | Quynh PX Nguyen | |

434 | ```
int old_link_weight = BCCs[comp_index].get_weight_map(vertex_id);
``` |
||

435 | if (old_link_weight != -1) { |
||

436 | ```
if (link_weight != old_link_weight) {
``` |
||

437 | e263e3c7 | Quynh PX Nguyen | cout << "ERROR in Link Weight for comp " << comp_index << " | vertex " << vertex_id << old_link_weight << " | " << link_weight << endl; |

438 | 162e1bda | Quynh PX Nguyen | } |

439 | } |
||

440 | |||

441 | cb770240 | Quynh PX Nguyen | BCCs[comp_index].update_weight_map(vertex_id, link_weight); |

442 | 4ca27bae | Quynh PX Nguyen | ```
// cout << " update weight for vertex_component pair: " << comp_index << " | " << vertex_id << " = " << link_weight << endl;
``` |

443 | cb770240 | Quynh PX Nguyen | find_unknown_weight_wrt_component(comp_index); |

444 | ee0dd796 | Quynh PX Nguyen | } |

445 | |||

446 | cb770240 | Quynh PX Nguyen | void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) { |

447 | ```
// The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/counting-number-of-same-values-in-map
``` |
||

448 | ```
typedef NameToIntMap::value_type MapEntry;
``` |
||

449 | ```
int count = std::count_if(
``` |
||

450 | BCCs[comp_index].weight_map().begin(), |
||

451 | BCCs[comp_index].weight_map().end(), |
||

452 | ```
second_equal_to<MapEntry>(-1));
``` |
||

453 | |||

454 | if (count == 1) { |
||

455 | ```
// Find the vertex id for the vertex with unknown link weight
``` |
||

456 | ```
string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight();
``` |
||

457 | |||

458 | QueueElem elem = { |
||

459 | .component_index = comp_index, |
||

460 | .vertex_id = vertex_id, |
||

461 | ```
.type = "component_vertex_pair",
``` |
||

462 | }; |
||

463 | e263e3c7 | Quynh PX Nguyen | ```
// cout << "Add component_vertex_pair: " << comp_index << " - " << vertex_id << endl;
``` |

464 | cb770240 | Quynh PX Nguyen | Q.push(elem); |

465 | } |
||

466 | 162e1bda | Quynh PX Nguyen | } |

467 | |||

468 | ```
bool BiConnectedComponents::verify_link_weight() {
``` |
||

469 | ```
// Returns True if there is no negative value in Link Weight
``` |
||

470 | bool result = true; |
||

471 | |||

472 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

473 | for (string id : BCCs[i].art_points_id()) { |
||

474 | if (BCCs[i].get_weight_map(id) == -1) { |
||

475 | 4ca27bae | Quynh PX Nguyen | cout << "ERROR Link Weight for vertex " << id << " in component " << i << " = " << -1 << endl; |

476 | 162e1bda | Quynh PX Nguyen | ```
result = false;
``` |

477 | } |
||

478 | } |
||

479 | } |
||

480 | } |
||

481 | |||

482 | ```
// BETWEENNESS CENTRALITY - HEURISTIC
``` |
||

483 | ```
void BiConnectedComponents::initialize_betweenness_centrality_heuristic() {
``` |
||

484 | ```
// Initialize bc_inter_ to be 0
``` |
||

485 | for (string id: all_art_points_id_) { |
||

486 | ```
bc_inter_[id] = 0;
``` |
||

487 | } |
||

488 | |||

489 | StringSet all_vertices_id; |
||

490 | graphext::id_of_all_vertices(gm_.g_, all_vertices_id); |
||

491 | |||

492 | ```
// Initialize bc_sum_, bc_score_ to be 0
``` |
||

493 | for (string id: all_vertices_id) { |
||

494 | ```
bc_sum_art_points_[id] = 0;
``` |
||

495 | ```
bc_score_[id] = 0;
``` |
||

496 | } |
||

497 | } |
||

498 | |||

499 | ```
void BiConnectedComponents::calculate_bc_inter() {
``` |
||

500 | for (int i = 0; i < num_of_bcc_; ++i) { |
||

501 | for (string id : BCCs[i].art_points_id()) { |
||

502 | bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id); |
||

503 | } |
||

504 | } |
||

505 | } |
||

506 | |||

507 | ```
void BiConnectedComponents::finalize_betweenness_centrality_heuristic() {
``` |
||

508 | ```
// Divide the bc_score_ by some factor
``` |
||

509 | ```
int n = num_of_vertices();
``` |
||

510 | double factor = 2.0 / (n*n - 3*n + 2); |
||

511 | NameToDoubleMap::iterator iter; |
||

512 | ```
for (iter = bc_score_.begin(); iter != bc_score_.end(); ++iter) {
``` |
||

513 | ```
double old_value = iter->second;
``` |
||

514 | bc_relative_score_[iter->first] = old_value * factor; |
||

515 | } |
||

516 | } |
||

517 | |||

518 | ```
// BETWEENNESS CENTRALITY
``` |
||

519 | ```
void BiConnectedComponents::initialize_betweenness_centrality() {
``` |
||

520 | v_centrality_vec_ = CentralityVec(num_of_vertices()); |
||

521 | v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap()); |
||

522 | cb770240 | Quynh PX Nguyen | } |