Revision 739fe075 fiddle/heuristicbetweennesscentrality/centrality_biconnected.py
fiddle/heuristicbetweennesscentrality/centrality_biconnected.py  

2  2 
# Heuristic Betweenness Centrality  Partitioning to Biconnected Components 
3  3  
4  4 
import os 
5 
import sys 

5  6 
import pprint 
6  7 
import networkx as nx 
7  8 
import betweenness_centrality as centrality 
...  ...  
169  170 
self.cutpoints = cutpoints 
170  171  
171  172 
self.Dv_B = [dict() for i in range(self.num_components)] # link weight 
172 
# self.generate_link_weight() 

173  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 
...  ...  
247  247  
248  248 
self.Dv_B[i][point] = weight 
249  249  
250 
# # 2nd way 

251 
# sum_of_connected_vertices = 0 

252 
# for point_temp in cp: 

253 
# if point_temp != point: 

254 
# sum_of_connected_vertices += self.num_vertices  

255  250 
print "Link Weight  For level %s: %s" % (level, self.Dv_B) 
256  251  
257  252 
level += 1 
...  ...  
275  270 
if pair['type'] == 'component_vertex_pair': 
276  271 
B_index = pair['value'][0] 
277  272 
v = pair['value'][1] 
278 
print' CV: %s %s' % (B_index, v) 

279  273 
size = len(self.bicomponents[B_index])  1; 
280  274 
all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints) 
281  275 
all_cutpoints.remove(v) 
...  ...  
283  277 
for cp in all_cutpoints: 
284  278 
if self.get_link_weight(B_index, cp) != 1: 
285  279 
size += self.num_vertices  self.get_link_weight(B_index, cp)  1 
280 
# size += self.num_vertices  self.get_link_weight(B_index, cp) 

286  281  
287 
self.set_link_weight(B_index, v, size) 

282 
link_weight = size 

283 
self._verify_link_weight(B_index, v, link_weight) 

284 
self.set_link_weight(B_index, v, link_weight) 

288  285  
289  286 
# update Q 
290  287 
Q = self._find_unknown_weight_wrt_cutpoint(v, Q) 
291  288  
292  289 
if pair['type'] == 'vertex_component_pair': 
293  290 
size = 0 
291 
# size = 1 

294  292 
B_index = pair['value'][0] 
295  293 
v = pair['value'][1] 
296 
print' vc: %s %s' % (B_index, v) 

297  294 
shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v) 
298  295 
shared_comp_indices.remove(B_index) 
299  296  
...  ...  
302  299 
if self.get_link_weight(i, v) !=  1: 
303  300 
size += self.get_link_weight(i, v) 
304  301  
305 
self.set_link_weight(B_index, v, self.num_vertices  1  size) 

302 
link_weight = self.num_vertices  1  size 

303 
self._verify_link_weight(B_index, v, link_weight) 

304 
self.set_link_weight(B_index, v, link_weight) 

306  305  
307  306 
# update Q 
308  307 
Q = self._find_unknown_weight_wrt_component(B_index, Q) 
309  308  
310 
print self.Dv_B 

309 
def _verify_link_weight(self, B_index, v, value): 

310 
""" If the old_value exist in self.Dv_B, then it must be equal to new value 

311  
312 
Otherwise, do nothing 

313 
""" 

314 
print "VERIFICATION FOR (%s, %s)" % (B_index, v) 

315 
old_value = self.get_link_weight(B_index, v) 

316 
# 1 is unknown 

317 
if old_value != 1: 

318 
if old_value != value: 

319 
print "BUGS FOUND in _verify_link_weight()" 

320 
sys.exit() 

321  
311  322  
312  323 
def _inititalize_component_tree_weight(self): 
313  324 
Q = [] 
...  ...  
338  349 
'value': (uncomputed_component_index.pop(), cutpoint) 
339  350 
} 
340  351 
Q.append(pair) 
341 
print "Append WRT Cutpoint %s" % pair 

342  352 
return Q 
343  353  
344  354 
def _find_unknown_weight_wrt_component(self, comp_index, Q): 
...  ...  
357  367 
'value': (comp_index, cp) 
358  368 
} 
359  369 
Q.append(pair) 
360 
print "Append WRT Component %s" % pair 

361  370 
return Q 
362  371  
363  372 
def __str__(self): 
...  ...  
369  378 
print [len(x) for x in bicomponents] 
370  379  
371  380 
def find_heuristic_bc(filepath): 
381 
filename = os.splitext(os.path.basename(filepath))[0] 

382  
372  383 
pp = pprint.PrettyPrinter(indent=4) 
373  384  
374  385 
graph = nx.read_weighted_edgelist(filepath) 
375  386  
387 
if not nx.is_connected(graph): 

388 
print "Graph is not connected" 

389 
# sys.exit() 

390 
else: 

391 
print "Graph is connected" 

392  
393  
376  394 
# Find biconnected components 
377  395 
analyse_biconnected_component(graph) 
378  396  
...  ...  
393  411  
394  412 
bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm) 
395  413 
bc.write(file_suffix) 
396 
# print bc


414 
print bc 

397  415  
398  416 
if __name__ == '__main__': 
417 
utility.initialize() 

418 
input_dir = os.path.join(MAIN_CODE_DIR, 'input') 

419  
399  420 
# filepath = MAIN_CODE_DIR + '/input/simple_house.edges' 
400  421 
# filepath = MAIN_CODE_DIR + '/input/simple2.edges' 
401  422 
# filepath = MAIN_CODE_DIR + '/input/simple.edges' 
423 
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified.edges' 

424 
# filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected.edges' 

402  425 
filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges' 
426 
# filepath = MAIN_CODE_DIR + '/input/ninux_connected.edges' 

427 
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted.edges' 

428 
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified.edges' 

429 
# filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified_connected.edges' 

403  430 
# filepath = MAIN_CODE_DIR + '/input/simple3.edges' 
404  431 
# filepath = MAIN_CODE_DIR + '/input/simple4.edges' 
432 
# filepath = MAIN_CODE_DIR + '/input/simple5.edges' 

405  433 
file_suffix = 'edge_list' 
406  434  
407 
# Weight betweenness centrality 

408 
utility.weight_betweenness_centrality(filepath, file_suffix) 

435 
# # Weight betweenness centrality 

436 
# utility.weight_betweenness_centrality(filepath, file_suffix) 

437  
438 
# # Brandess betweenness centrality 

439 
# utility.brandes_betweenness_centrality(filepath, file_suffix) 

409  440  
410 
# Brandess betweenness centrality


411 
utility.brandes_betweenness_centrality(filepath, file_suffix)


441 
# # Heuristic BC


442 
# find_heuristic_bc(filepath)


412  443  
413 
# Heuristic BC 

414 
find_heuristic_bc(filepath) 
Also available in: Unified diff