Revision 24a4abf9 fiddle/heuristicbetweennesscentrality/centrality_biconnected.py
fiddle/heuristicbetweennesscentrality/centrality_biconnected.py  

169  169 
self.cutpoints = cutpoints 
170  170  
171  171 
self.Dv_B = [dict() for i in range(self.num_components)] # link weight 
172 
self.generate_link_weight() 

173 
# self.compute_component_tree_weight()


172 
# self.generate_link_weight()


173 
self.compute_component_tree_weight() 

174  174  
175  175 
self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight 
176  176 
self.generate_reverse_link_weight() 
...  ...  
271  271  
272  272 
Q = self._inititalize_component_tree_weight() 
273  273 
while Q: 
274 
print self.Dv_B 

275  274 
pair = Q.pop(0) 
276  275 
if pair['type'] == 'component_vertex_pair': 
277  276 
B_index = pair['value'][0] 
...  ...  
283  282  
284  283 
for cp in all_cutpoints: 
285  284 
if self.get_link_weight(B_index, cp) != 1: 
286 
size += self.num_vertices  self.get_link_weight(B_index, cp) 

285 
size += self.num_vertices  self.get_link_weight(B_index, cp)  1


287  286  
288  287 
self.set_link_weight(B_index, v, size) 
289  288  
...  ...  
291  290 
Q = self._find_unknown_weight_wrt_cutpoint(v, Q) 
292  291  
293  292 
if pair['type'] == 'vertex_component_pair': 
294 
size = 1


293 
size = 0


295  294 
B_index = pair['value'][0] 
296  295 
v = pair['value'][1] 
297  296 
print' vc: %s %s' % (B_index, v) 
...  ...  
308  307 
# update Q 
309  308 
Q = self._find_unknown_weight_wrt_component(B_index, Q) 
310  309  
310 
print self.Dv_B 

311  
311  312 
def _inititalize_component_tree_weight(self): 
312  313 
Q = [] 
313  314 
for i, comp in enumerate(self.bicomponents): 
...  ...  
322  323 
return Q 
323  324  
324  325 
def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q): 
326 
# Cutpoint v such that the weights of all but one of its links in T are already computed. 

327 
num_of_uncomputed_weight = 0 

328 
uncomputed_component_index = [] 

329  
325  330 
for i, Dv_B_comp in enumerate(self.Dv_B): 
331 
if cutpoint in Dv_B_comp: 

332 
if Dv_B_comp[cutpoint] == 1: 

333 
num_of_uncomputed_weight += 1 

334 
uncomputed_component_index.append(i) 

335 
if num_of_uncomputed_weight == 1: 

336 
pair = { 

337 
'type': 'vertex_component_pair', 

338 
'value': (uncomputed_component_index.pop(), cutpoint) 

339 
} 

340 
Q.append(pair) 

341 
print "Append WRT Cutpoint %s" % pair 

342 
return Q 

343  
344 
def _find_unknown_weight_wrt_component(self, comp_index, Q): 

345 
# Component B such that weights of all but one of its links in T are already computed. 

346 
Dv_B_comp = self.Dv_B[comp_index] 

347 
values = Dv_B_comp.values() 

348  
349 
# Check if 1 value appear only 1 time 

350 
flag = False 

351 
minus_one_value = [x for x in values if x == 1] 

352 
if len(minus_one_value) == 1: 

326  353 
for cp, value in Dv_B_comp.iteritems(): 
327  354 
if value == 1: 
328  355 
pair = { 
329 
'type': 'vertex_component_pair',


330 
'value': (i, cp)


356 
'type': 'component_vertex_pair',


357 
'value': (comp_index, cp)


331  358 
} 
332  359 
Q.append(pair) 
360 
print "Append WRT Component %s" % pair 

333  361 
return Q 
334  362  
335 
def _find_unknown_weight_wrt_component(self, comp_index, Q): 

336 
Dv_B_comp = self.Dv_B[comp_index] 

337 
for cp, value in Dv_B_comp.iteritems(): 

338 
if value == 1: 

339 
pair = { 

340 
'type': 'component_vertex_pair', 

341 
'value': (comp_index, cp) 

342 
} 

343 
Q.append(pair) 

344 
return Q 

345  
346  
347  363 
def __str__(self): 
348  364 
return str(self.Dv_B) 
349  365  
...  ...  
371  387 
print 'link weight: ' 
372  388 
print(lw) 
373  389  
374 
# tm = TrafficMatrix(bicomponents, cutpoints, lw)


375 
# print 'traffic matrix:'


376 
# pp.pprint(tm.h)


390 
tm = TrafficMatrix(bicomponents, cutpoints, lw) 

391 
print 'traffic matrix:' 

392 
pp.pprint(tm.h) 

377  393  
378 
# bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)


379 
# bc.write(file_suffix)


380 
# # print bc


394 
bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm) 

395 
bc.write(file_suffix) 

396 
# print bc 

381  397  
382  398 
if __name__ == '__main__': 
383  399 
# filepath = MAIN_CODE_DIR + '/input/simple_house.edges' 
384  400 
# filepath = MAIN_CODE_DIR + '/input/simple2.edges' 
385  401 
# filepath = MAIN_CODE_DIR + '/input/simple.edges' 
386 
# filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'


402 
filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges' 

387  403 
# filepath = MAIN_CODE_DIR + '/input/simple3.edges' 
388 
filepath = MAIN_CODE_DIR + '/input/simple4.edges' 

404 
# filepath = MAIN_CODE_DIR + '/input/simple4.edges'


389  405 
file_suffix = 'edge_list' 
390  406  
391  407 
# Weight betweenness centrality 
Also available in: Unified diff