Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/tests/test_random_graphs.py @ 0:4f3585e2f14b draft default tip
"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 """Unit tests for the :mod:`networkx.generators.random_graphs` module. | |
2 | |
3 """ | |
4 import pytest | |
5 | |
6 from networkx.exception import NetworkXError | |
7 from networkx.generators.random_graphs import barabasi_albert_graph | |
8 from networkx.generators.random_graphs import dual_barabasi_albert_graph | |
9 from networkx.generators.random_graphs import extended_barabasi_albert_graph | |
10 from networkx.generators.random_graphs import binomial_graph | |
11 from networkx.generators.random_graphs import connected_watts_strogatz_graph | |
12 from networkx.generators.random_graphs import dense_gnm_random_graph | |
13 from networkx.generators.random_graphs import erdos_renyi_graph | |
14 from networkx.generators.random_graphs import fast_gnp_random_graph | |
15 from networkx.generators.random_graphs import gnm_random_graph | |
16 from networkx.generators.random_graphs import gnp_random_graph | |
17 from networkx.generators.random_graphs import newman_watts_strogatz_graph | |
18 from networkx.generators.random_graphs import powerlaw_cluster_graph | |
19 from networkx.generators.random_graphs import random_kernel_graph | |
20 from networkx.generators.random_graphs import random_lobster | |
21 from networkx.generators.random_graphs import random_powerlaw_tree | |
22 from networkx.generators.random_graphs import random_powerlaw_tree_sequence | |
23 from networkx.generators.random_graphs import random_regular_graph | |
24 from networkx.generators.random_graphs import random_shell_graph | |
25 from networkx.generators.random_graphs import watts_strogatz_graph | |
26 | |
27 | |
28 class TestGeneratorsRandom: | |
29 def test_random_graph(self): | |
30 seed = 42 | |
31 G = gnp_random_graph(100, 0.25, seed) | |
32 G = gnp_random_graph(100, 0.25, seed, directed=True) | |
33 G = binomial_graph(100, 0.25, seed) | |
34 G = erdos_renyi_graph(100, 0.25, seed) | |
35 G = fast_gnp_random_graph(100, 0.25, seed) | |
36 G = fast_gnp_random_graph(100, 0.25, seed, directed=True) | |
37 G = gnm_random_graph(100, 20, seed) | |
38 G = gnm_random_graph(100, 20, seed, directed=True) | |
39 G = dense_gnm_random_graph(100, 20, seed) | |
40 | |
41 G = watts_strogatz_graph(10, 2, 0.25, seed) | |
42 assert len(G) == 10 | |
43 assert G.number_of_edges() == 10 | |
44 | |
45 G = connected_watts_strogatz_graph(10, 2, 0.1, tries=10, seed=seed) | |
46 assert len(G) == 10 | |
47 assert G.number_of_edges() == 10 | |
48 pytest.raises( | |
49 NetworkXError, connected_watts_strogatz_graph, 10, 2, 0.1, tries=0 | |
50 ) | |
51 | |
52 G = watts_strogatz_graph(10, 4, 0.25, seed) | |
53 assert len(G) == 10 | |
54 assert G.number_of_edges() == 20 | |
55 | |
56 G = newman_watts_strogatz_graph(10, 2, 0.0, seed) | |
57 assert len(G) == 10 | |
58 assert G.number_of_edges() == 10 | |
59 | |
60 G = newman_watts_strogatz_graph(10, 4, 0.25, seed) | |
61 assert len(G) == 10 | |
62 assert G.number_of_edges() >= 20 | |
63 | |
64 G = barabasi_albert_graph(100, 1, seed) | |
65 G = barabasi_albert_graph(100, 3, seed) | |
66 assert G.number_of_edges() == (97 * 3) | |
67 | |
68 G = extended_barabasi_albert_graph(100, 1, 0, 0, seed) | |
69 assert G.number_of_edges() == 99 | |
70 G = extended_barabasi_albert_graph(100, 3, 0, 0, seed) | |
71 assert G.number_of_edges() == 97 * 3 | |
72 G = extended_barabasi_albert_graph(100, 1, 0, 0.5, seed) | |
73 assert G.number_of_edges() == 99 | |
74 G = extended_barabasi_albert_graph(100, 2, 0.5, 0, seed) | |
75 assert G.number_of_edges() > 100 * 3 | |
76 assert G.number_of_edges() < 100 * 4 | |
77 | |
78 G = extended_barabasi_albert_graph(100, 2, 0.3, 0.3, seed) | |
79 assert G.number_of_edges() > 100 * 2 | |
80 assert G.number_of_edges() < 100 * 4 | |
81 | |
82 G = powerlaw_cluster_graph(100, 1, 1.0, seed) | |
83 G = powerlaw_cluster_graph(100, 3, 0.0, seed) | |
84 assert G.number_of_edges() == (97 * 3) | |
85 | |
86 G = random_regular_graph(10, 20, seed) | |
87 | |
88 pytest.raises(NetworkXError, random_regular_graph, 3, 21) | |
89 pytest.raises(NetworkXError, random_regular_graph, 33, 21) | |
90 | |
91 constructor = [(10, 20, 0.8), (20, 40, 0.8)] | |
92 G = random_shell_graph(constructor, seed) | |
93 | |
94 def is_caterpillar(g): | |
95 """ | |
96 A tree is a caterpillar iff all nodes of degree >=3 are surrounded | |
97 by at most two nodes of degree two or greater. | |
98 ref: http://mathworld.wolfram.com/CaterpillarGraph.html | |
99 """ | |
100 deg_over_3 = [n for n in g if g.degree(n) >= 3] | |
101 for n in deg_over_3: | |
102 nbh_deg_over_2 = [nbh for nbh in g.neighbors(n) if g.degree(nbh) >= 2] | |
103 if not len(nbh_deg_over_2) <= 2: | |
104 return False | |
105 return True | |
106 | |
107 def is_lobster(g): | |
108 """ | |
109 A tree is a lobster if it has the property that the removal of leaf | |
110 nodes leaves a caterpillar graph (Gallian 2007) | |
111 ref: http://mathworld.wolfram.com/LobsterGraph.html | |
112 """ | |
113 non_leafs = [n for n in g if g.degree(n) > 1] | |
114 return is_caterpillar(g.subgraph(non_leafs)) | |
115 | |
116 G = random_lobster(10, 0.1, 0.5, seed) | |
117 assert max([G.degree(n) for n in G.nodes()]) > 3 | |
118 assert is_lobster(G) | |
119 pytest.raises(NetworkXError, random_lobster, 10, 0.1, 1, seed) | |
120 pytest.raises(NetworkXError, random_lobster, 10, 1, 1, seed) | |
121 pytest.raises(NetworkXError, random_lobster, 10, 1, 0.5, seed) | |
122 | |
123 # docstring says this should be a caterpillar | |
124 G = random_lobster(10, 0.1, 0.0, seed) | |
125 assert is_caterpillar(G) | |
126 | |
127 # difficult to find seed that requires few tries | |
128 seq = random_powerlaw_tree_sequence(10, 3, seed=14, tries=1) | |
129 G = random_powerlaw_tree(10, 3, seed=14, tries=1) | |
130 | |
131 def test_dual_barabasi_albert(self, m1=1, m2=4, p=0.5): | |
132 """ | |
133 Tests that the dual BA random graph generated behaves consistently. | |
134 | |
135 Tests the exceptions are raised as expected. | |
136 | |
137 The graphs generation are repeated several times to prevent lucky shots | |
138 | |
139 """ | |
140 seed = 42 | |
141 repeats = 2 | |
142 | |
143 while repeats: | |
144 repeats -= 1 | |
145 | |
146 # This should be BA with m = m1 | |
147 BA1 = barabasi_albert_graph(100, m1, seed) | |
148 DBA1 = dual_barabasi_albert_graph(100, m1, m2, 1, seed) | |
149 assert BA1.size() == DBA1.size() | |
150 | |
151 # This should be BA with m = m2 | |
152 BA2 = barabasi_albert_graph(100, m2, seed) | |
153 DBA2 = dual_barabasi_albert_graph(100, m1, m2, 0, seed) | |
154 assert BA2.size() == DBA2.size() | |
155 | |
156 # Testing exceptions | |
157 dbag = dual_barabasi_albert_graph | |
158 pytest.raises(NetworkXError, dbag, m1, m1, m2, 0) | |
159 pytest.raises(NetworkXError, dbag, m2, m1, m2, 0) | |
160 pytest.raises(NetworkXError, dbag, 100, m1, m2, -0.5) | |
161 pytest.raises(NetworkXError, dbag, 100, m1, m2, 1.5) | |
162 | |
163 def test_extended_barabasi_albert(self, m=2): | |
164 """ | |
165 Tests that the extended BA random graph generated behaves consistently. | |
166 | |
167 Tests the exceptions are raised as expected. | |
168 | |
169 The graphs generation are repeated several times to prevent lucky-shots | |
170 | |
171 """ | |
172 seed = 42 | |
173 repeats = 2 | |
174 BA_model = barabasi_albert_graph(100, m, seed) | |
175 BA_model_edges = BA_model.number_of_edges() | |
176 | |
177 while repeats: | |
178 repeats -= 1 | |
179 | |
180 # This behaves just like BA, the number of edges must be the same | |
181 G1 = extended_barabasi_albert_graph(100, m, 0, 0, seed) | |
182 assert G1.size() == BA_model_edges | |
183 | |
184 # More than twice more edges should have been added | |
185 G1 = extended_barabasi_albert_graph(100, m, 0.8, 0, seed) | |
186 assert G1.size() > BA_model_edges * 2 | |
187 | |
188 # Only edge rewiring, so the number of edges less than original | |
189 G2 = extended_barabasi_albert_graph(100, m, 0, 0.8, seed) | |
190 assert G2.size() == BA_model_edges | |
191 | |
192 # Mixed scenario: less edges than G1 and more edges than G2 | |
193 G3 = extended_barabasi_albert_graph(100, m, 0.3, 0.3, seed) | |
194 assert G3.size() > G2.size() | |
195 assert G3.size() < G1.size() | |
196 | |
197 # Testing exceptions | |
198 ebag = extended_barabasi_albert_graph | |
199 pytest.raises(NetworkXError, ebag, m, m, 0, 0) | |
200 pytest.raises(NetworkXError, ebag, 1, 0.5, 0, 0) | |
201 pytest.raises(NetworkXError, ebag, 100, 2, 0.5, 0.5) | |
202 | |
203 def test_random_zero_regular_graph(self): | |
204 """Tests that a 0-regular graph has the correct number of nodes and | |
205 edges. | |
206 | |
207 """ | |
208 seed = 42 | |
209 G = random_regular_graph(0, 10, seed) | |
210 assert len(G) == 10 | |
211 assert sum(1 for _ in G.edges()) == 0 | |
212 | |
213 def test_gnp(self): | |
214 for generator in [ | |
215 gnp_random_graph, | |
216 binomial_graph, | |
217 erdos_renyi_graph, | |
218 fast_gnp_random_graph, | |
219 ]: | |
220 G = generator(10, -1.1) | |
221 assert len(G) == 10 | |
222 assert sum(1 for _ in G.edges()) == 0 | |
223 | |
224 G = generator(10, 0.1) | |
225 assert len(G) == 10 | |
226 | |
227 G = generator(10, 0.1, seed=42) | |
228 assert len(G) == 10 | |
229 | |
230 G = generator(10, 1.1) | |
231 assert len(G) == 10 | |
232 assert sum(1 for _ in G.edges()) == 45 | |
233 | |
234 G = generator(10, -1.1, directed=True) | |
235 assert G.is_directed() | |
236 assert len(G) == 10 | |
237 assert sum(1 for _ in G.edges()) == 0 | |
238 | |
239 G = generator(10, 0.1, directed=True) | |
240 assert G.is_directed() | |
241 assert len(G) == 10 | |
242 | |
243 G = generator(10, 1.1, directed=True) | |
244 assert G.is_directed() | |
245 assert len(G) == 10 | |
246 assert sum(1 for _ in G.edges()) == 90 | |
247 | |
248 # assert that random graphs generate all edges for p close to 1 | |
249 edges = 0 | |
250 runs = 100 | |
251 for i in range(runs): | |
252 edges += sum(1 for _ in generator(10, 0.99999, directed=True).edges()) | |
253 assert abs(edges / float(runs) - 90) <= runs * 2.0 / 100 | |
254 | |
255 def test_gnm(self): | |
256 G = gnm_random_graph(10, 3) | |
257 assert len(G) == 10 | |
258 assert sum(1 for _ in G.edges()) == 3 | |
259 | |
260 G = gnm_random_graph(10, 3, seed=42) | |
261 assert len(G) == 10 | |
262 assert sum(1 for _ in G.edges()) == 3 | |
263 | |
264 G = gnm_random_graph(10, 100) | |
265 assert len(G) == 10 | |
266 assert sum(1 for _ in G.edges()) == 45 | |
267 | |
268 G = gnm_random_graph(10, 100, directed=True) | |
269 assert len(G) == 10 | |
270 assert sum(1 for _ in G.edges()) == 90 | |
271 | |
272 G = gnm_random_graph(10, -1.1) | |
273 assert len(G) == 10 | |
274 assert sum(1 for _ in G.edges()) == 0 | |
275 | |
276 def test_watts_strogatz_big_k(self): | |
277 # Test to make sure than n <= k | |
278 pytest.raises(NetworkXError, watts_strogatz_graph, 10, 11, 0.25) | |
279 pytest.raises(NetworkXError, newman_watts_strogatz_graph, 10, 11, 0.25) | |
280 | |
281 # could create an infinite loop, now doesn't | |
282 # infinite loop used to occur when a node has degree n-1 and needs to rewire | |
283 watts_strogatz_graph(10, 9, 0.25, seed=0) | |
284 newman_watts_strogatz_graph(10, 9, 0.5, seed=0) | |
285 | |
286 # Test k==n scenario | |
287 watts_strogatz_graph(10, 10, 0.25, seed=0) | |
288 newman_watts_strogatz_graph(10, 10, 0.25, seed=0) | |
289 | |
290 def test_random_kernel_graph(self): | |
291 def integral(u, w, z): | |
292 return c * (z - w) | |
293 | |
294 def root(u, w, r): | |
295 return r / c + w | |
296 | |
297 c = 1 | |
298 graph = random_kernel_graph(1000, integral, root) | |
299 graph = random_kernel_graph(1000, integral, root, seed=42) | |
300 assert len(graph) == 1000 |