Revision 24a4abf9 fiddle/heuristic-betweenness-centrality/centrality_biconnected.py

View differences:

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