Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/linalg/tests/test_algebraic_connectivity.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 from math import sqrt | |
2 | |
3 import pytest | |
4 | |
5 numpy = pytest.importorskip("numpy") | |
6 numpy.linalg = pytest.importorskip("numpy.linalg") | |
7 scipy = pytest.importorskip("scipy") | |
8 scipy.sparse = pytest.importorskip("scipy.sparse") | |
9 | |
10 | |
11 import networkx as nx | |
12 from networkx.testing import almost_equal | |
13 | |
14 try: | |
15 from scikits.sparse.cholmod import cholesky | |
16 | |
17 _cholesky = cholesky | |
18 except ImportError: | |
19 _cholesky = None | |
20 | |
21 if _cholesky is None: | |
22 methods = ("tracemin_pcg", "tracemin_lu", "lanczos", "lobpcg") | |
23 else: | |
24 methods = ("tracemin_pcg", "tracemin_chol", "tracemin_lu", "lanczos", "lobpcg") | |
25 | |
26 | |
27 def check_eigenvector(A, l, x): | |
28 nx = numpy.linalg.norm(x) | |
29 # Check zeroness. | |
30 assert not almost_equal(nx, 0) | |
31 y = A * x | |
32 ny = numpy.linalg.norm(y) | |
33 # Check collinearity. | |
34 assert almost_equal(numpy.dot(x, y), nx * ny) | |
35 # Check eigenvalue. | |
36 assert almost_equal(ny, l * nx) | |
37 | |
38 | |
39 class TestAlgebraicConnectivity: | |
40 @pytest.mark.parametrize("method", methods) | |
41 def test_directed(self, method): | |
42 G = nx.DiGraph() | |
43 pytest.raises( | |
44 nx.NetworkXNotImplemented, nx.algebraic_connectivity, G, method=method | |
45 ) | |
46 pytest.raises(nx.NetworkXNotImplemented, nx.fiedler_vector, G, method=method) | |
47 | |
48 @pytest.mark.parametrize("method", methods) | |
49 def test_null_and_singleton(self, method): | |
50 G = nx.Graph() | |
51 pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method=method) | |
52 pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method) | |
53 G.add_edge(0, 0) | |
54 pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method=method) | |
55 pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method) | |
56 | |
57 @pytest.mark.parametrize("method", methods) | |
58 def test_disconnected(self, method): | |
59 G = nx.Graph() | |
60 G.add_nodes_from(range(2)) | |
61 assert nx.algebraic_connectivity(G) == 0 | |
62 pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method) | |
63 G.add_edge(0, 1, weight=0) | |
64 assert nx.algebraic_connectivity(G) == 0 | |
65 pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method=method) | |
66 | |
67 def test_unrecognized_method(self): | |
68 G = nx.path_graph(4) | |
69 pytest.raises(nx.NetworkXError, nx.algebraic_connectivity, G, method="unknown") | |
70 pytest.raises(nx.NetworkXError, nx.fiedler_vector, G, method="unknown") | |
71 | |
72 @pytest.mark.parametrize("method", methods) | |
73 def test_two_nodes(self, method): | |
74 G = nx.Graph() | |
75 G.add_edge(0, 1, weight=1) | |
76 A = nx.laplacian_matrix(G) | |
77 assert almost_equal(nx.algebraic_connectivity(G, tol=1e-12, method=method), 2) | |
78 x = nx.fiedler_vector(G, tol=1e-12, method=method) | |
79 check_eigenvector(A, 2, x) | |
80 | |
81 @pytest.mark.parametrize("method", methods) | |
82 def test_two_nodes_multigraph(self, method): | |
83 G = nx.MultiGraph() | |
84 G.add_edge(0, 0, spam=1e8) | |
85 G.add_edge(0, 1, spam=1) | |
86 G.add_edge(0, 1, spam=-2) | |
87 A = -3 * nx.laplacian_matrix(G, weight="spam") | |
88 assert almost_equal( | |
89 nx.algebraic_connectivity(G, weight="spam", tol=1e-12, method=method), 6 | |
90 ) | |
91 x = nx.fiedler_vector(G, weight="spam", tol=1e-12, method=method) | |
92 check_eigenvector(A, 6, x) | |
93 | |
94 def test_abbreviation_of_method(self): | |
95 G = nx.path_graph(8) | |
96 A = nx.laplacian_matrix(G) | |
97 sigma = 2 - sqrt(2 + sqrt(2)) | |
98 ac = nx.algebraic_connectivity(G, tol=1e-12, method="tracemin") | |
99 assert almost_equal(ac, sigma) | |
100 x = nx.fiedler_vector(G, tol=1e-12, method="tracemin") | |
101 check_eigenvector(A, sigma, x) | |
102 | |
103 @pytest.mark.parametrize("method", methods) | |
104 def test_path(self, method): | |
105 G = nx.path_graph(8) | |
106 A = nx.laplacian_matrix(G) | |
107 sigma = 2 - sqrt(2 + sqrt(2)) | |
108 ac = nx.algebraic_connectivity(G, tol=1e-12, method=method) | |
109 assert almost_equal(ac, sigma) | |
110 x = nx.fiedler_vector(G, tol=1e-12, method=method) | |
111 check_eigenvector(A, sigma, x) | |
112 | |
113 @pytest.mark.parametrize("method", methods) | |
114 def test_problematic_graph_issue_2381(self, method): | |
115 G = nx.path_graph(4) | |
116 G.add_edges_from([(4, 2), (5, 1)]) | |
117 A = nx.laplacian_matrix(G) | |
118 sigma = 0.438447187191 | |
119 ac = nx.algebraic_connectivity(G, tol=1e-12, method=method) | |
120 assert almost_equal(ac, sigma) | |
121 x = nx.fiedler_vector(G, tol=1e-12, method=method) | |
122 check_eigenvector(A, sigma, x) | |
123 | |
124 @pytest.mark.parametrize("method", methods) | |
125 def test_cycle(self, method): | |
126 G = nx.cycle_graph(8) | |
127 A = nx.laplacian_matrix(G) | |
128 sigma = 2 - sqrt(2) | |
129 ac = nx.algebraic_connectivity(G, tol=1e-12, method=method) | |
130 assert almost_equal(ac, sigma) | |
131 x = nx.fiedler_vector(G, tol=1e-12, method=method) | |
132 check_eigenvector(A, sigma, x) | |
133 | |
134 @pytest.mark.parametrize("method", methods) | |
135 def test_seed_argument(self, method): | |
136 G = nx.cycle_graph(8) | |
137 A = nx.laplacian_matrix(G) | |
138 sigma = 2 - sqrt(2) | |
139 ac = nx.algebraic_connectivity(G, tol=1e-12, method=method, seed=1) | |
140 assert almost_equal(ac, sigma) | |
141 x = nx.fiedler_vector(G, tol=1e-12, method=method, seed=1) | |
142 check_eigenvector(A, sigma, x) | |
143 | |
144 @pytest.mark.parametrize( | |
145 ("normalized", "sigma", "laplacian_fn"), | |
146 ( | |
147 (False, 0.2434017461399311, nx.laplacian_matrix), | |
148 (True, 0.08113391537997749, nx.normalized_laplacian_matrix), | |
149 ), | |
150 ) | |
151 @pytest.mark.parametrize("method", methods) | |
152 def test_buckminsterfullerene(self, normalized, sigma, laplacian_fn, method): | |
153 G = nx.Graph( | |
154 [ | |
155 (1, 10), | |
156 (1, 41), | |
157 (1, 59), | |
158 (2, 12), | |
159 (2, 42), | |
160 (2, 60), | |
161 (3, 6), | |
162 (3, 43), | |
163 (3, 57), | |
164 (4, 8), | |
165 (4, 44), | |
166 (4, 58), | |
167 (5, 13), | |
168 (5, 56), | |
169 (5, 57), | |
170 (6, 10), | |
171 (6, 31), | |
172 (7, 14), | |
173 (7, 56), | |
174 (7, 58), | |
175 (8, 12), | |
176 (8, 32), | |
177 (9, 23), | |
178 (9, 53), | |
179 (9, 59), | |
180 (10, 15), | |
181 (11, 24), | |
182 (11, 53), | |
183 (11, 60), | |
184 (12, 16), | |
185 (13, 14), | |
186 (13, 25), | |
187 (14, 26), | |
188 (15, 27), | |
189 (15, 49), | |
190 (16, 28), | |
191 (16, 50), | |
192 (17, 18), | |
193 (17, 19), | |
194 (17, 54), | |
195 (18, 20), | |
196 (18, 55), | |
197 (19, 23), | |
198 (19, 41), | |
199 (20, 24), | |
200 (20, 42), | |
201 (21, 31), | |
202 (21, 33), | |
203 (21, 57), | |
204 (22, 32), | |
205 (22, 34), | |
206 (22, 58), | |
207 (23, 24), | |
208 (25, 35), | |
209 (25, 43), | |
210 (26, 36), | |
211 (26, 44), | |
212 (27, 51), | |
213 (27, 59), | |
214 (28, 52), | |
215 (28, 60), | |
216 (29, 33), | |
217 (29, 34), | |
218 (29, 56), | |
219 (30, 51), | |
220 (30, 52), | |
221 (30, 53), | |
222 (31, 47), | |
223 (32, 48), | |
224 (33, 45), | |
225 (34, 46), | |
226 (35, 36), | |
227 (35, 37), | |
228 (36, 38), | |
229 (37, 39), | |
230 (37, 49), | |
231 (38, 40), | |
232 (38, 50), | |
233 (39, 40), | |
234 (39, 51), | |
235 (40, 52), | |
236 (41, 47), | |
237 (42, 48), | |
238 (43, 49), | |
239 (44, 50), | |
240 (45, 46), | |
241 (45, 54), | |
242 (46, 55), | |
243 (47, 54), | |
244 (48, 55), | |
245 ] | |
246 ) | |
247 A = laplacian_fn(G) | |
248 try: | |
249 assert almost_equal( | |
250 nx.algebraic_connectivity( | |
251 G, normalized=normalized, tol=1e-12, method=method | |
252 ), | |
253 sigma, | |
254 ) | |
255 x = nx.fiedler_vector(G, normalized=normalized, tol=1e-12, method=method) | |
256 check_eigenvector(A, sigma, x) | |
257 except nx.NetworkXError as e: | |
258 if e.args not in ( | |
259 ("Cholesky solver unavailable.",), | |
260 ("LU solver unavailable.",), | |
261 ): | |
262 raise | |
263 | |
264 | |
265 class TestSpectralOrdering: | |
266 _graphs = (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph) | |
267 | |
268 @pytest.mark.parametrize("graph", _graphs) | |
269 def test_nullgraph(self, graph): | |
270 G = graph() | |
271 pytest.raises(nx.NetworkXError, nx.spectral_ordering, G) | |
272 | |
273 @pytest.mark.parametrize("graph", _graphs) | |
274 def test_singleton(self, graph): | |
275 G = graph() | |
276 G.add_node("x") | |
277 assert nx.spectral_ordering(G) == ["x"] | |
278 G.add_edge("x", "x", weight=33) | |
279 G.add_edge("x", "x", weight=33) | |
280 assert nx.spectral_ordering(G) == ["x"] | |
281 | |
282 def test_unrecognized_method(self): | |
283 G = nx.path_graph(4) | |
284 pytest.raises(nx.NetworkXError, nx.spectral_ordering, G, method="unknown") | |
285 | |
286 @pytest.mark.parametrize("method", methods) | |
287 def test_three_nodes(self, method): | |
288 G = nx.Graph() | |
289 G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1)], weight="spam") | |
290 order = nx.spectral_ordering(G, weight="spam", method=method) | |
291 assert set(order) == set(G) | |
292 assert {1, 3} in (set(order[:-1]), set(order[1:])) | |
293 | |
294 @pytest.mark.parametrize("method", methods) | |
295 def test_three_nodes_multigraph(self, method): | |
296 G = nx.MultiDiGraph() | |
297 G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1), (2, 3, 2)]) | |
298 order = nx.spectral_ordering(G, method=method) | |
299 assert set(order) == set(G) | |
300 assert {2, 3} in (set(order[:-1]), set(order[1:])) | |
301 | |
302 @pytest.mark.parametrize("method", methods) | |
303 def test_path(self, method): | |
304 # based on setup_class numpy is installed if we get here | |
305 from numpy.random import shuffle | |
306 | |
307 path = list(range(10)) | |
308 shuffle(path) | |
309 G = nx.Graph() | |
310 nx.add_path(G, path) | |
311 order = nx.spectral_ordering(G, method=method) | |
312 assert order in [path, list(reversed(path))] | |
313 | |
314 @pytest.mark.parametrize("method", methods) | |
315 def test_seed_argument(self, method): | |
316 # based on setup_class numpy is installed if we get here | |
317 from numpy.random import shuffle | |
318 | |
319 path = list(range(10)) | |
320 shuffle(path) | |
321 G = nx.Graph() | |
322 nx.add_path(G, path) | |
323 order = nx.spectral_ordering(G, method=method, seed=1) | |
324 assert order in [path, list(reversed(path))] | |
325 | |
326 @pytest.mark.parametrize("method", methods) | |
327 def test_disconnected(self, method): | |
328 G = nx.Graph() | |
329 nx.add_path(G, range(0, 10, 2)) | |
330 nx.add_path(G, range(1, 10, 2)) | |
331 order = nx.spectral_ordering(G, method=method) | |
332 assert set(order) == set(G) | |
333 seqs = [ | |
334 list(range(0, 10, 2)), | |
335 list(range(8, -1, -2)), | |
336 list(range(1, 10, 2)), | |
337 list(range(9, -1, -2)), | |
338 ] | |
339 assert order[:5] in seqs | |
340 assert order[5:] in seqs | |
341 | |
342 @pytest.mark.parametrize( | |
343 ("normalized", "expected_order"), | |
344 ( | |
345 (False, [[1, 2, 0, 3, 4, 5, 6, 9, 7, 8], [8, 7, 9, 6, 5, 4, 3, 0, 2, 1]]), | |
346 (True, [[1, 2, 3, 0, 4, 5, 9, 6, 7, 8], [8, 7, 6, 9, 5, 4, 0, 3, 2, 1]]), | |
347 ), | |
348 ) | |
349 @pytest.mark.parametrize("method", methods) | |
350 def test_cycle(self, normalized, expected_order, method): | |
351 path = list(range(10)) | |
352 G = nx.Graph() | |
353 nx.add_path(G, path, weight=5) | |
354 G.add_edge(path[-1], path[0], weight=1) | |
355 A = nx.laplacian_matrix(G).todense() | |
356 try: | |
357 order = nx.spectral_ordering(G, normalized=normalized, method=method) | |
358 except nx.NetworkXError as e: | |
359 if e.args not in ( | |
360 ("Cholesky solver unavailable.",), | |
361 ("LU solver unavailable.",), | |
362 ): | |
363 raise | |
364 else: | |
365 assert order in expected_order |