## Revision 3673c3e8 fiddle/heuristic-betweenness-centrality/centrality_biconnected.py

View differences:

fiddle/heuristic-betweenness-centrality/centrality_biconnected.py
12 12

13 13
```MAIN_CODE_DIR = os.environ.get('MAIN_CODE_DIR', '')
```
14 14

15

16 15
```class HeuristicBetweennessCentrality():
```
17 16
```    def __init__(self, subgraphs, bicomponents, cutpoints, num_vertices, link_weight, traffic_matrix):
```
18 17
```        self.subgraphs = subgraphs
```
......
200 199
```        else:
```
201 200
```            return 0
```
202 201

203
```    def generate_link_weight(self):
```
204
```        # How many cutpoints does this component have
```
205
```        B_plus_v = list()
```
206
```        B_cutpoints = list() # number of cutpoints in component B
```
207
```        for comp in self.bicomponents:
```
208
```            points = comp.intersection(self.cutpoints)
```
209
```            B_plus_v.append(comp.difference(points))
```
210
```            B_cutpoints.append(points)
```
211

212
```        len_B_plus_v = [len(x) for x in B_plus_v]
```
213
```        len_B_cutpoints = [len(x) for x in B_cutpoints]
```
214

215
```        # Calculate the Dv_B
```
216

217
```        # For the leaf in the block-cut tree
```
218
```        level = 1
```
219
```        for (i, cp) in enumerate(B_cutpoints):
```
220
```            if len_B_cutpoints[i] == level:
```
221
```                point = list(cp)[0] # there is only 1 element
```
222
```                self.Dv_B[i][point] = len_B_plus_v[i]
```
223

224
```        # For other nodes in the block-cut tree
```
225
```        level += 1
```
226
```        while level <= max(len_B_cutpoints):
```
227
```            if level == 3:
```
228
```                debugger()
```
229
```            for (i, cp) in enumerate(B_cutpoints):
```
230
```                if len_B_cutpoints[i] == level:
```
231

232
```                    for point in cp:
```
233
```                        # 1st way
```
234
```                        shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, point)
```
235
```                        shared_comp_indices.remove(i)
```
236
```                        weight_shared_comp = list()
```
237

238
```                        for index in shared_comp_indices:
```
239
```                            weight_shared_comp.append(self.get_link_weight(index, point))
```
240

241
```                        weight = self.num_vertices - 1 - sum(weight_shared_comp)
```
242

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

245
```            level += 1
```
246

247 202
```    def generate_reverse_link_weight(self):
```
248 203
```        for i, Dv_B_i in enumerate(self.Dv_B):
```
249 204
```            for key, value in Dv_B_i.iteritems():
```
......
258 213
```            B_cutpoints.append(points)
```
259 214

260 215
```        Q = self._inititalize_component_tree_weight()
```
216
```        print "finish initialization\n"
```
261 217
```        while Q:
```
262 218
```            pair = Q.pop(0)
```
263 219
```            if pair['type'] == 'component_vertex_pair':
```
......
319 275
```                    'type': 'component_vertex_pair',
```
320 276
```                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
```
321 277
```                    })
```
278
```                print "added component_vertex_pair(%s, %s)" % (i, list(current_cutpoints)[0])
```
322 279
```            for cp in current_cutpoints:
```
323 280
```                self.set_link_weight(i, cp, -1)
```
324 281
```        return Q
```
325 282

326 283
```    def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q):
```
284
```        print "_find_unknown_weight_wrt_cutpoint %s" % cutpoint
```
285

327 286
```        # Cut-point v such that the weights of all but one of its links in T are already computed.
```
328 287
```        num_of_uncomputed_weight = 0
```
329 288
```        uncomputed_component_index = []
```
......
332 291
```            if cutpoint in Dv_B_comp:
```
333 292
```                if Dv_B_comp[cutpoint] == -1:
```
334 293
```                    num_of_uncomputed_weight += 1
```
294
```                    print "    %i" % i
```
335 295
```                    uncomputed_component_index.append(i)
```
296
```                if num_of_uncomputed_weight > 1:
```
297
```                    break
```
298

336 299
```        if num_of_uncomputed_weight == 1:
```
337 300
```            pair = {
```
338 301
```                'type': 'vertex_component_pair',
```
339 302
```                'value': (uncomputed_component_index.pop(), cutpoint)
```
340 303
```            }
```
304
```            print "      Added vertex_component_pair (%s, %s)" % pair['value'];
```
341 305
```            Q.append(pair)
```
342 306
```        return Q
```
343 307

......
356 320
```                        'type': 'component_vertex_pair',
```
357 321
```                        'value': (comp_index, cp)
```
358 322
```                    }
```
323
```                    print "Added component_vertex_pair (%s, %s)" % pair['value'];
```
359 324
```                    Q.append(pair)
```
360 325
```        return Q
```
361 326

362 327
```    def __str__(self):
```
363 328
```        return str(self.Dv_B)
```
364 329

365
```def analyse_biconnected_component(graph):
```
366
```    bicomponents = list(nx.biconnected_components(graph))
```
367
```    print bicomponents
```
368
```    print [len(x) for x in bicomponents]
```
369

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

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

375
```    graph = nx.read_weighted_edgelist(filepath)
```
376

377
```    if not nx.is_connected(graph):
```
378
```        print "Graph is not connected"
```
379
```        # sys.exit()
```
380
```    else:
```
381
```        print "Graph is connected"
```
382

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

386
```    subgraphs = list(nx.biconnected_component_subgraphs(graph))
```
387
```    bicomponents = list(nx.biconnected_components(graph))
```
388
```    component_edges = list(nx.biconnected_component_edges(graph))
```
389
```    cutpoints = set(nx.articulation_points(graph))
```
390

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

393
```    lw = LinkWeight(graph, bicomponents, cutpoints)
```
394

395
```    tm = TrafficMatrix(bicomponents, cutpoints, lw)
```
396

397
```    bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
```
398
```    bc.write(file_suffix)
```
399
```    print bc
```
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

407
```if __name__ == '__main__':
```
408
```    utility.initialize()
```
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)
```
412

413
```    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
```
414
```    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
```
415
```    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
```
416
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified.edges'
```
417
```    # filepath = MAIN_CODE_DIR + '/input/ninux_simplified_connected.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'
```
424
```    # filepath = MAIN_CODE_DIR + '/input/ninux_connected.edges'
```
425
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted.edges'
```
426
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified.edges'
```
427
```    # filepath = MAIN_CODE_DIR + '/input/ninux_unweighted_simplified_connected.edges'
```
428
```    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
```
429
```    # filepath = MAIN_CODE_DIR + '/input/simple4.edges'
```
430
```    # filepath = MAIN_CODE_DIR + '/input/simple5.edges'
```
431

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

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)
```
440

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

Also available in: Unified diff