Revision efed924d custompackages/graphparser/src/sub_component.cpp
custompackages/graphparser/src/sub_component.cpp  

6  6  
7  7  
8  8 
SubComponent::SubComponent() { 
9 
// do nothing 

9  10 
} 
10  11  
11 
SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) : art_points(aart_points), subGraph(asubGraph) {


12 
SubComponent::SubComponent(StringSet art_points, Graph sub_graph) : art_points_(art_points), sub_graph_(sub_graph) {


12  13 
// SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) { 
13  14 
// art_points = aart_points; 
14  15 
// subGraph = asubGraph; 
...  ...  
21  22 
// cout << " subGraph " << subGraph[*vi].name << endl; 
22  23 
// } 
23  24  
24 
// Test if deep copy is performed for aart_points 

25 
cout << "Test if deep copy is performed for art_points" << endl; 

26 
cout << "&art_points " << &aart_points << endl; 

27 
cout << "&this>art_points " << &this>art_points << endl; 

28 
cout << "art_points[0] " << aart_points[0] << endl; 

29 
cout << "this>art_points[0] " << this>art_points[0] << endl; 

30  25  
31 
// create Vertex > Index Mapping 

32 
v_index_map = VertexIndexMap(v_index_std_map); 

33 
int i = 0; 

34 
BGL_FORALL_VERTICES(vertex, this>subGraph, Graph) { 

35 
boost::put(v_index_map, vertex, i); 

36 
++i; 

37 
} 

38  
39 
// Deep copy for subGraph 

40 
// TODO: optimize  is there anyway that we can avoid using deep copy 

41  
42 
// This is not working 

43 
// copy_graph(asubGraph, this>subGraph, vertex_index_map(v_index_map)); 

44  
45 
// this>subGraph = Graph(asubGraph); 

46  
47 
// Vertices in this>subGraph 

48 
cout << "Vertices in this>subGraph  constructor" << endl; 

49 
BGL_FORALL_VERTICES(vertex, this>subGraph, Graph) { 

50 
cout << vertex << " " << this>subGraph[vertex].name << endl; 

51 
} 

52  
53 
cout << "Vertices in asubGraph  constructor" << endl; 

54 
BGL_FORALL_VERTICES(vertex, asubGraph, Graph) { 

55 
cout << vertex << " " << asubGraph[vertex].name << endl; 

56 
} 

57 
init(); 

26 
// init(); 

58  27 
} 
59  28  
60 
void SubComponent::init() { 

61 
// create list of normal vertices 

62 
Viter vi, vi_end; 

63 
boost::tie(vi, vi_end) = boost::vertices(subGraph); 

64 
std::set_difference(vi, vi_end, 

65 
art_points.begin(), art_points.end(), 

66 
back_inserter(normal_vertices) 

67 
); 

68  
69  
70 
cout << "Vertices in this>subGraph  init()" << endl; 

71 
BGL_FORALL_VERTICES(vertex, this>subGraph, Graph) { 

72 
cout << vertex << " " << this>subGraph[vertex].name << endl; 

73 
} 

74  
75 
cout << "Test normal_vertices  init()" << endl; 

76 
for (vector<Vertex>::iterator vi = normal_vertices.begin(); vi != normal_vertices.end(); ++vi) { 

77 
cout << *vi << " "; 

78 
cout << subGraph[*vi].name << endl; 

79 
} 

80  
81 
/* STEP 1 

82 
** Compute Link Weight 

83 
** ==> Link Weight is computed by the main Bi Connected Components. 

84 
** That main BCC will set the Link Weight value for each subcomponent. 

85 
*/ 

86  
87 
/* STEP 2 

88 
** Compute Traffic Matrix 

89 
*/ 

90 
// _initializeTrafficMatrix(); 

91 
// _computeTrafficMatrix(); 

92  
93 
/* STEP 3 

94 
** Compute the Betweenness Centrality 

95 
** The calculation is executed by the main BCCs calling each subcomponent 

96 
*/ 

97 
// Initialize variables for calculating BC 

98 
_initializeBetweennessCentrality(); 

99 
findBetweennessCentrality(); 

29 
StringSet SubComponent::art_points() const { 

30 
return art_points_; 

100  31 
} 
101  32  
102 
VertexVec SubComponent::get_art_points() {


103 
return art_points;


33 
void SubComponent::set_art_points(StringSet& art_points) {


34 
art_points_ = art_points;


104  35 
} 
105  36  
106  37 
int SubComponent::num_vertices() { 
107 
return boost::num_vertices(subGraph); 

108 
} 

109  
110 
void SubComponent::_initialize_weight() { 

111 
for (VertexVecIter vvi = art_points.begin(); vvi != art_points.end(); ++vvi) { 

112 
setWeight(*vvi, 1); 

113 
} 

114 
} 

115  
116 
void SubComponent::setWeight(Vertex art_point, int value) { 

117 
weightMap[art_point] = value; 

118 
} 

119  
120 
int SubComponent::getWeight(Vertex art_point) { 

121 
VertexMapIter vmi; 

122  
123 
vmi = weightMap.find(art_point); 

124  
125 
if (vmi != weightMap.end()) { 

126 
return weightMap.at(art_point); 

127 
} 

128 
else { 

129 
return 0; 

130 
} 

131 
} 

132  
133 
int SubComponent::getReversedWeight(Vertex art_point) { 

134 
VertexMapIter vmi; 

135  
136 
vmi = weightMap.find(art_point); 

137  
138 
if (vmi != weightMap.end()) { 

139 
return (boost::num_vertices(subGraph)  weightMap.at(art_point)  1); 

140 
} 

141 
else { 

142 
return 0; 

143 
} 

144 
} 

145  
146 
void SubComponent::printWeight() { 

147 
for (VertexMapIter vmi = weightMap.begin(); vmi != weightMap.end(); ++vmi) { 

148 
cout << subGraph[(*vmi).first].name << " = " << (*vmi).second << endl; 

149 
} 

150 
} 

151  
152 
void SubComponent::_find_vertices_with_unknown_weight(VertexVec& unknown_weight_vertices) { 

153 
VertexMapIter wi; 

154 
Vertex vertex; 

155  
156 
int current_weight; 

157 
for (wi = weightMap.begin(); wi != weightMap.end(); ++wi) { 

158 
vertex = (*wi).first; 

159 
current_weight = (*wi).second; 

160  
161 
if (current_weight == 1) { 

162 
unknown_weight_vertices.insert(unknown_weight_vertices.end(), vertex); 

163 
} 

164 
} 

38 
return boost::num_vertices(sub_graph_); 

165  39 
} 
166  40  
167 
void SubComponent::_initializeTrafficMatrix() { 

168 
// generate_empty_traffic_matrix, with 1 every where, and 0 in the main diagonal 

169 
int size = boost::num_vertices(subGraph); 

170 
trafficMatrix = vector<vector<int> >(size); 

171 
for (int j = 0; j < size; ++j) { 

172 
trafficMatrix[j] = vector<int>(size, 1); 

173 
} 

41 
void SubComponent::AddEdge(Router r1, Router r2, Link l) { 

42 
cout << "add edge " << r1.label << "  " << r2.label << endl; 

174  43  
175 
// Reset the main diagonal to 0 

176 
for (int j = 0; j < size; ++j) { 

177 
trafficMatrix[j][j] = 0; 

178 
} 

179 
} 

44 
string s1 = r1.id; 

45 
string s2 = r2.id; 

46 
Vertex v1; 

47 
Vertex v2; 

180  48  
181 
void SubComponent::_setTrafficMatrix(Vertex v_1, Vertex v_2, int value) { 

182 
int i_1 = _indexOfVertex(v_1); 

183 
int i_2 = _indexOfVertex(v_2); 

184 
trafficMatrix[i_1][i_2] = value; 

185 
trafficMatrix[i_2][i_1] = value; // because Traffic Matrix is symmetric 

186 
} 

187  
188 
int SubComponent::_indexOfVertex(Vertex v) { 

189  49 
try { 
190 
return boost::get(v_index_map, v);


50 
v1 = get_vertex_from_id(s1);


191  51 
} 
192  52 
catch (exception& e) { 
193 
// TODO handle exception here 

194 
cout << "ERROR _indexOfVertex() " << e.what() << endl; 

195 
return 1; 

53 
v1 = boost::add_vertex(r1, sub_graph_); 

54 
name_vertex_map_[s1] = v1; 

196  55 
} 
197 
} 

198  
199 
void SubComponent::_computeTrafficMatrix() { 

200 
// Update the value when one vertex is a cutpoint, another vertex is not a cutpoint 

201 
for (int j = 0; j < art_points.size(); ++j) { 

202 
for (int k = 0; k < normal_vertices.size(); ++k) { 

203 
int communication_intensity = getReversedWeight(art_points[j]) + 1; 

204 
_setTrafficMatrix(art_points[j], normal_vertices[k], communication_intensity); 

205 
} 

206 
} 

207  
208 
// Update the value when both vertices are cutpoints 

209 
int size = art_points.size(); 

210 
if (size > 1) { 

211 
for (int j = 0; j < size  1; ++j) { 

212 
for (int k = 1; k < size; ++k) { 

213 
if (j == k) { 

214 
continue; 

215 
} 

216  
217 
int communication_intensity = ( 

218 
(getReversedWeight(art_points[j]) + 1) * 

219 
(getReversedWeight(art_points[k]) + 1) 

220 
); 

221  
222 
_setTrafficMatrix(art_points[j], art_points[k], communication_intensity); 

223 
} 

224 
} 

225 
} 

226 
} 

227  
228 
int SubComponent::getTrafficMatrix(Vertex v_1, Vertex v_2) { 

229 
int i_1 = _indexOfVertex(v_1); 

230 
int i_2 = _indexOfVertex(v_2); 

231  56 
try { 
232 
return trafficMatrix[i_1][i_2];


57 
v2 = get_vertex_from_id(s2);


233  58 
} 
234  59 
catch (exception& e) { 
235 
cout << "ERROR: getTrafficMatrix: " << e.what() << endl; 

60 
v2 = boost::add_vertex(r2, sub_graph_); 

61 
name_vertex_map_[s2] = v2; 

236  62 
} 
237  
63 
boost::add_edge(v1, v2, l, sub_graph_); 

238  64 
} 
239  65  
240 
void SubComponent::_initializeBetweennessCentrality() { 

241 
v_centrality_vec = CentralityVec(boost::num_vertices(subGraph), 0); 

242 
v_centrality_map = CentralityMap(v_centrality_vec.begin(), v_index_map); 

243 
cout << "Test v_index_map" << endl; 

244 
BGL_FORALL_VERTICES(vertex, subGraph, Graph) { 

245 
cout << subGraph[vertex].name << " " << boost::get(v_index_map, vertex) << endl; 

246 
} 

247  
248 
cout << "Vertices in this>subGraph  init BC()" << endl; 

249 
BGL_FORALL_VERTICES(vertex, this>subGraph, Graph) { 

250 
cout << vertex << " " << this>subGraph[vertex].id << endl; 

251 
} 

252  
253  
66 
bool SubComponent::vertex_existed(string s) { 

67 
std::map<std::string, Vertex>::iterator it; 

68 
it = name_vertex_map_.find(s); 

69 
return (it != name_vertex_map_.end()); 

254  70 
} 
255  71  
256 
void SubComponent::findBetweennessCentrality() { 

257 
cout << "****** find BC() *******" << endl; 

258 
cout << "Test art_points" << endl; 

259 
for (VertexVecIter vi = art_points.begin(); vi != art_points.end(); ++vi) { 

260 
cout << *vi << " "; 

261 
cout << subGraph[*vi].name << endl; 

262 
} 

263  
264 
cout << "Vertices in this>subGraph  find BC()" << endl; 

265 
BGL_FORALL_VERTICES(vertex, this>subGraph, Graph) { 

266 
cout << vertex << " " << this>subGraph[vertex].id << endl; 

72 
const Vertex& SubComponent::get_vertex_from_id(string s) { 

73 
if (vertex_existed(s)) { 

74 
return name_vertex_map_[s]; 

267  75 
} 
268  
269 
cout << "Test normal_vertices 2" << endl; 

270 
for (vector<Vertex>::iterator vi = normal_vertices.begin(); vi != normal_vertices.end(); ++vi) { 

271 
cout << *vi << " " << endl; 

272 
cout << subGraph[*vi].name << endl; 

76 
else { 

77 
throw std::runtime_error("Vertex not found\n"); 

273  78 
} 
274 
cout << "BC abc " << endl; 

275 
/* Test v_index_map */ 

276 
// BGL_FORALL_VERTICES(vertex, subGraph, Graph) { 

277 
// cout << subGraph[vertex].name << " " << boost::get(v_index_map, vertex) << endl; 

278 
// } 

279  
280 
// /* Test v_centrality_map 

281 
// ** 

282 
// */ 

283 
// cout << "v_centrality_map" << endl; 

284 
// BGL_FORALL_VERTICES(vertex, subGraph, Graph) { 

285 
// cout << subGraph[vertex].name << endl; 

286 
// // double score = boost::get(v_centrality_map, vertex); 

287 
// // cout << vertex << " " << score << endl; 

288 
// } 

289  
290 
// brandes_betweenness_centrality(subGraph, boost::centrality_map(v_centrality_map).vertex_index_map(v_index_map)); 

291 
cout << "BC done" << endl; 

292  79 
} 
293  80  
294 
void SubComponent::printBetweennessCentrality() { 

295 
cout << "Vertex betweenness" << endl; 

81 
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) { 

82 
cout << "Subcomponent" << endl; 

83 
outops::operator<<(cout, sc.sub_graph()); 

84 
outops::operator<<(cout, sc.art_points()); 

85 
return os; 

86 
} 

296  87  
297 
Viter vi, vi_end; 

298 
int i = 0; 

299 
for (boost::tie(vi, vi_end) = boost::vertices(subGraph); vi != vi_end; ++vi) { 

300 
cout << subGraph[*vi].id << "\t" << v_centrality_vec.at(i) << endl; 

301 
++i; 

302 
} 

88 
Graph const& SubComponent::sub_graph() const { 

89 
return sub_graph_; 

303  90 
} 
91 
Also available in: Unified diff