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

5  5 
#include "bi_connected_components.h" 
6  6 
using namespace std; 
7  7  
8 
BiConnectedComponents::BiConnectedComponents(const Graph &g) : g(g) { 

8 
/****************************** 

9 
* Public functions 

10 
******************************/ 

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

12 
cout << "BCC constructor \n"; 

9  13 
init(); 
10 
findBiConnectedComponents();


14 
FindBiConnectedComponents();


11  15 
} 
12  16  
13  
14  17 
void BiConnectedComponents::init() { 
15 
size_t i = 0; // for indexing in the loop 

16  
17 
// Populate the e_index_map, by changing the value of the original e_index_std_map 

18 
e_index_map = EdgeIndexMap(e_index_std_map); 

19 
i = 0; 

20 
BGL_FORALL_EDGES(edge, g, Graph) { 

21 
e_index_std_map.insert(pair<Edge, size_t>(edge, i)); 

22 
++i; 

23 
} 

18 
// Set some variables 

19 
num_of_vertices_ = boost::num_vertices(gm_.g_); 

24  20  
25 
this>component_vec = ComponentVec(boost::num_edges(g), 0); 

26 
this>component_map = ComponentMap(this>component_vec.begin(), e_index_map); 

27  
28 
// Populate the VertexIndexMap  by using the put() from Property Map 

29 
v_index_map = VertexIndexMap(v_index_std_map); 

30 
Viter vi, ve; // vertex_iterator, vertex_iterator_end 

31 
i = 0; 

32 
for (boost::tie(vi, ve) = boost::vertices(g); vi != ve; ++vi) { 

33 
boost::put(this>v_index_map, *vi, i); 

34 
++i; 

35 
} 

21 
component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0); 

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

36  23 
} 
37  24  
38 
void BiConnectedComponents::findBiConnectedComponents() { 

39 
cout << "Running findBiConnectedComponents" << endl; 

40 
size_t i; 

25 
/* GETTER */ 

26 
StringSet const& BiConnectedComponents::all_art_points_id() const { 

27 
return all_art_points_id_; 

28 
} 

41  29  
30 
/* SUBCOMPONENT */ 

31 
void BiConnectedComponents::FindBiConnectedComponents() { 

32 
cout << "Running FindBiConnectedComponents" << endl; 

42  33  
43 
boost::biconnected_components(g, component_map,


44 
back_inserter(art_points), 

45 
boost::vertex_index_map(this>v_index_map));


34 
boost::biconnected_components(gm_.g_, component_map_,


35 
back_inserter(art_points_),


36 
boost::vertex_index_map(gm_.v_index_map()));


46  37  
47 
cout << "Articulation points: \n"; 

48 
set<string> art_point_ids; 

49 
graphext::id_of_vertices(g, art_points, art_point_ids); 

50 
outops::operator<<(cout, art_point_ids); 

38 
// Set some variables 

39 
graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_); 

51  40  
52  41 
// Process the result from boost::biconnected_components 
53 
BCCs = Component_t(num_bcc()); 

54 
verticesInBCC(); 

55 
// testVerticesInBCC(); 

56 
processArtPoints(); 

57 
// testProcessArtPoints(); 

58 
// _test_set_difference(); 

59 
createSubComponents(); 

60 
} 

42 
BCCs = Component_t(num_of_bcc()); 

43 
CreateSubComponents(); 

61  44  
62 
void BiConnectedComponents::createSubComponents() { 

63 
// Generating articulation points for each subcomponent 

64 
for (int i = 0; i < num_bcc(); ++i) { 

65 
StringSet art_point_ids; 

66 
VertexVec art_points_vec; 

67 
art_points_vec = get_art_points_for_component(i); 

68 
graphext::id_of_vertices(g, art_points_vec, art_point_ids); 

45 
// Calculate Link Weight 

46 
cout << "Calculate Link Weight\n"; 

47 
CalculateLinkWeight(); 

69  48  
70 
outops::operator<<(cout, art_point_ids);


71 
BCCs[i].set_art_points(art_point_ids);


72 
}


49 
// Calculate Traffic Matrix


50 
cout << "Calculate Traffic Matrix\n";


51 
CalculateTrafficMatrix();


73  52  
53 
print(); 

54 
} 

55  
56 
void BiConnectedComponents::CreateSubComponents() { 

74  57 
// Generating subgraph for each subcomponent 
75 
BGL_FORALL_EDGES(edge, g, Graph) { 

76 
int comp_index = boost::get(component_map, edge); 

77 
Router r1 = g[boost::source(edge, g)];


78 
Router r2 = g[boost::target(edge, g)];


79 
Link l = g[edge]; 

58 
BGL_FORALL_EDGES(edge, gm_.g_, Graph) {


59 
int comp_index = boost::get(component_map_, edge);


60 
Router r1 = gm_.g_[boost::source(edge, gm_.g_)];


61 
Router r2 = gm_.g_[boost::target(edge, gm_.g_)];


62 
Link l = gm_.g_[edge];


80  63 
BCCs[comp_index].AddEdge(r1, r2, l); 
81  64 
} 
82  65  
83 
for (int i = 0; i < num_bcc(); ++i) { 

84 
cout << BCCs[i] << endl; 

66 
// Finalizing each sub components 

67 
for (int i = 0; i < num_of_bcc(); ++i) { 

68 
BCCs[i].FinalizeSubComponent(all_art_points_id_); 

85  69 
} 
86  70 
} 
87  71  
88 
void BiConnectedComponents::print() { 

89 
// Test the biconnected components 

90 
Eiter ei, ei_end; 

91 
size_t i = 0; 

92 
for (boost::tie(ei, ei_end) = boost::edges(g); ei != ei_end; ++ei) { 

93 
string source = g[(*ei).m_source].id; 

94 
string target = g[(*ei).m_target].id; 

95 
edges_size_type comp = this>component_vec.at(i); 

96 
cout << source << " " << target << " " << comp << endl; 

97 
++i; 

72 
/* LINK WEIGHT */ 

73 
void BiConnectedComponents::CalculateLinkWeight() { 

74 
initialize_weight(); 

75 
initialize_queue(); 

76  
77 
while (!Q.empty()) { 

78 
QueueElem elem = Q.front(); 

79 
Q.pop(); 

80 
int comp_index = elem.component_index; 

81 
string vertex_id = elem.vertex_id; 

82  
83 
if (elem.type == "component_vertex_pair") { 

84 
// cout << "component_vertex_pair: " << comp_index << "  " << vertex_id << endl; 

85 
process_component_vertex_pair(comp_index, vertex_id); 

86 
} 

87 
else if (elem.type == "vertex_component_pair") { 

88 
// cout << "vertex_component_pair: " << comp_index << "  " << vertex_id << endl; 

89 
process_vertex_component_pair(comp_index, vertex_id); 

90 
} 

98  91 
} 
99  92 
} 
100  93  
101 
int BiConnectedComponents::num_bcc() { 

102 
if (num_of_bcc == 1) { // calculate it 

94 
/* TRAFFIC MATRIX */ 

95 
void BiConnectedComponents::CalculateTrafficMatrix() { 

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

97 
BCCs[i].CalculateTrafficMatrix(); 

98 
} 

99 
} 

100  
101 
/* HELPERS */ 

102 
int BiConnectedComponents::num_of_bcc() { 

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

103  104 
// +1 to counteract for the zeroindexing 
104 
num_of_bcc = *std::max_element(component_vec.begin(), component_vec.end()) + 1;


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


105  106 
} 
106  107  
107 
return num_of_bcc; 

108 
return num_of_bcc_;


108  109 
} 
109  110  
110 
void BiConnectedComponents::verticesInBCC() { 

111 
size_t size = num_bcc(); 

112  
113 
vector<set<Vertex> > set_vertices(size); 

111 
/* HELPERS FOR OUTPUTTING RESULT */ 

112 
void BiConnectedComponents::print() { 

113 
for (int i = 0; i < num_of_bcc(); ++i) { 

114 
cout << BCCs[i] << endl; 

115 
} 

116 
} 

114  117  
115 
Edge edge;


116 
Vertex source;


117 
Vertex target;


118 
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {


119 
cout << "\n\nBiConnected Components\n\n";


120 
cout << rhs.gm_;


118  121  
119 
int comp_id; 

120 
BGL_FORALL_EDGES(edge, g, Graph) { 

121 
comp_id = boost::get(component_map, edge); 

122 
source = edge.m_source; 

123 
target = edge.m_target; 

124 
set_vertices[comp_id].insert(source); 

125 
set_vertices[comp_id].insert(target); 

126 
} 

122 
cout << "\nArticulation points:\n"; 

123 
outops::operator<<(cout, rhs.all_art_points_id()); 

124 
return os; 

127  125  
128 
bcc_vertices = vector<VertexVec>(size); 

129 
size_t i = 0; 

130 
for (i = 0; i < size; ++i) { 

131 
bcc_vertices[i] = vector<Vertex>(set_vertices[i].begin(), set_vertices[i].end()); 

132 
} 

126 
// TODO: output the result of BCC 

127 
// Test the biconnected components 

128 
// Eiter ei, ei_end; 

129 
// size_t i = 0; 

130 
// for (boost::tie(ei, ei_end) = boost::edges(gm_.g_); ei != ei_end; ++ei) { 

131 
// string source = gm_.g_[(*ei).m_source].id; 

132 
// string target = gm_.g_[(*ei).m_target].id; 

133 
// edges_size_type comp = component_vec_.at(i); 

134 
// cout << source << " " << target << " " << comp << endl; 

135 
// ++i; 

136 
// } 

133  137 
} 
134  138  
135 
void BiConnectedComponents::testVerticesInBCC() { 

136 
size_t i = 0; 

137 
for (i; i < num_of_bcc; ++i) { 

138 
vector<Vertex> abc = bcc_vertices[i]; 

139 
cout << "vertices in BCC " << i << endl; 

140 
for (int j = 0; j < abc.size(); ++j) { 

139 
/****************************** 

140 
* Private functions 

141 
******************************/ 

141  142  
142 
cout << g[bcc_vertices[i][j]].id << endl; 

143 
} 

143 
/* LINK WEIGHT */ 

144 
void BiConnectedComponents::initialize_weight() { 

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

146 
BCCs[i].initialize_weight(); 

144  147 
} 
145  148 
} 
146  149  
147 
bool BiConnectedComponents::hasVertex(Vertex v, int comp_index) { 

148 
vector<Vertex> vv = bcc_vertices[comp_index]; 

149 
vector<Vertex>::iterator it; 

150  
151 
it = std::find(vv.begin(), vv.end(), v); 

152 
if (it == vv.end()) { 

153 
return false; 

154 
} 

155 
else { 

156 
return true; 

150 
void BiConnectedComponents::initialize_queue() { 

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

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

153 
string vertex_id = *(BCCs[i].art_points_id().begin()); 

154 
string type = "component_vertex_pair"; 

155 
QueueElem elem = { 

156 
.component_index = i, 

157 
.vertex_id = vertex_id, 

158 
.type = type, 

159 
}; 

160  
161 
Q.push(elem); 

162 
} 

157  163 
} 
158  164 
} 
159  165  
160 
void BiConnectedComponents::processArtPoints() { 

161 
// For each articulation points, quickly identify (through the std::map) all the component containing those points. 

162 
art_point_component_map = ArtPointComponentMap(art_point_component_std_map); 

163  
164 
std::vector<Vertex>::iterator vi = art_points.begin(); 

165 
std::vector<int>::iterator ii; 

166  
167 
for (vi; vi < art_points.end(); ++vi) { 

168 
Vertex articulation_point = *vi; 

169  
170 
size_t i = 0; 

171 
std::vector<int> components; 

172 
for (i = 0; i < num_of_bcc; ++i) { 

173 
ii = components.end(); 

174 
if (hasVertex(articulation_point, i)) { 

175 
components.insert(ii, i); 

166 
void BiConnectedComponents::process_component_vertex_pair(int comp_index, string vertex_id) { 

167 
int size = BCCs[comp_index].num_of_vertices()  1; 

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

169 
if (s.compare(vertex_id) != 0) { 

170 
int weight = BCCs[comp_index].get_weight_map(s); 

171 
if (weight != 1) { 

172 
size += num_of_vertices_  weight  1; 

176  173 
} 
177  174 
} 
178 
boost::put(art_point_component_map, articulation_point, components); 

179 
} 

180  
181 
// For each component, quickly identify (through the std::map) all the articulation points belonging to it. 

182 
component_art_point_map = ComponentArtPointMap(component_art_point_std_map); 

183  
184 
BccIter_t bi = bcc_vertices.begin(); 

185 
BccIter_t bi_end = bcc_vertices.end(); 

186  
187 
VertexVecIter vvi = art_points.begin(); 

188 
VertexVecIter vvi_end = art_points.end(); 

189  
190 
int i = 0; 

191 
for (bi; bi != bi_end; ++bi) { 

192 
// intersection 

193 
VertexVec component = *bi; 

194 
VertexVec intersection_result; 

195 
std::set_intersection(component.begin(), component.end(), vvi, vvi_end, back_inserter(intersection_result)); 

196  
197 
boost::put(component_art_point_map, i, intersection_result); 

198 
++i; 

199  
200  175 
} 
176 
int link_weight = size; 

177 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 

178 
find_unknown_weight_wrt_art_point(vertex_id); 

201  179 
} 
202  180  
181 
void BiConnectedComponents::find_unknown_weight_wrt_art_point(string vertex_id) { 

182 
int count = 0; 

183 
int comp_index = 1; 

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

185 
if (BCCs[i].vertex_exists(vertex_id)) { 

186 
if (BCCs[i].get_weight_map(vertex_id) == 1) { 

187 
++count; 

188 
comp_index = i; 

189 
} 

203  190  
204 
void BiConnectedComponents::testProcessArtPoints() { 

205 
std::vector<Vertex>::iterator vi = art_points.begin(); 

206 
std::vector<int>::iterator ii; 

207  
208 
for (vi; vi < art_points.end(); ++vi) { 

209 
Vertex articulation_point = *vi; 

210  
211 
std::vector<int> components = boost::get(art_point_component_map, articulation_point); 

212  
213 
cout << "Components belonging to articulation point " << g[articulation_point].label << endl; 

214  
215 
for (ii = components.begin(); ii < components.end(); ++ii) { 

216 
cout << *ii << endl; 

191 
if (count > 1) break; 

217  192 
} 
218  193 
} 
219  194  
220 
VertexVecIter vvi; 

221 
int i = 0; 

222 
for (i; i < num_bcc(); ++i) { 

223 
VertexVec vv = boost::get(component_art_point_map, i); 

195 
if (count == 1) { 

196 
// Add new element to QueueElem 

197 
QueueElem elem = { 

198 
.component_index = comp_index, 

199 
.vertex_id = vertex_id, 

200 
.type = "vertex_component_pair" 

201 
}; 

224  202  
225 
cout << "Articulation points from the component " << i << endl; 

226  
227 
for (vvi = vv.begin(); vvi != vv.end(); ++vvi) { 

228 
cout << *vvi << endl; 

229 
} 

203 
// cout << "Add vertex_component_pair: " << comp_index << "  " << vertex_id << endl; 

204 
Q.push(elem); 

230  205 
} 
231  206 
} 
232  207  
233 
VertexVec BiConnectedComponents::get_art_points_for_component(int comp_index) { 

234 
return boost::get(component_art_point_map, comp_index); 

235 
} 

236  
237 
vector<int> BiConnectedComponents::get_components_for_art_point(Vertex vertex) { 

238 
return boost::get(art_point_component_map, vertex); 

239 
} 

240  
241 
int BiConnectedComponents::num_of_vertices_in_component(int comp_index) { 

242 
return bcc_vertices[comp_index].size(); 

243 
} 

208 
void BiConnectedComponents::process_vertex_component_pair(int comp_index, string vertex_id) { 

209 
int size = 0; 

244  210  
245 
VertexVec BiConnectedComponents::get_normal_vertices_for_component(int comp_index) { 

246 
VertexVec normal_points; 

247 
std::set_difference(bcc_vertices[comp_index].begin(), 

248 
bcc_vertices[comp_index].end(), 

249 
art_points.begin(), 

250 
art_points.end(), 

251 
back_inserter(normal_points) 

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

212 
if (i != comp_index) { 

213 
if (BCCs[i].vertex_exists(vertex_id)) { 

214 
int weight = BCCs[i].get_weight_map(vertex_id); 

215 
if (weight != 1) { 

216 
size += weight; 

217 
} 

218 
} 

219 
} 

220 
} 

252  221  
253 
); 

254 
return normal_points; 

222 
int link_weight = num_of_vertices_  1  size; 

223 
BCCs[comp_index].update_weight_map(vertex_id, link_weight); 

224 
find_unknown_weight_wrt_component(comp_index); 

255  225 
} 
256  226  
257 
// void BiConnectedComponents::compute_weight() { 

258 
// _initialize_weight(); 

259 
// _initialize_queue(); 

260  
261 
// while (!Q.empty()) { 

262 
// QueueElem elem = Q.front(); 

263 
// Q.pop(); 

264 
// int comp_index = elem.component_index; 

265 
// Vertex current_art_point = elem.art_point; 

266  
267 
// if (elem.type == "component_vertex_pair") { 

268 
// int size = BCCs[comp_index].num_vertices()  1; 

269 
// VertexVec art_points = BCCs[comp_index].art_points(); 

270  
271 
// // TODO: I assume here that vvi != art_points.end(), aka. the element is always found. 

272 
// VertexVecIter vvi; 

273 
// vvi = std::find(art_points.begin(), art_points.end(), current_art_point); 

274 
// try { 

275 
// art_points.erase(vvi); 

276 
// } 

277 
// catch (exception& e) { 

278 
// cout << "Standard exception: " << e.what() << endl; 

279 
// } 

280  
281 
// for (vvi = art_points.begin(); vvi != art_points.end(); ++vvi) { 

282 
// cout << " " << g[*vvi].label << endl; 

283 
// int weight = BCCs[comp_index].getWeight(*vvi); 

284 
// if (weight != 1) { 

285 
// size += boost::num_vertices(g)  weight  1; 

286 
// } 

287 
// } 

288  
289 
// int link_weight = size; 

290 
// // _verify_weight(comp_index, current_art_point, link_weight); 

291 
// BCCs[comp_index].setWeight(current_art_point, link_weight); 

292  
293 
// _find_unknown_weight_wrt_art_point(current_art_point); 

294 
// } 

295  
296 
// if (elem.type == "vertex_component_pair") { 

297 
// vector<int> comp_indices = get_components_for_art_point(current_art_point);; 

298  
299 
// vector<int>::iterator vi; 

300 
// vi = std::find(comp_indices.begin(), comp_indices.end(), comp_index); 

301 
// try { 

302 
// comp_indices.erase(vi); 

303 
// } 

304 
// catch (exception& e) { 

305 
// cout << "Standard exception: " << e.what() << endl; 

306 
// } 

307  
308 
// int size = 0; 

309 
// for (vi = comp_indices.begin(); vi != comp_indices.end(); ++vi) { 

310 
// int weight = BCCs[*vi].getWeight(current_art_point); 

311 
// if (weight != 1) { 

312 
// size += weight; 

313 
// } 

314 
// } 

315  
316 
// int link_weight = boost::num_vertices(g)  1  size; 

317 
// // _verify_weight(comp_index, current_art_point, link_weight); 

318 
// BCCs[comp_index].setWeight(current_art_point, link_weight); 

319 
// _find_unknown_weight_wrt_component(comp_index); 

320  
321 
// } 

322 
// } 

323 
// } 

324  
325 
// void BiConnectedComponents::_initialize_weight() { 

326 
// ComponentIter_t ci; 

327 
// for (ComponentIter_t ci = BCCs.begin(); ci != BCCs.end(); ++ci) { 

328 
// (*ci)._initialize_weight(); 

329 
// } 

330 
// } 

331  
332 
// void BiConnectedComponents::_initialize_queue() { 

333 
// VertexVecIter vvi; 

334  
335 
// int i = 0; 

336 
// VertexVec current_art_points; 

337 
// for (i; i < num_bcc(); ++i) { 

338 
// current_art_points = BCCs[i].art_points(); 

339 
// if (curr ent_art_points.size() == 1) { 

340 
// // creating element for queue Q 

341 
// Vertex art_point = current_art_points[0]; 

342 
// string type = "component_vertex_pair"; 

343 
// QueueElem qe = { 

344 
// .component_index = i, 

345 
// .art_point = art_point, 

346 
// .type = type, 

347 
// }; 

348  
349 
// Q.push(qe); 

350 
// } 

351 
// } 

352 
// } 

353  
354 
// void BiConnectedComponents::_find_unknown_weight_wrt_art_point(Vertex art_point) { 

355 
// int num_of_uncomputed_weight = 0; 

356 
// vector<int> uncomputed_weight_component_indices; 

357  
358 
// size_t i; 

359 
// for (i = 0; i < num_bcc(); ++i) { 

360 
// if (hasVertex(art_point, i)) { 

361 
// // Check if value 1 appear exactly 1 time 

362 
// if (BCCs[i].getWeight(art_point) == 1) { 

363 
// num_of_uncomputed_weight += 1; 

364 
// uncomputed_weight_component_indices.insert(uncomputed_weight_component_indices.end(), i); 

365 
// } 

366 
// } 

367  
368 
// if (num_of_uncomputed_weight > 1) { 

369 
// break; 

370 
// } 

371 
// } 

372  
373 
// if (num_of_uncomputed_weight == 1) { 

374 
// QueueElem elem = { 

375 
// component_index: uncomputed_weight_component_indices[0], 

376 
// art_point: art_point, 

377 
// type: "vertex_component_pair", 

378 
// }; 

379 
// Q.push(elem); 

380 
// } 

381 
// } 

382  
383 
// void BiConnectedComponents::_find_unknown_weight_wrt_component(int comp_index) { 

384 
// VertexVec unknown_weight_vertices; 

385 
// BCCs[comp_index]._find_vertices_with_unknown_weight(unknown_weight_vertices); 

386  
387 
// if (unknown_weight_vertices.size() == 1) { 

388 
// QueueElem elem = { 

389 
// .component_index = comp_index, 

390 
// .art_point = unknown_weight_vertices[0], 

391 
// .type = "component_vertex_pair", 

392 
// }; 

393  
394 
// Q.push(elem); 

395 
// } 

396 
// } 

397  
398 
// void BiConnectedComponents::print_weight() { 

399 
// for (int i = 0; i < num_bcc(); ++i) { 

400 
// BCCs[i].printWeight(); 

401 
// } 

402 
// } 

403  
404 
// void BiConnectedComponents::findBetweennessCentrality() { 

405 
// for (int i = 0; i < num_bcc(); ++i) { 

406 
// // BCCs[i]._computeTrafficMatrix(); 

407 
// cout << "###########" << endl; 

408 
// _print_art_points(); 

409 
// cout << "###########" << endl; 

410 
// BCCs[i].findBetweennessCentrality(); 

411 
// } 

412 
// } 

413  
414 
// void BiConnectedComponents::printBetweennessCentrality() { 

415 
// for (int i = 0; i < num_bcc(); ++i) { 

416 
// BCCs[i].printBetweennessCentrality(); 

417 
// } 

418 
// } 

419  
420 
// void BiConnectedComponents::_print_art_points() { 

421 
// for (int i = 0; i < art_points.size(); ++i) { 

422 
// cout << &art_points[i] << endl; 

423 
// } 

424 
// } 

425  
426 
// void BiConnectedComponents::_test_set_difference() { 

427 
// VertexVec component = bcc_vertices[0]; 

428 
// VertexVec intersection_result; 

429  
430 
// cout << "******** Test set_difference ********" << endl; 

431 
// cout << " Component" << endl; 

432 
// for (VertexVecIter vvi = component.begin(); vvi != component.end(); ++vvi) { 

433 
// cout << "\t" << *vvi << endl; 

434 
// } 

435 
// cout << " Articulation points" << endl; 

436 
// cout << " " << &art_points[0] << endl; 

437 
// cout << " " << &art_points[1] << endl; 

438  
439 
// for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) { 

440 
// cout << "\t" << *vvi << endl; 

441 
// } 

442  
443 
// VertexVec copy_art_points = VertexVec(art_points); 

444 
// cout << " Copy Articulation points" << endl; 

445 
// cout << " " << ©_art_points << endl; 

446 
// // cout << " " << &(*copy_art_points) << endl; 

447 
// cout << " " << &(copy_art_points[0]) << " " << copy_art_points[0] << endl; 

448 
// cout << " " << &(*(©_art_points[0])) << " " << *(©_art_points[0]) << endl; 

449 
// cout << " " << ©_art_points[1] << " " << copy_art_points[1] << endl; 

450 
// for (VertexVecIter vvi = copy_art_points.begin(); vvi != copy_art_points.end(); ++vvi) { 

451 
// cout << "\t" << *vvi << endl; 

452 
// } 

453  
454 
// std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(intersection_result)); 

455  
456 
// cout << " Intersection result" << endl; 

457 
// for (VertexVecIter vvi = intersection_result.begin(); vvi != intersection_result.end(); ++vvi) { 

458 
// cout << "\t" << *vvi << endl; 

459 
// } 

460  
461 
// VertexVec difference_result; 

462 
// std::set_intersection(component.begin(), component.end(), art_points.begin(), art_points.end(), back_inserter(difference_result)); 

463  
464 
// cout << " Difference result" << endl; 

465 
// for (VertexVecIter vvi = difference_result.begin(); vvi != difference_result.end(); ++vvi) { 

466 
// cout << "\t" << *vvi << endl; 

467 
// } 

468 
// } 

227 
void BiConnectedComponents::find_unknown_weight_wrt_component(int comp_index) { 

228 
// The 'counting' solution is found here: http://stackoverflow.com/questions/5517615/countingnumberofsamevaluesinmap 

229 
typedef NameToIntMap::value_type MapEntry; 

230 
int count = std::count_if( 

231 
BCCs[comp_index].weight_map().begin(), 

232 
BCCs[comp_index].weight_map().end(), 

233 
second_equal_to<MapEntry>(1)); 

234  
235 
if (count == 1) { 

236 
// Find the vertex id for the vertex with unknown link weight 

237 
string vertex_id = BCCs[comp_index].first_vertex_id_with_unknown_weight(); 

238  
239 
QueueElem elem = { 

240 
.component_index = comp_index, 

241 
.vertex_id = vertex_id, 

242 
.type = "component_vertex_pair", 

243 
}; 

244 
// cout << "Add component_vertex_pair: " << comp_index << "  " << vertex_id << endl; 

245 
Q.push(elem); 

246 
} 

247 
} 
Also available in: Unified diff