Revision 3c6ce57c 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 pprint
5 6
import networkx as nx
6 7
import betweenness_centrality as centrality
7 8
import utility
......
27 28
        self.finalize()
28 29

  
29 30
    def calculate_bc_non_cutpoint(self):
30
        """BCen for non cutpoint
31
        """BC for non cutpoint
31 32
        """
32 33
        for i, subgraphs in enumerate(self.subgraphs):
33 34
            traffic_matrix = self.traffic_matrix[i]
34
            results = centrality.betweenness_centrality(subgraphs, traffic_matrix, endpoints=True)
35
            results = centrality.weight_betweenness_centrality(subgraphs, traffic_matrix)
35 36
            self.bc_components.append(results)
36 37

  
37 38
            # print results
......
58 59
                    # debugger()
59 60
                    bc_locally += self.bc_components[i][v]
60 61
            print 'locally = %s' % bc_locally
61
            self.bc_cutpoints[v] = bc_locally - bc_inter[v]
62
            # self.bc_cutpoints[v] = bc_locally - bc_inter[v]
63
            # TODO: do not minus the bc_inter
64
            self.bc_cutpoints[v] = bc_locally
62 65

  
63 66
    def finalize(self):
64 67
        # Add the bc for non cutpoint vertices
......
71 74
        for key, value in self.bc_cutpoints.iteritems():
72 75
            self.bc[key] = value
73 76

  
77
        print '*** betweenness = %s' % self.bc
74 78
        # Rescale the bc according to the original graph
75
        factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
79
        factor = 1.0 / ((self.num_vertices - 1) * (self.num_vertices - 2))
80
        # factor = 2.0 / (self.num_vertices*self.num_vertices - 3 * self.num_vertices + 2)
76 81
        for key, value in self.bc.iteritems():
77 82
            self.bc[key] = value * factor
78 83

  
......
84 89

  
85 90
    def __str__(self):
86 91
        return str(self.bc)
87
        # for bc_component in self.bc_components:
88
        #     print bc_component
89 92

  
90 93

  
91 94
class TrafficMatrix():
......
167 170

  
168 171
        self.Dv_B = [dict() for i in range(self.num_components)] # link weight
169 172
        self.generate_link_weight()
173
        # self.compute_component_tree_weight()
170 174

  
171 175
        self.reverse_Dv_B = [dict() for i in range(self.num_components)] # reverse link weight
172 176
        self.generate_reverse_link_weight()
......
181 185
        return indices
182 186

  
183 187
    def get_link_weight(self, comp_index, point):
184
        print "Dv_B = %s" % str(self.Dv_B)
185

  
186 188
        Dv_B_comp = self.Dv_B[comp_index]
187 189

  
188 190
        if point in Dv_B_comp:
......
190 192
        else:
191 193
            return 0
192 194

  
195
    def set_link_weight(self, comp_index, point, value):
196
        self.Dv_B[comp_index][point] = value
197

  
193 198
    def get_reverse_link_weight(self, comp_index, point):
194 199
        reverse_Dv_B_comp = self.reverse_Dv_B[comp_index]
195 200

  
......
207 212
            B_plus_v.append(comp.difference(points))
208 213
            B_cutpoints.append(points)
209 214

  
210
        print 'B_cutpoints %s' % str(B_cutpoints)
211 215
        len_B_plus_v = [len(x) for x in B_plus_v]
212 216
        len_B_cutpoints = [len(x) for x in B_cutpoints]
213 217

  
......
220 224
                point = list(cp)[0] # there is only 1 element
221 225
                self.Dv_B[i][point] = len_B_plus_v[i]
222 226

  
223
        print 'B_cutpoints %s' % str(B_cutpoints)
227
        print "Link Weight - For all the leaves: %s" % self.Dv_B
224 228

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

  
231 237
                    for point in cp:
232
                        print 'cutpoints = %s' % cp
238
                        # 1st way
233 239
                        shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, point)
234 240
                        shared_comp_indices.remove(i)
235
                        print 'shared indices %s' % shared_comp_indices
236 241
                        weight_shared_comp = list()
237 242

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

  
241
                        print 'weight shared comp %s' % str(weight_shared_comp)
242
                        weight = num_vertices - 1 - sum(weight_shared_comp)
246
                        weight = self.num_vertices - 1 - sum(weight_shared_comp)
243 247

  
244 248
                        self.Dv_B[i][point] = weight
245 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
            print "Link Weight - For level %s: %s" % (level, self.Dv_B)
256

  
246 257
            level += 1
247 258

  
248 259
    def generate_reverse_link_weight(self):
......
250 261
            for key, value in Dv_B_i.iteritems():
251 262
                self.reverse_Dv_B[i][key] = self.num_vertices - 1 - self.get_link_weight(i, key)
252 263

  
253
        print 'reverse = %s' % self.reverse_Dv_B
264
    def compute_component_tree_weight(self):
265
        """Follows exactly the Algorithm 1 [Puzis 2012]
266
        """
267
        B_cutpoints = list() # number of cutpoints in component B
268
        for comp in self.bicomponents:
269
            points = comp.intersection(self.cutpoints)
270
            B_cutpoints.append(points)
271

  
272
        Q = self._inititalize_component_tree_weight()
273
        while Q:
274
            print self.Dv_B
275
            pair = Q.pop(0)
276
            if pair['type'] == 'component_vertex_pair':
277
                B_index = pair['value'][0]
278
                v = pair['value'][1]
279
                print'  CV: %s %s' % (B_index, v)
280
                size = len(self.bicomponents[B_index]) - 1;
281
                all_cutpoints = self.bicomponents[B_index].intersection(self.cutpoints)
282
                all_cutpoints.remove(v)
283

  
284
                for cp in all_cutpoints:
285
                    if self.get_link_weight(B_index, cp) != -1:
286
                        size += self.num_vertices - self.get_link_weight(B_index, cp)
287

  
288
                self.set_link_weight(B_index, v, size)
289

  
290
                # update Q
291
                Q = self._find_unknown_weight_wrt_cutpoint(v, Q)
292

  
293
            if pair['type'] == 'vertex_component_pair':
294
                size = 1
295
                B_index = pair['value'][0]
296
                v = pair['value'][1]
297
                print'  vc: %s %s' % (B_index, v)
298
                shared_comp_indices = self._components_sharing_cutpoint(B_cutpoints, v)
299
                shared_comp_indices.remove(B_index)
300

  
301

  
302
                for i in shared_comp_indices:
303
                    if self.get_link_weight(i, v) != - 1:
304
                        size += self.get_link_weight(i, v)
305

  
306
                self.set_link_weight(B_index, v, self.num_vertices - 1 - size)
307

  
308
                # update Q
309
                Q = self._find_unknown_weight_wrt_component(B_index, Q)
310

  
311
    def _inititalize_component_tree_weight(self):
312
        Q = []
313
        for i, comp in enumerate(self.bicomponents):
314
            current_cutpoints = self.cutpoints.intersection(comp)
315
            if len(current_cutpoints) == 1:
316
                Q.append({
317
                    'type': 'component_vertex_pair',
318
                    'value': (i, list(current_cutpoints)[0]) # (B_i, cutpoint) = (i-th component, the cutpoint name)
319
                    })
320
            for cp in current_cutpoints:
321
                self.set_link_weight(i, cp, -1)
322
        return Q
323

  
324
    def _find_unknown_weight_wrt_cutpoint(self, cutpoint, Q):
325
        for i, Dv_B_comp in enumerate(self.Dv_B):
326
            for cp, value in Dv_B_comp.iteritems():
327
                if value == -1:
328
                    pair = {
329
                        'type': 'vertex_component_pair',
330
                        'value': (i, cp)
331
                    }
332
                    Q.append(pair)
333
        return Q
334

  
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

  
254 346

  
255 347
    def __str__(self):
256 348
        return str(self.Dv_B)
......
260 352
    print bicomponents
261 353
    print [len(x) for x in bicomponents]
262 354

  
263
if __name__ == '__main__':
264
    filepath = MAIN_CODE_DIR + '/input/simple.edges'
265
    file_suffix = 'edge_list'
355
def find_heuristic_bc(filepath):
356
    pp = pprint.PrettyPrinter(indent=4)
266 357

  
267
    # Brandes betweenness centrality
268
    utility.brandes_betweenness_centrality(filepath, file_suffix)
269

  
270
    # Heuristic betweenness centrality
271 358
    graph = nx.read_weighted_edgelist(filepath)
272 359

  
273 360
    # Find biconnected components
......
276 363
    subgraphs = list(nx.biconnected_component_subgraphs(graph))
277 364
    bicomponents = list(nx.biconnected_components(graph))
278 365
    component_edges = list(nx.biconnected_component_edges(graph))
279
    # cutpoints = list(nx.articulation_points(graph))
280 366
    cutpoints = set(nx.articulation_points(graph))
281 367

  
282 368
    num_vertices = nx.number_of_nodes(graph)
283 369

  
284 370
    lw = LinkWeight(graph, bicomponents, cutpoints)
285 371
    print 'link weight: '
286
    print lw
372
    print(lw)
373

  
374
    # tm = TrafficMatrix(bicomponents, cutpoints, lw)
375
    # print 'traffic matrix:'
376
    # pp.pprint(tm.h)
287 377

  
288
    tm = TrafficMatrix(bicomponents, cutpoints, lw)
289
    print tm
378
    # bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
379
    # bc.write(file_suffix)
380
    # # print bc
290 381

  
382
if __name__ == '__main__':
383
    # filepath = MAIN_CODE_DIR + '/input/simple_house.edges'
384
    # filepath = MAIN_CODE_DIR + '/input/simple2.edges'
385
    # filepath = MAIN_CODE_DIR + '/input/simple.edges'
386
    # filepath = MAIN_CODE_DIR + '/input/ninux_30_1.edges'
387
    # filepath = MAIN_CODE_DIR + '/input/simple3.edges'
388
    filepath = MAIN_CODE_DIR + '/input/simple4.edges'
389
    file_suffix = 'edge_list'
390

  
391
    # Weight betweenness centrality
392
    utility.weight_betweenness_centrality(filepath, file_suffix)
393

  
394
    # Brandess betweenness centrality
395
    utility.brandes_betweenness_centrality(filepath, file_suffix)
291 396

  
292
    bc = HeuristicBetweennessCentrality(subgraphs, bicomponents, cutpoints, num_vertices, lw, tm)
293
    bc.write(file_suffix)
294
    print bc
397
    # Heuristic BC
398
    find_heuristic_bc(filepath)

Also available in: Unified diff