Revision 739fe075 fiddle/heuristic-betweenness-centrality/centrality_biconnected.py

View differences:

fiddle/heuristic-betweenness-centrality/centrality_biconnected.py
2 2
# Heuristic Betweenness Centrality - Partitioning to Bi-connected 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