Revision 24a4abf9 fiddle/heuristic-betweenness-centrality/centrality_biconnected.py
fiddle/heuristic-betweenness-centrality/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 |
# Cut-point 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