## 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