Revision 437fd680 custompackages/graphparser/src/bi_connected_components.cpp
custompackages/graphparser/src/bi_connected_components.cpp  

19  19 
num_of_vertices_ = boost::num_vertices(gm_.g_); 
20  20  
21  21 
component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0); 
22 
component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_map()); 

22 
component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap());


23  23 
} 
24  24  
25  25 
/* GETTER */ 
26 
int const BiConnectedComponents::num_of_bcc() { 

27 
if (num_of_bcc_ == 1) { // calculate it 

28 
// +1 to counteract for the zeroindexing 

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

30 
} 

31  
32 
return num_of_bcc_; 

33 
} 

34  
35 
int const BiConnectedComponents::num_of_vertices() const { 

36 
return num_of_vertices_; 

37 
} 

38  
26  39 
StringSet const& BiConnectedComponents::all_art_points_id() const { 
27  40 
return all_art_points_id_; 
28  41 
} 
29  42  
43 
NameToDoubleMap const& BiConnectedComponents::bc_score() const { 

44 
return bc_score_; 

45 
} 

46  
30  47 
/* SUBCOMPONENT */ 
31  48 
void BiConnectedComponents::FindBiConnectedComponents() { 
32  49 
cout << "Running FindBiConnectedComponents" << endl; 
33  50  
34  51 
boost::biconnected_components(gm_.g_, component_map_, 
35  52 
back_inserter(art_points_), 
36 
boost::vertex_index_map(gm_.v_index_map())); 

53 
boost::vertex_index_map(gm_.v_index_pmap()));


37  54  
38  55 
// Set some variables 
39  56 
graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_); 
...  ...  
54  71 
cout << "Calculate Betweenness Centrality\n"; 
55  72 
CalculateBetweennessCentrality(); 
56  73  
74 
// Print all the sub components 

57  75 
print(); 
58  76 
} 
59  77  
...  ...  
104  122  
105  123 
/* BETWEENNESS CENTRALITY */ 
106  124 
void BiConnectedComponents::CalculateBetweennessCentrality() { 
125 
cout << "BETWEENNESS CENTRALITY\n"; 

126  
127 
initialize_betweenness_centrality(); 

128  
107  129 
for (int i = 0; i < num_of_bcc_; ++i) { 
130 
cout << "BC for component " << i << endl; 

108  131 
BCCs[i].CalculateBetweennessCentrality(); 
109  132 
} 
133  
134 
double score; 

135 
// Sum the BC for each subcomponent 

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

137 
// For non articulation points 

138 
for (string id: BCCs[i].non_art_points_id()) { 

139 
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; 

148 
} 

149 
} 

150  
151 
// Update the BC score for articulation points 

152 
for (string id : all_art_points_id_) { 

153 
bc_score_[id] = bc_sum_art_points_[id]; 

154  
155 
// 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]; 

157 
} 

158  
159 
cout << "DONE WITH BETWEENNESS CENTRALITY\n"; 

110  160 
} 
111  161  
112 
/* HELPERS */ 

113 
int BiConnectedComponents::num_of_bcc() { 

114 
if (num_of_bcc_ == 1) { // calculate it 

115 
// +1 to counteract for the zeroindexing 

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

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; 

117  166 
} 
118  167  
119 
return num_of_bcc_; 

168 
StringSet all_vertices_id; 

169 
graphext::id_of_all_vertices(gm_.g_, all_vertices_id); 

170  
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; 

175 
} 

176 
} 

177  
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 
} 

183 
} 

120  184 
} 
121  185  
122  186 
/* HELPERS FOR OUTPUTTING RESULT */ 
187  
123  188 
void BiConnectedComponents::print() { 
124  189 
for (int i = 0; i < num_of_bcc(); ++i) { 
125 
cout << BCCs[i] << endl; 

190 
// cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout 

191 
BCCs[i].print(); 

126  192 
} 
127  193 
} 
128  194  
129  195 
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) { 
196 
cout << "MARK\n"; 

130  197 
cout << "\n\nBiConnected Components\n\n"; 
131  198 
cout << rhs.gm_; 
132  199  
133  200 
cout << "\nArticulation points:\n"; 
134  201 
outops::operator<<(cout, rhs.all_art_points_id()); 
202  
203 
cout << "\nBetweenness Centrality Score:\n"; 

204 
outops::operator<< <double>(cout, rhs.bc_score()); 

135  205 
return os; 
136  206  
137  207 
// TODO: output the result of BCC 
Also available in: Unified diff