Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_threshold.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 """ | |
2 Threshold Graphs | |
3 ================ | |
4 """ | |
5 | |
6 import pytest | |
7 | |
8 import networkx as nx | |
9 import networkx.algorithms.threshold as nxt | |
10 from networkx.algorithms.isomorphism.isomorph import graph_could_be_isomorphic | |
11 from networkx.testing import almost_equal | |
12 | |
13 cnlti = nx.convert_node_labels_to_integers | |
14 | |
15 | |
16 class TestGeneratorThreshold: | |
17 def test_threshold_sequence_graph_test(self): | |
18 G = nx.star_graph(10) | |
19 assert nxt.is_threshold_graph(G) | |
20 assert nxt.is_threshold_sequence(list(d for n, d in G.degree())) | |
21 | |
22 G = nx.complete_graph(10) | |
23 assert nxt.is_threshold_graph(G) | |
24 assert nxt.is_threshold_sequence(list(d for n, d in G.degree())) | |
25 | |
26 deg = [3, 2, 2, 1, 1, 1] | |
27 assert not nxt.is_threshold_sequence(deg) | |
28 | |
29 deg = [3, 2, 2, 1] | |
30 assert nxt.is_threshold_sequence(deg) | |
31 | |
32 G = nx.generators.havel_hakimi_graph(deg) | |
33 assert nxt.is_threshold_graph(G) | |
34 | |
35 def test_creation_sequences(self): | |
36 deg = [3, 2, 2, 1] | |
37 G = nx.generators.havel_hakimi_graph(deg) | |
38 | |
39 with pytest.raises(ValueError): | |
40 nxt.creation_sequence(deg, with_labels=True, compact=True) | |
41 | |
42 cs0 = nxt.creation_sequence(deg) | |
43 H0 = nxt.threshold_graph(cs0) | |
44 assert "".join(cs0) == "ddid" | |
45 | |
46 cs1 = nxt.creation_sequence(deg, with_labels=True) | |
47 H1 = nxt.threshold_graph(cs1) | |
48 assert cs1 == [(1, "d"), (2, "d"), (3, "i"), (0, "d")] | |
49 | |
50 cs2 = nxt.creation_sequence(deg, compact=True) | |
51 H2 = nxt.threshold_graph(cs2) | |
52 assert cs2 == [2, 1, 1] | |
53 assert "".join(nxt.uncompact(cs2)) == "ddid" | |
54 assert graph_could_be_isomorphic(H0, G) | |
55 assert graph_could_be_isomorphic(H0, H1) | |
56 assert graph_could_be_isomorphic(H0, H2) | |
57 | |
58 def test_make_compact(self): | |
59 assert nxt.make_compact(["d", "d", "d", "i", "d", "d"]) == [3, 1, 2] | |
60 assert nxt.make_compact([3, 1, 2]) == [3, 1, 2] | |
61 assert pytest.raises(TypeError, nxt.make_compact, [3.0, 1.0, 2.0]) | |
62 | |
63 def test_uncompact(self): | |
64 assert nxt.uncompact([3, 1, 2]) == ["d", "d", "d", "i", "d", "d"] | |
65 assert nxt.uncompact(["d", "d", "i", "d"]) == ["d", "d", "i", "d"] | |
66 assert nxt.uncompact( | |
67 nxt.uncompact([(1, "d"), (2, "d"), (3, "i"), (0, "d")]) | |
68 ) == nxt.uncompact([(1, "d"), (2, "d"), (3, "i"), (0, "d")]) | |
69 assert pytest.raises(TypeError, nxt.uncompact, [3.0, 1.0, 2.0]) | |
70 | |
71 def test_creation_sequence_to_weights(self): | |
72 assert nxt.creation_sequence_to_weights([3, 1, 2]) == [ | |
73 0.5, | |
74 0.5, | |
75 0.5, | |
76 0.25, | |
77 0.75, | |
78 0.75, | |
79 ] | |
80 assert pytest.raises( | |
81 TypeError, nxt.creation_sequence_to_weights, [3.0, 1.0, 2.0] | |
82 ) | |
83 | |
84 def test_weights_to_creation_sequence(self): | |
85 deg = [3, 2, 2, 1] | |
86 with pytest.raises(ValueError): | |
87 nxt.weights_to_creation_sequence(deg, with_labels=True, compact=True) | |
88 assert nxt.weights_to_creation_sequence(deg, with_labels=True) == [ | |
89 (3, "d"), | |
90 (1, "d"), | |
91 (2, "d"), | |
92 (0, "d"), | |
93 ] | |
94 assert nxt.weights_to_creation_sequence(deg, compact=True) == [4] | |
95 | |
96 def test_find_alternating_4_cycle(self): | |
97 G = nx.Graph() | |
98 G.add_edge(1, 2) | |
99 assert not nxt.find_alternating_4_cycle(G) | |
100 | |
101 def test_shortest_path(self): | |
102 deg = [3, 2, 2, 1] | |
103 G = nx.generators.havel_hakimi_graph(deg) | |
104 cs1 = nxt.creation_sequence(deg, with_labels=True) | |
105 for n, m in [(3, 0), (0, 3), (0, 2), (0, 1), (1, 3), (3, 1), (1, 2), (2, 3)]: | |
106 assert nxt.shortest_path(cs1, n, m) == nx.shortest_path(G, n, m) | |
107 | |
108 spl = nxt.shortest_path_length(cs1, 3) | |
109 spl2 = nxt.shortest_path_length([t for v, t in cs1], 2) | |
110 assert spl == spl2 | |
111 | |
112 spld = {} | |
113 for j, pl in enumerate(spl): | |
114 n = cs1[j][0] | |
115 spld[n] = pl | |
116 assert spld == nx.single_source_shortest_path_length(G, 3) | |
117 | |
118 assert nxt.shortest_path(["d", "d", "d", "i", "d", "d"], 1, 2) == [1, 2] | |
119 assert nxt.shortest_path([3, 1, 2], 1, 2) == [1, 2] | |
120 assert pytest.raises(TypeError, nxt.shortest_path, [3.0, 1.0, 2.0], 1, 2) | |
121 assert pytest.raises(ValueError, nxt.shortest_path, [3, 1, 2], "a", 2) | |
122 assert pytest.raises(ValueError, nxt.shortest_path, [3, 1, 2], 1, "b") | |
123 assert nxt.shortest_path([3, 1, 2], 1, 1) == [1] | |
124 | |
125 def test_shortest_path_length(self): | |
126 assert nxt.shortest_path_length([3, 1, 2], 1) == [1, 0, 1, 2, 1, 1] | |
127 assert nxt.shortest_path_length(["d", "d", "d", "i", "d", "d"], 1) == [ | |
128 1, | |
129 0, | |
130 1, | |
131 2, | |
132 1, | |
133 1, | |
134 ] | |
135 assert nxt.shortest_path_length(("d", "d", "d", "i", "d", "d"), 1) == [ | |
136 1, | |
137 0, | |
138 1, | |
139 2, | |
140 1, | |
141 1, | |
142 ] | |
143 assert pytest.raises(TypeError, nxt.shortest_path, [3.0, 1.0, 2.0], 1) | |
144 | |
145 def random_threshold_sequence(self): | |
146 assert len(nxt.random_threshold_sequence(10, 0.5)) == 10 | |
147 assert nxt.random_threshold_sequence(10, 0.5, seed=42) == [ | |
148 "d", | |
149 "i", | |
150 "d", | |
151 "d", | |
152 "d", | |
153 "i", | |
154 "i", | |
155 "i", | |
156 "d", | |
157 "d", | |
158 ] | |
159 assert pytest.raises(ValueError, nxt.random_threshold_sequence, 10, 1.5) | |
160 | |
161 def test_right_d_threshold_sequence(self): | |
162 assert nxt.right_d_threshold_sequence(3, 2) == ["d", "i", "d"] | |
163 assert pytest.raises(ValueError, nxt.right_d_threshold_sequence, 2, 3) | |
164 | |
165 def test_left_d_threshold_sequence(self): | |
166 assert nxt.left_d_threshold_sequence(3, 2) == ["d", "i", "d"] | |
167 assert pytest.raises(ValueError, nxt.left_d_threshold_sequence, 2, 3) | |
168 | |
169 def test_weights_thresholds(self): | |
170 wseq = [3, 4, 3, 3, 5, 6, 5, 4, 5, 6] | |
171 cs = nxt.weights_to_creation_sequence(wseq, threshold=10) | |
172 wseq = nxt.creation_sequence_to_weights(cs) | |
173 cs2 = nxt.weights_to_creation_sequence(wseq) | |
174 assert cs == cs2 | |
175 | |
176 wseq = nxt.creation_sequence_to_weights(nxt.uncompact([3, 1, 2, 3, 3, 2, 3])) | |
177 assert wseq == [ | |
178 s * 0.125 for s in [4, 4, 4, 3, 5, 5, 2, 2, 2, 6, 6, 6, 1, 1, 7, 7, 7] | |
179 ] | |
180 | |
181 wseq = nxt.creation_sequence_to_weights([3, 1, 2, 3, 3, 2, 3]) | |
182 assert wseq == [ | |
183 s * 0.125 for s in [4, 4, 4, 3, 5, 5, 2, 2, 2, 6, 6, 6, 1, 1, 7, 7, 7] | |
184 ] | |
185 | |
186 wseq = nxt.creation_sequence_to_weights(list(enumerate("ddidiiidididi"))) | |
187 assert wseq == [s * 0.1 for s in [5, 5, 4, 6, 3, 3, 3, 7, 2, 8, 1, 9, 0]] | |
188 | |
189 wseq = nxt.creation_sequence_to_weights("ddidiiidididi") | |
190 assert wseq == [s * 0.1 for s in [5, 5, 4, 6, 3, 3, 3, 7, 2, 8, 1, 9, 0]] | |
191 | |
192 wseq = nxt.creation_sequence_to_weights("ddidiiidididid") | |
193 ws = [s / float(12) for s in [6, 6, 5, 7, 4, 4, 4, 8, 3, 9, 2, 10, 1, 11]] | |
194 assert sum([abs(c - d) for c, d in zip(wseq, ws)]) < 1e-14 | |
195 | |
196 def test_finding_routines(self): | |
197 G = nx.Graph({1: [2], 2: [3], 3: [4], 4: [5], 5: [6]}) | |
198 G.add_edge(2, 4) | |
199 G.add_edge(2, 5) | |
200 G.add_edge(2, 7) | |
201 G.add_edge(3, 6) | |
202 G.add_edge(4, 6) | |
203 | |
204 # Alternating 4 cycle | |
205 assert nxt.find_alternating_4_cycle(G) == [1, 2, 3, 6] | |
206 | |
207 # Threshold graph | |
208 TG = nxt.find_threshold_graph(G) | |
209 assert nxt.is_threshold_graph(TG) | |
210 assert sorted(TG.nodes()) == [1, 2, 3, 4, 5, 7] | |
211 | |
212 cs = nxt.creation_sequence(dict(TG.degree()), with_labels=True) | |
213 assert nxt.find_creation_sequence(G) == cs | |
214 | |
215 def test_fast_versions_properties_threshold_graphs(self): | |
216 cs = "ddiiddid" | |
217 G = nxt.threshold_graph(cs) | |
218 assert nxt.density("ddiiddid") == nx.density(G) | |
219 assert sorted(nxt.degree_sequence(cs)) == sorted(d for n, d in G.degree()) | |
220 | |
221 ts = nxt.triangle_sequence(cs) | |
222 assert ts == list(nx.triangles(G).values()) | |
223 assert sum(ts) // 3 == nxt.triangles(cs) | |
224 | |
225 c1 = nxt.cluster_sequence(cs) | |
226 c2 = list(nx.clustering(G).values()) | |
227 assert almost_equal(sum([abs(c - d) for c, d in zip(c1, c2)]), 0) | |
228 | |
229 b1 = nx.betweenness_centrality(G).values() | |
230 b2 = nxt.betweenness_sequence(cs) | |
231 assert sum([abs(c - d) for c, d in zip(b1, b2)]) < 1e-14 | |
232 | |
233 assert nxt.eigenvalues(cs) == [0, 1, 3, 3, 5, 7, 7, 8] | |
234 | |
235 # Degree Correlation | |
236 assert abs(nxt.degree_correlation(cs) + 0.593038821954) < 1e-12 | |
237 assert nxt.degree_correlation("diiiddi") == -0.8 | |
238 assert nxt.degree_correlation("did") == -1.0 | |
239 assert nxt.degree_correlation("ddd") == 1.0 | |
240 assert nxt.eigenvalues("dddiii") == [0, 0, 0, 0, 3, 3] | |
241 assert nxt.eigenvalues("dddiiid") == [0, 1, 1, 1, 4, 4, 7] | |
242 | |
243 def test_tg_creation_routines(self): | |
244 s = nxt.left_d_threshold_sequence(5, 7) | |
245 s = nxt.right_d_threshold_sequence(5, 7) | |
246 s1 = nxt.swap_d(s, 1.0, 1.0) | |
247 s1 = nxt.swap_d(s, 1.0, 1.0, seed=1) | |
248 | |
249 def test_eigenvectors(self): | |
250 np = pytest.importorskip("numpy") | |
251 eigenval = np.linalg.eigvals | |
252 scipy = pytest.importorskip("scipy") | |
253 | |
254 cs = "ddiiddid" | |
255 G = nxt.threshold_graph(cs) | |
256 (tgeval, tgevec) = nxt.eigenvectors(cs) | |
257 dot = np.dot | |
258 assert [abs(dot(lv, lv) - 1.0) < 1e-9 for lv in tgevec] == [True] * 8 | |
259 lapl = nx.laplacian_matrix(G) | |
260 | |
261 # tgev=[ dot(lv,dot(lapl,lv)) for lv in tgevec ] | |
262 # assert_true(sum([abs(c-d) for c,d in zip(tgev,tgeval)]) < 1e-9) | |
263 # tgev.sort() | |
264 # lev=list(eigenval(lapl)) | |
265 # lev.sort() | |
266 # assert_true(sum([abs(c-d) for c,d in zip(tgev,lev)]) < 1e-9) | |
267 | |
268 def test_create_using(self): | |
269 cs = "ddiiddid" | |
270 G = nxt.threshold_graph(cs) | |
271 assert pytest.raises( | |
272 nx.exception.NetworkXError, | |
273 nxt.threshold_graph, | |
274 cs, | |
275 create_using=nx.DiGraph(), | |
276 ) | |
277 MG = nxt.threshold_graph(cs, create_using=nx.MultiGraph()) | |
278 assert sorted(MG.edges()) == sorted(G.edges()) |