root / custompackages / graphparser / src / sub_component.cpp @ ee0dd796
History  View  Annotate  Download (9.25 KB)
1 
//


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

3 
//

4  
5 
#include "sub_component.h" 
6  
7  
8 
SubComponent::SubComponent() { 
9 
} 
10  
11 
SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) : art_points(aart_points), subGraph(asubGraph) { 
12 
// SubComponent::SubComponent(VertexVec aart_points, Graph asubGraph) {

13 
// art_points = aart_points;

14 
// subGraph = asubGraph;

15 
// Deep copy for art_points

16 
// cout << "ABC " << endl;

17 
// for (VertexVecIter vi = aart_points.begin(); vi != aart_points.end(); ++vi) {

18 
// Vertex v = Vertex(*vi);

19 
// this>art_points.insert(this>art_points.end(), v);

20 
// cout << " asubGraph " << asubGraph[*vi].name << endl;

21 
// cout << " subGraph " << subGraph[*vi].name << endl;

22 
// }

23  
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  
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(); 
58 
} 
59  
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(); 
100 
} 
101  
102 
VertexVec SubComponent::get_art_points() { 
103 
return art_points;

104 
} 
105  
106 
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 
} 
165 
} 
166  
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 
} 
174  
175 
// Reset the main diagonal to 0

176 
for (int j = 0; j < size; ++j) { 
177 
trafficMatrix[j][j] = 0;

178 
} 
179 
} 
180  
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 
try {

190 
return boost::get(v_index_map, v);

191 
} 
192 
catch (exception& e) {

193 
// TODO handle exception here

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

195 
return 1; 
196 
} 
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 
try {

232 
return trafficMatrix[i_1][i_2];

233 
} 
234 
catch (exception& e) {

235 
cout << "ERROR: getTrafficMatrix: " << e.what() << endl;

236 
} 
237  
238 
} 
239  
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  
254 
} 
255  
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; 
267 
} 
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; 
273 
} 
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 
} 
293  
294 
void SubComponent::printBetweennessCentrality() {

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

296  
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 
} 
303 
} 