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