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