Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/tests/test_closeness_centrality.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """
2 Tests for closeness centrality.
3 """
4 import pytest
5 import networkx as nx
6 from networkx.testing import almost_equal
7
8
9 class TestClosenessCentrality:
10 @classmethod
11 def setup_class(cls):
12 cls.K = nx.krackhardt_kite_graph()
13 cls.P3 = nx.path_graph(3)
14 cls.P4 = nx.path_graph(4)
15 cls.K5 = nx.complete_graph(5)
16
17 cls.C4 = nx.cycle_graph(4)
18 cls.T = nx.balanced_tree(r=2, h=2)
19 cls.Gb = nx.Graph()
20 cls.Gb.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (4, 5), (3, 5)])
21
22 F = nx.florentine_families_graph()
23 cls.F = F
24
25 cls.LM = nx.les_miserables_graph()
26
27 # Create random undirected, unweighted graph for testing incremental version
28 cls.undirected_G = nx.fast_gnp_random_graph(n=100, p=0.6, seed=123)
29 cls.undirected_G_cc = nx.closeness_centrality(cls.undirected_G)
30
31 def test_wf_improved(self):
32 G = nx.union(self.P4, nx.path_graph([4, 5, 6]))
33 c = nx.closeness_centrality(G)
34 cwf = nx.closeness_centrality(G, wf_improved=False)
35 res = {0: 0.25, 1: 0.375, 2: 0.375, 3: 0.25, 4: 0.222, 5: 0.333, 6: 0.222}
36 wf_res = {0: 0.5, 1: 0.75, 2: 0.75, 3: 0.5, 4: 0.667, 5: 1.0, 6: 0.667}
37 for n in G:
38 assert almost_equal(c[n], res[n], places=3)
39 assert almost_equal(cwf[n], wf_res[n], places=3)
40
41 def test_digraph(self):
42 G = nx.path_graph(3, create_using=nx.DiGraph())
43 c = nx.closeness_centrality(G)
44 cr = nx.closeness_centrality(G.reverse())
45 d = {0: 0.0, 1: 0.500, 2: 0.667}
46 dr = {0: 0.667, 1: 0.500, 2: 0.0}
47 for n in sorted(self.P3):
48 assert almost_equal(c[n], d[n], places=3)
49 assert almost_equal(cr[n], dr[n], places=3)
50
51 def test_k5_closeness(self):
52 c = nx.closeness_centrality(self.K5)
53 d = {0: 1.000, 1: 1.000, 2: 1.000, 3: 1.000, 4: 1.000}
54 for n in sorted(self.K5):
55 assert almost_equal(c[n], d[n], places=3)
56
57 def test_p3_closeness(self):
58 c = nx.closeness_centrality(self.P3)
59 d = {0: 0.667, 1: 1.000, 2: 0.667}
60 for n in sorted(self.P3):
61 assert almost_equal(c[n], d[n], places=3)
62
63 def test_krackhardt_closeness(self):
64 c = nx.closeness_centrality(self.K)
65 d = {
66 0: 0.529,
67 1: 0.529,
68 2: 0.500,
69 3: 0.600,
70 4: 0.500,
71 5: 0.643,
72 6: 0.643,
73 7: 0.600,
74 8: 0.429,
75 9: 0.310,
76 }
77 for n in sorted(self.K):
78 assert almost_equal(c[n], d[n], places=3)
79
80 def test_florentine_families_closeness(self):
81 c = nx.closeness_centrality(self.F)
82 d = {
83 "Acciaiuoli": 0.368,
84 "Albizzi": 0.483,
85 "Barbadori": 0.4375,
86 "Bischeri": 0.400,
87 "Castellani": 0.389,
88 "Ginori": 0.333,
89 "Guadagni": 0.467,
90 "Lamberteschi": 0.326,
91 "Medici": 0.560,
92 "Pazzi": 0.286,
93 "Peruzzi": 0.368,
94 "Ridolfi": 0.500,
95 "Salviati": 0.389,
96 "Strozzi": 0.4375,
97 "Tornabuoni": 0.483,
98 }
99 for n in sorted(self.F):
100 assert almost_equal(c[n], d[n], places=3)
101
102 def test_les_miserables_closeness(self):
103 c = nx.closeness_centrality(self.LM)
104 d = {
105 "Napoleon": 0.302,
106 "Myriel": 0.429,
107 "MlleBaptistine": 0.413,
108 "MmeMagloire": 0.413,
109 "CountessDeLo": 0.302,
110 "Geborand": 0.302,
111 "Champtercier": 0.302,
112 "Cravatte": 0.302,
113 "Count": 0.302,
114 "OldMan": 0.302,
115 "Valjean": 0.644,
116 "Labarre": 0.394,
117 "Marguerite": 0.413,
118 "MmeDeR": 0.394,
119 "Isabeau": 0.394,
120 "Gervais": 0.394,
121 "Listolier": 0.341,
122 "Tholomyes": 0.392,
123 "Fameuil": 0.341,
124 "Blacheville": 0.341,
125 "Favourite": 0.341,
126 "Dahlia": 0.341,
127 "Zephine": 0.341,
128 "Fantine": 0.461,
129 "MmeThenardier": 0.461,
130 "Thenardier": 0.517,
131 "Cosette": 0.478,
132 "Javert": 0.517,
133 "Fauchelevent": 0.402,
134 "Bamatabois": 0.427,
135 "Perpetue": 0.318,
136 "Simplice": 0.418,
137 "Scaufflaire": 0.394,
138 "Woman1": 0.396,
139 "Judge": 0.404,
140 "Champmathieu": 0.404,
141 "Brevet": 0.404,
142 "Chenildieu": 0.404,
143 "Cochepaille": 0.404,
144 "Pontmercy": 0.373,
145 "Boulatruelle": 0.342,
146 "Eponine": 0.396,
147 "Anzelma": 0.352,
148 "Woman2": 0.402,
149 "MotherInnocent": 0.398,
150 "Gribier": 0.288,
151 "MmeBurgon": 0.344,
152 "Jondrette": 0.257,
153 "Gavroche": 0.514,
154 "Gillenormand": 0.442,
155 "Magnon": 0.335,
156 "MlleGillenormand": 0.442,
157 "MmePontmercy": 0.315,
158 "MlleVaubois": 0.308,
159 "LtGillenormand": 0.365,
160 "Marius": 0.531,
161 "BaronessT": 0.352,
162 "Mabeuf": 0.396,
163 "Enjolras": 0.481,
164 "Combeferre": 0.392,
165 "Prouvaire": 0.357,
166 "Feuilly": 0.392,
167 "Courfeyrac": 0.400,
168 "Bahorel": 0.394,
169 "Bossuet": 0.475,
170 "Joly": 0.394,
171 "Grantaire": 0.358,
172 "MotherPlutarch": 0.285,
173 "Gueulemer": 0.463,
174 "Babet": 0.463,
175 "Claquesous": 0.452,
176 "Montparnasse": 0.458,
177 "Toussaint": 0.402,
178 "Child1": 0.342,
179 "Child2": 0.342,
180 "Brujon": 0.380,
181 "MmeHucheloup": 0.353,
182 }
183 for n in sorted(self.LM):
184 assert almost_equal(c[n], d[n], places=3)
185
186 def test_weighted_closeness(self):
187 edges = [
188 ("s", "u", 10),
189 ("s", "x", 5),
190 ("u", "v", 1),
191 ("u", "x", 2),
192 ("v", "y", 1),
193 ("x", "u", 3),
194 ("x", "v", 5),
195 ("x", "y", 2),
196 ("y", "s", 7),
197 ("y", "v", 6),
198 ]
199 XG = nx.Graph()
200 XG.add_weighted_edges_from(edges)
201 c = nx.closeness_centrality(XG, distance="weight")
202 d = {"y": 0.200, "x": 0.286, "s": 0.138, "u": 0.235, "v": 0.200}
203 for n in sorted(XG):
204 assert almost_equal(c[n], d[n], places=3)
205
206 #
207 # Tests for incremental closeness centrality.
208 #
209 @staticmethod
210 def pick_add_edge(g):
211 u = nx.utils.arbitrary_element(g)
212 possible_nodes = set(g.nodes())
213 neighbors = list(g.neighbors(u)) + [u]
214 possible_nodes.difference_update(neighbors)
215 v = nx.utils.arbitrary_element(possible_nodes)
216 return (u, v)
217
218 @staticmethod
219 def pick_remove_edge(g):
220 u = nx.utils.arbitrary_element(g)
221 possible_nodes = list(g.neighbors(u))
222 v = nx.utils.arbitrary_element(possible_nodes)
223 return (u, v)
224
225 def test_directed_raises(self):
226 with pytest.raises(nx.NetworkXNotImplemented):
227 dir_G = nx.gn_graph(n=5)
228 prev_cc = None
229 edge = self.pick_add_edge(dir_G)
230 insert = True
231 nx.incremental_closeness_centrality(dir_G, edge, prev_cc, insert)
232
233 def test_wrong_size_prev_cc_raises(self):
234 with pytest.raises(nx.NetworkXError):
235 G = self.undirected_G.copy()
236 edge = self.pick_add_edge(G)
237 insert = True
238 prev_cc = self.undirected_G_cc.copy()
239 prev_cc.pop(0)
240 nx.incremental_closeness_centrality(G, edge, prev_cc, insert)
241
242 def test_wrong_nodes_prev_cc_raises(self):
243 with pytest.raises(nx.NetworkXError):
244 G = self.undirected_G.copy()
245 edge = self.pick_add_edge(G)
246 insert = True
247 prev_cc = self.undirected_G_cc.copy()
248 num_nodes = len(prev_cc)
249 prev_cc.pop(0)
250 prev_cc[num_nodes] = 0.5
251 nx.incremental_closeness_centrality(G, edge, prev_cc, insert)
252
253 def test_zero_centrality(self):
254 G = nx.path_graph(3)
255 prev_cc = nx.closeness_centrality(G)
256 edge = self.pick_remove_edge(G)
257 test_cc = nx.incremental_closeness_centrality(G, edge, prev_cc, insertion=False)
258 G.remove_edges_from([edge])
259 real_cc = nx.closeness_centrality(G)
260 shared_items = set(test_cc.items()) & set(real_cc.items())
261 assert len(shared_items) == len(real_cc)
262 assert 0 in test_cc.values()
263
264 def test_incremental(self):
265 # Check that incremental and regular give same output
266 G = self.undirected_G.copy()
267 prev_cc = None
268 for i in range(5):
269 if i % 2 == 0:
270 # Remove an edge
271 insert = False
272 edge = self.pick_remove_edge(G)
273 else:
274 # Add an edge
275 insert = True
276 edge = self.pick_add_edge(G)
277
278 # start = timeit.default_timer()
279 test_cc = nx.incremental_closeness_centrality(G, edge, prev_cc, insert)
280 # inc_elapsed = (timeit.default_timer() - start)
281 # print(f"incremental time: {inc_elapsed}")
282
283 if insert:
284 G.add_edges_from([edge])
285 else:
286 G.remove_edges_from([edge])
287
288 # start = timeit.default_timer()
289 real_cc = nx.closeness_centrality(G)
290 # reg_elapsed = (timeit.default_timer() - start)
291 # print(f"regular time: {reg_elapsed}")
292 # Example output:
293 # incremental time: 0.208
294 # regular time: 0.276
295 # incremental time: 0.00683
296 # regular time: 0.260
297 # incremental time: 0.0224
298 # regular time: 0.278
299 # incremental time: 0.00804
300 # regular time: 0.208
301 # incremental time: 0.00947
302 # regular time: 0.188
303
304 assert set(test_cc.items()) == set(real_cc.items())
305
306 prev_cc = test_cc