Revision d5b7a27f custompackages/graphparser/src/bi_connected_components.cpp
custompackages/graphparser/src/bi_connected_components.cpp  

8  8 
/****************************** 
9  9 
* Public functions 
10  10 
******************************/ 
11 
BiConnectedComponents::BiConnectedComponents(GraphManager &gm, bool weighted_graph) : gm_(gm), weighted_graph_(weighted_graph) {


11 
BiConnectedComponents::BiConnectedComponents(GraphManager &gm) : gm_(gm) {


12  12 
init(); 
13  13 
} 
14  14  
...  ...  
41  41 
return bc_relative_score_; 
42  42 
} 
43  43  
44 
bool BiConnectedComponents::weighted_graph() const { 

45 
return weighted_graph_; 

46 
} 

47  
48 
// Setter functions 

49 
void BiConnectedComponents::set_weighted_graph(bool rhs) { 

50 
weighted_graph_ = rhs; 

51 
} 

52  
53  44 
// AUTO RUN 
54  45 
void BiConnectedComponents::run() { 
55  46 
/* Auto run all the necessary functions 
56  47 
*/ 
48 
cout << "Running FindBiConnectedComponents" << endl; 

57  49 
FindBiConnectedComponents(); 
58  50  
59 
cout << "\nArticulation points:\n"; 

60 
outops::operator<<(cout, all_art_points_id_); 

61  
62 
cout << "All Sub Components:\n\n"; 

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

64 
cout << " " << i << endl; 

65 
outops::operator<<(cout, BCCs[i].all_vertices_id()); 

66 
} 

67  
68  51 
// Calculate Link Weight + Link Weight Reversed 
69  52 
cout << "Calculate Link Weight + Link Weight Reversed\n"; 
70  53 
CalculateLinkWeight(); 
...  ...  
78  61 
// Calculate Betweenness Centrality Heuristic 
79  62 
cout << "Calculate Betweenness Centrality Heuristic\n"; 
80  63 
CalculateBetweennessCentralityHeuristic(); 
81  
82 
// Calculate Betweenness Centrality 

83 
cout << "Calculate Betweenness Centrality\n"; 

84 
CalculateBetweennessCentrality(); 

85  64 
} 
86  65  
87  66 
// SUBCOMPONENT 
88  67 
void BiConnectedComponents::FindBiConnectedComponents() { 
89 
cout << "Running FindBiConnectedComponents" << endl; 

90  
91  68 
boost::biconnected_components(gm_.g_, component_map_, 
92  69 
back_inserter(art_points_), 
93  70 
boost::vertex_index_map(gm_.v_index_pmap())); 
...  ...  
99  76  
100  77 
// Process the result from boost::biconnected_components 
101  78 
cout << "Create Sub Components\n"; 
102 
BCCs = Component_t(num_of_bcc_); 

103  79 
CreateSubComponents(); 
104  80 
} 
105  81  
...  ...  
191  167 
} 
192  168  
193  169 
// BETWEENNESS CENTRALITY  NORMAL CALCULATION 
194 
void BiConnectedComponents::CalculateBetweennessCentrality() { 

170 
void BiConnectedComponents::CalculateBetweennessCentrality(bool targets_inclusion) {


195  171 
initialize_betweenness_centrality(); 
196  172  
197 
if (weighted_graph_) { // calculate BC for weighted graph 

173 
if (gm_.weighted_graph()) { // calculate BC for weighted graph 

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

175  
198  176 
typedef map<Edge, double> EdgeWeightStdMap; 
199  177 
typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap; 
200  178 
EdgeIndexStdMap edge_weight_std_map; 
...  ...  
203  181 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 
204  182 
edge_weight_std_map[edge] = gm_.g_[edge].cost; 
205  183 
} 
206 
boost::brandes_betweenness_centrality(gm_.g_, 

184 
boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_, 

185 
targets_inclusion, 

207  186 
boost::centrality_map( 
208  187 
v_centrality_pmap_).vertex_index_map( 
209  188 
gm_.v_index_pmap()).weight_map( 
...  ...  
211  190 
); 
212  191 
} 
213  192 
else { // for unweighted graph 
214 
boost::brandes_betweenness_centrality(gm_.g_, 

193 
boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_, 

194 
targets_inclusion, 

215  195 
boost::centrality_map( 
216  196 
v_centrality_pmap_).vertex_index_map( 
217  197 
gm_.v_index_pmap()) 
...  ...  
229  209 
} 
230  210 
} 
231  211  
212 
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  
232  223 
void BiConnectedComponents::print_betweenness_centrality() { 
233  224 
BGL_FORALL_VERTICES(v, gm_.g_, Graph) { 
234  225 
double bc_score = boost::get(v_centrality_pmap_, v); 
...  ...  
261  252 
int index = gm_.get_index_from_id(id); 
262  253 
double bc_score = v_centrality_vec_.at(index); 
263  254  
264 
outFile << id << "\t" << bc_score << "\t" << heuristic_bc_score << endl; 

255 
outFile << id << "\t" << setprecision(4) << fixed << bc_score << "\t" << heuristic_bc_score << endl;


265  256 
} 
266  257 
// for (boost::tie(vi, ve) = boost::vertices(gm_.g_); vi != ve; ++vi) { 
267  258 
// string id = gm_.g_[*vi].id; 
...  ...  
277  268 
cout << "\n\nBiConnected Components\n\n"; 
278  269 
cout << gm_; 
279  270  
280 
cout << "\nArticulation points:\n"; 

281 
outops::operator<<(cout, all_art_points_id_); 

282  
283 
cout << "All Sub Components:\n\n"; 

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

285 
cout << " " << i << endl; 

286 
outops::operator<<(cout, BCCs[i].all_vertices_id()); 

287 
} 

271 
print_biconnected_components(); 

288  272  
289  273 
cout << "\nHeuristic Betweenness Centrality Score:\n"; 
290  274 
outops::operator<< <double>(cout, bc_score_); 
...  ...  
294  278  
295  279 
cout << "\nNormal Betweenness Centrality Score:\n"; 
296  280 
print_betweenness_centrality(); 
297  
298 
cout << "Special debugging case\n"; 

299 
BCCs[71].print(); 

300  281 
} 
301  282  
302  283 
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) { 
...  ...  
324  305 
} 
325  306  
326  307 
void BiConnectedComponents::CreateSubComponents() { 
327 
cout << "Create Sub COmponent\n"; 

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

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

310 
} 

311  
328  312 
// Generating subgraph for each subcomponent 
329  313 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) { 
330  314 
Vertex source = boost::source(edge, gm_.g_); 
...  ...  
371  355 
.vertex_id = vertex_id, 
372  356 
.type = type, 
373  357 
}; 
374 
cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n"; 

358 
// cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";


375  359 
Q.push(elem); 
376  360 
} 
377  361 
} 
...  ...  
397  381 
} 
398  382  
399  383 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 
400 
cout << " update weight for comp " << comp_index << "  vertex " << vertex_id << " = " << link_weight << endl; 

384 
// cout << " update weight for comp " << comp_index << "  vertex " << vertex_id << " = " << link_weight << endl;


401  385 
find_unknown_weight_wrt_art_point(vertex_id); 
402  386 
} 
403  387 
Also available in: Unified diff