Statistics
| Branch: | Revision:

nepatest_popbabel / mylib / compute_theoretical_values.py @ 60ba786f

History | View | Annotate | Download (6.97 KB)

1 60ba786f LoreBz
#!/usr/bin/env python
2
import sys
3
sys.path.append('../')
4
import networkx as nx
5
from collections import defaultdict
6
import matplotlib.pyplot as plt
7
import glob
8
import numpy as np
9
10
import math
11
12
13
class ComputeTheoreticalValues():
14
15
    def __init__(self, graph_file=None, graph=None, cent="C", cH=2.0, cTC=5.0):
16
17
        if graph_file:
18
            try:
19
                self.G = nx.read_weighted_edgelist(graph_file, nodetype=int)
20
            except TypeError:
21
                self.G = nx.read_graphml(graph_file)
22
            except:
23
                print "Can not read files, tried with edge_list and graphml"
24
                raise
25
        elif graph:
26
            self.G = graph
27
        self.cent = cent
28
        self.cH = cH
29
        self.cTC = cTC
30
        self.decimal_values = 3
31
        if cent == "B":
32
            self.bet_dict = nx.betweenness_centrality(self.G, endpoints=True)
33
            self.bet_ordered_nodes = [i[0] for i in sorted(
34
                self.bet_dict.items(), key=lambda x: x[1])]
35
        elif cent == "C":
36
            self.bet_dict = nx.betweenness_centrality(self.G, endpoints=True)
37
            self.bet_ordered_nodes = [i[0] for i in sorted(
38
                self.bet_dict.items(), key=lambda x: x[1])]
39
        elif cent == "L":
40
            self.bet_dict = nx.load_centrality(self.G)
41
            self.bet_ordered_nodes = [i[0] for i in sorted(
42
                self.bet_dict.items(), key=lambda x: x[1])]
43
44
            self.cent_dict = nx.closeness_centrality(self.G)
45
            self.cent_ordered_nodes = [i[0] for i in sorted(
46
                self.cent_dict.items(), key=lambda x: x[1])]
47
        self.deg_dict = self.G.degree()
48
        self.node_list = filter(lambda x: self.deg_dict[x] > 0, self.G)
49
        self.R = len(self.G.edges())
50
        self.compute_constants()
51
        # self.print_constants()
52
        self.compute_timers()
53
        self.check_consistency()
54
55
    def compute_constants(self):
56
        # self.lambda_H, self.lambda_TC, self.O_H, self.O_TC = \
57
        self.O_H = sum([self.deg_dict[l] for l in self.node_list])/self.cH
58
        self.O_TC = len(self.node_list)*self.R/self.cTC
59
        sqrt_sum = 0
60
        for node in self.node_list:
61
            sqrt_sum += math.sqrt(self.deg_dict[node]*self.bet_dict[node])
62
        self.sq_lambda_H = sqrt_sum/self.O_H
63
        sqrt_sum = 0
64
        for node in self.node_list:
65
            sqrt_sum += math.sqrt(self.R*self.bet_dict[node])
66
        self.sq_lambda_TC = sqrt_sum/self.O_TC
67
68
    def print_constants(self):
69
        print "Loaded Graph with:"
70
        print len(self.G.nodes()), " nodes"
71
        print len(self.G.edges()), " edges"
72
        print self.O_H, self.O_TC, self.sq_lambda_H, self.sq_lambda_TC
73
74
    def print_timers(self):
75
        print "H:", [h[1] for h in sorted(self.Hi.items(), key=lambda x:x[1])]
76
        print "TC:", \
77
            [t[1] for t in sorted(self.TCi.items(), key=lambda x:x[1])]
78
        vv =  sorted([[self.deg_dict[node]/self.Hi[node], self.bet_dict[node], \
79
                            self.deg_dict[node], self.Hi[node], self.TCi[node]] for node in self.node_list], key=lambda x:-x[0])
80
        for v in vv:
81
                print v
82
83
    def get_graph_size(self):
84
        return len(self.G.nodes())
85
86
    def compute_timers(self):
87
        self.Hi = {}
88
        self.TCi = {}
89
        for node in self.node_list:
90
            self.Hi[node] = \
91
                    math.sqrt(self.deg_dict[node]/self.bet_dict[node])*self.sq_lambda_H
92
            self.TCi[node] = \
93
                math.sqrt(self.R/self.bet_dict[node])*self.sq_lambda_TC
94
95
    def compute_average_load(self, pop=True):
96
        O_h = 0
97
        O_tc = 0
98
        if pop:
99
            for node in self.node_list:
100
                O_h += self.deg_dict[node]/self.Hi[node]
101
                O_tc += self.R/self.TCi[node]
102
103
        else:
104
            for node in self.node_list:
105
                O_h += self.deg_dict[node]/self.cH
106
                O_tc += self.R/self.cTC
107
        return round(O_h, self.decimal_values), \
108
            round(O_tc, self.decimal_values)
109
110
    def compute_average_loss(self, pop=True, leaf_nodes=True):
111
        L_h = 0
112
        L_tc = 0
113
        for node in self.node_list:
114
            if not leaf_nodes:
115
                if self.deg_dict[node] == 1:
116
                    continue
117
            if pop:
118
                L_h += self.Hi[node]*self.bet_dict[node]
119
                L_tc += self.TCi[node]*self.bet_dict[node]
120
            else:
121
                L_h += self.cH*self.bet_dict[node]
122
                L_tc += self.cTC*self.bet_dict[node]
123
        return round(L_h, self.decimal_values), \
124
            round(L_tc, self.decimal_values)
125
126
    def check_consistency(self):
127
        """ Check that the generated overhead is the same with
128
        and without pop """
129
        load = self.compute_average_load(pop=True), \
130
            self.compute_average_load(pop=False)
131
        loss = self.compute_average_loss(pop=True), \
132
            self.compute_average_loss(pop=False)
133
134
        print "Load pop/standard", load[0][0]/load[1][0], load[0][1]/load[1][1]
135
        print "Loss pop/standard", 1-loss[0][0]/loss[1][0], \
136
            1-loss[0][1]/loss[1][1]
137
138
139
class average_graphs():
140
    """ FIXME rework this class """
141
    def __init__(self, folder_list):
142
143
        self.folder_list = folder_list
144
        self.data = defaultdict(dict)
145
        self.limit_number = 30
146
147
    def load_file_list(self, folder):
148
        return glob.glob(folder+"/*.edges")[:self.limit_number]
149
150
    def average_folder(self, folder):
151
        loss_red_h = []
152
        loss_red_tc = []
153
        for graph_file in self.load_file_list(folder):
154
            c = ComputeTheoreticalValues(graph_file, cent="B")
155
            pop_l_h, pop_l_tc = c.compute_average_loss()
156
            std_l_h, std_l_tc = c.compute_average_loss(pop=False)
157
            loss_red_h.append(1-pop_l_h/std_l_h)
158
            loss_red_tc.append(1-pop_l_tc/std_l_tc)
159
        avg_loss_r_h = np.average(loss_red_h)
160
        avg_loss_r_tc = np.average(loss_red_tc)
161
        self.data[folder]["size"] = c.get_graph_size()
162
        self.data[folder]["H_r"] = avg_loss_r_h
163
        self.data[folder]["TC_r"] = avg_loss_r_tc
164
165
166
    def compute_average_values(self):
167
        for folder in self.folder_list:
168
            print "parsing folder", folder
169
            self.average_folder(folder)
170
171
    def plot_results(self, out_folder):
172
        x = []
173
        loss_r_h = {}
174
        loss_r_tc = {}
175
        for folder in self.data:
176
            s = self.data[folder]["size"]
177
            x.append(s)
178
            loss_r_h[s] = self.data[folder]['H_r']
179
            loss_r_tc[s] = self.data[folder]['TC_r']
180
        plt.plot(sorted(x), [y[1] for y in sorted(loss_r_h.items(),
181
                 key=lambda x: x[0])], "+-", label="H_r")
182
        plt.plot(sorted(x), [y[1] for y in sorted(loss_r_tc.items(),
183
                 key=lambda x: x[0])], "+-", label="TC_r")
184
        plt.xlabel("Graph size")
185
        plt.ylabel("Loss ratio")
186
        plt.legend()
187
        plt.savefig(out_folder+"/plot.png")
188
        plt.show()
189
        print 
190
        print 
191
        print 
192
        print "size", "H_r", "TC_r"
193
        for s in sorted(x):
194
            print s, loss_r_h[s], loss_r_tc[s]