## Revision 82c7c698 fiddle/heuristic-betweenness-centrality/centrality_biconnected.py

View differences:

fiddle/heuristic-betweenness-centrality/centrality_biconnected.py
1 1
```# Implement the section IV in Puzis 2012 paper
```
2
```# straight_lineent the section IV in Puzis 2012 paper
```
2 3
```# Heuristic Betweenness Centrality - Partitioning to Bi-connected Components
```
3 4

4 5
```import os
```
......
36 37
```            results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix)
```
37 38
```            self.bc_components.append(results)
```
38 39

39
```            # print results
```
40

41 40
```    def calculate_bc_cutpoint(self):
```
42 41
```        self.bc_cutpoints = dict()
```
43 42

......
57 56
```            bc_locally = 0
```
58 57
```            for i, comp in enumerate(self.bicomponents):
```
59 58
```                if v in comp:
```
60
```                    # debugger()
```
61 59
```                    bc_locally += self.bc_components[i][v]
```
62
```            print 'locally = %s' % bc_locally
```
63 60
```            # self.bc_cutpoints[v] = bc_locally - bc_inter[v]
```
64 61
```            # TODO: do not minus the bc_inter
```
65 62
```            self.bc_cutpoints[v] = bc_locally
```
......
78 75
```        print '*** betweenness = %s' % self.bc
```
79 76
```        # Rescale the bc according to the original graph
```
80 77
```        factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2))
```
78
```        # TODO: check the scaling factor, how much should it be?
```
81 79
```        # factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
```
82 80
```        for key, value in self.bc.iteritems():
```
83 81
```            self.bc[key] = value * factor
```
......
145 143
```        self.h[comp_index][y_pos][x_pos] = value
```
146 144

147 145
```    def update(self, comp_index, x, y, value):
```
148
```        comp = self.bicomponents[comp_index]
```
146
```        comp = sorted(self.bicomponents[comp_index])
```
149 147
```        try:
```
150 148
```            x_pos = list(comp).index(x)
```
151 149
```            y_pos = list(comp).index(y)
```
......
178 176
```    def _components_sharing_cutpoint(self, B_cutpoints, point):
```
179 177
```        indices = list()
```
180 178
```        for i, cp in enumerate(B_cutpoints):
```
181
```            # debugger()
```
182 179
```            if point in cp:
```
183 180
```                indices.append(i)
```
184 181

......
224 221
```                point = list(cp)[0] # there is only 1 element
```
225 222
```                self.Dv_B[i][point] = len_B_plus_v[i]
```
226 223

227
```        print "Link Weight - For all the leaves: %s" % self.Dv_B
```
228

229 224
```        # For other nodes in the block-cut tree
```
230 225
```        level += 1
```
231 226
```        while level <= max(len_B_cutpoints):
```
......
247 242

248 243
```                        self.Dv_B[i][point] = weight
```
249 244

250
```            print "Link Weight - For level %s: %s" % (level, self.Dv_B)
```
251

252 245
```            level += 1
```
253 246

254 247
```    def generate_reverse_link_weight(self):
```
......
277 270
```                for cp in all_cutpoints:
```
278 271
```                    if self.get_link_weight(B_index, cp) != -1:
```
279 272
```                        size += self.num_vertices - self.get_link_weight(B_index, cp) - 1
```
280
```                        # size += self.num_vertices - self.get_link_weight(B_index, cp)
```
281 273

282 274
```                link_weight = size
```
283 275
```                self._verify_link_weight(B_index, v, link_weight)
```
......
288 280

289 281
```            if pair['type'] == 'vertex_component_pair':
```
290 282
```                size = 0
```
291
```                # size = 1
```
292 283
```                B_index = pair['value'][0]
```
293 284
```                v = pair['value'][1]
```
294 285
```                shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
```
......
311 302

312 303
```        Otherwise, do nothing
```
313 304
```        """
```
314
```        print "VERIFICATION FOR (%s, %s)" % (B_index, v)
```
315 305
```        old_value = self.get_link_weight(B_index, v)
```
316
```        # -1 is unknown
```
317
```        if old_value != -1:
```
306

307
```        if old_value != -1: # -1 is unknown
```
318 308
```            if old_value != value:
```
319 309
```                print "BUGS FOUND in _verify_link_weight()"
```
320 310
```                sys.exit()
```
......
378 368
```    print [len(x) for x in bicomponents]
```
379 369

380 370
```def find_heuristic_bc(filepath):
```
381
```    filename = os.splitext(os.path.basename(filepath))[0]
```
371
```    filename = os.path.splitext(os.path.basename(filepath))[0]
```
382 372

383 373
```    pp = pprint.PrettyPrinter(indent=4)
```
384 374

......
390 380
```    else:
```
391 381
```        print "Graph is connected"
```
392 382

393

394 383
```    # Find biconnected components
```
395 384
```    analyse_biconnected_component(graph)
```
396 385

......
402 391
```    num_vertices = nx.number_of_nodes(graph)
```
403 392

404 393
```    lw = LinkWeight(graph, bicomponents, cutpoints)
```
405
```    print 'link weight: '
```
406
```    print(lw)
```
407 394

408 395
```    tm = TrafficMatrix(bicomponents, cutpoints, lw)
```
409
```    print 'traffic matrix:'
```
410
```    pp.pprint(tm.h)
```
411 396

412 397
```    bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
```
413 398
```    bc.write(file_suffix)
```
414 399
```    print bc
```
415 400

401
```def test_isomorphic_graphs(filepath1, filepath2):
```
402
```    graph1 = nx.read_weighted_edgelist(filepath1)
```
403
```    graph2 = nx.read_weighted_edgelist(filepath2)
```
404
```    print "Isomorphic = %s" % nx.is_isomorphic(graph1, graph2)
```
405

406

416 407
```if __name__ == '__main__':
```
417 408
```    utility.initialize()
```
418
```    input_dir = os.path.join(MAIN_CODE_DIR, 'input')
```
409
```    f1 = MAIN_CODE_DIR + '/input/9_vertices_green.edges'
```
410
```    f2 = MAIN_CODE_DIR + '/input/9_vertices_blue.edges'
```
411
```    test_isomorphic_graphs(f1, f2)
```
419 412

420 413
```    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
```
421 414
```    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
```
422 415
```    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
```
423 416
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified.edges'
```
424 417
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected.edges'
```
425
```    filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'
```
418
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected2.edges'
```
419
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected3.edges'
```
420
```    # filepath = MAIN_CODE_DIR + '/input/9_vertices_green.edges'
```
421
```    # filepath = MAIN_CODE_DIR + '/input/9_vertices_blue.edges'
```
422
```    # filepath = MAIN_CODE_DIR + '/input/simple_loop.edges'
```
423
```    # filepath = MAIN_CODE_DIR + '/input/straight_line.edges'
```
426 424
```    # filepath = MAIN_CODE_DIR + '/input/ninux_connected.edges'
```
427 425
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted.edges'
```
428 426
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified.edges'
```
......
430 428
```    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
```
431 429
```    # filepath = MAIN_CODE_DIR + '/input/simple4.edges'
```
432 430
```    # filepath = MAIN_CODE_DIR + '/input/simple5.edges'
```
431

432
```    filepath = MAIN_CODE_DIR + '/input/ninux.edges'
```
433 433
```    file_suffix = 'edge_list'
```
434 434

435
```    # # Weight betweenness centrality
```
436
```    # utility.weight_betweenness_centrality(filepath, file_suffix)
```
435
```    # Weight betweenness centrality
```
436
```    utility.weight_betweenness_centrality(filepath, file_suffix)
```
437 437

438
```    # # Brandess betweenness centrality
```
439
```    # utility.brandes_betweenness_centrality(filepath, file_suffix)
```
438
```    # Brandess betweenness centrality
```
439
```    utility.brandes_betweenness_centrality(filepath, file_suffix)
```
440 440

441
```    # # Heuristic BC
```
442
```    # find_heuristic_bc(filepath)
```
441
```    # Heuristic BC
```
442
```    find_heuristic_bc(filepath)
```
443 443

Also available in: Unified diff