Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_cycles.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 import pytest | |
2 import networkx | |
3 import networkx as nx | |
4 | |
5 from networkx.algorithms import find_cycle | |
6 from networkx.algorithms import minimum_cycle_basis | |
7 | |
8 FORWARD = nx.algorithms.edgedfs.FORWARD | |
9 REVERSE = nx.algorithms.edgedfs.REVERSE | |
10 | |
11 | |
12 class TestCycles: | |
13 @classmethod | |
14 def setup_class(cls): | |
15 G = networkx.Graph() | |
16 nx.add_cycle(G, [0, 1, 2, 3]) | |
17 nx.add_cycle(G, [0, 3, 4, 5]) | |
18 nx.add_cycle(G, [0, 1, 6, 7, 8]) | |
19 G.add_edge(8, 9) | |
20 cls.G = G | |
21 | |
22 def is_cyclic_permutation(self, a, b): | |
23 n = len(a) | |
24 if len(b) != n: | |
25 return False | |
26 l = a + a | |
27 return any(l[i : i + n] == b for i in range(n)) | |
28 | |
29 def test_cycle_basis(self): | |
30 G = self.G | |
31 cy = networkx.cycle_basis(G, 0) | |
32 sort_cy = sorted(sorted(c) for c in cy) | |
33 assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]] | |
34 cy = networkx.cycle_basis(G, 1) | |
35 sort_cy = sorted(sorted(c) for c in cy) | |
36 assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]] | |
37 cy = networkx.cycle_basis(G, 9) | |
38 sort_cy = sorted(sorted(c) for c in cy) | |
39 assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]] | |
40 # test disconnected graphs | |
41 nx.add_cycle(G, "ABC") | |
42 cy = networkx.cycle_basis(G, 9) | |
43 sort_cy = sorted(sorted(c) for c in cy[:-1]) + [sorted(cy[-1])] | |
44 assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5], ["A", "B", "C"]] | |
45 | |
46 def test_cycle_basis2(self): | |
47 with pytest.raises(nx.NetworkXNotImplemented): | |
48 G = nx.DiGraph() | |
49 cy = networkx.cycle_basis(G, 0) | |
50 | |
51 def test_cycle_basis3(self): | |
52 with pytest.raises(nx.NetworkXNotImplemented): | |
53 G = nx.MultiGraph() | |
54 cy = networkx.cycle_basis(G, 0) | |
55 | |
56 def test_simple_cycles(self): | |
57 edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)] | |
58 G = nx.DiGraph(edges) | |
59 cc = sorted(nx.simple_cycles(G)) | |
60 ca = [[0], [0, 1, 2], [0, 2], [1, 2], [2]] | |
61 assert len(cc) == len(ca) | |
62 for c in cc: | |
63 assert any(self.is_cyclic_permutation(c, rc) for rc in ca) | |
64 | |
65 def test_simple_cycles_graph(self): | |
66 with pytest.raises(nx.NetworkXNotImplemented): | |
67 G = nx.Graph() | |
68 c = sorted(nx.simple_cycles(G)) | |
69 | |
70 def test_unsortable(self): | |
71 # TODO What does this test do? das 6/2013 | |
72 G = nx.DiGraph() | |
73 nx.add_cycle(G, ["a", 1]) | |
74 c = list(nx.simple_cycles(G)) | |
75 | |
76 def test_simple_cycles_small(self): | |
77 G = nx.DiGraph() | |
78 nx.add_cycle(G, [1, 2, 3]) | |
79 c = sorted(nx.simple_cycles(G)) | |
80 assert len(c) == 1 | |
81 assert self.is_cyclic_permutation(c[0], [1, 2, 3]) | |
82 nx.add_cycle(G, [10, 20, 30]) | |
83 cc = sorted(nx.simple_cycles(G)) | |
84 assert len(cc) == 2 | |
85 ca = [[1, 2, 3], [10, 20, 30]] | |
86 for c in cc: | |
87 assert any(self.is_cyclic_permutation(c, rc) for rc in ca) | |
88 | |
89 def test_simple_cycles_empty(self): | |
90 G = nx.DiGraph() | |
91 assert list(nx.simple_cycles(G)) == [] | |
92 | |
93 def test_complete_directed_graph(self): | |
94 # see table 2 in Johnson's paper | |
95 ncircuits = [1, 5, 20, 84, 409, 2365, 16064] | |
96 for n, c in zip(range(2, 9), ncircuits): | |
97 G = nx.DiGraph(nx.complete_graph(n)) | |
98 assert len(list(nx.simple_cycles(G))) == c | |
99 | |
100 def worst_case_graph(self, k): | |
101 # see figure 1 in Johnson's paper | |
102 # this graph has exactly 3k simple cycles | |
103 G = nx.DiGraph() | |
104 for n in range(2, k + 2): | |
105 G.add_edge(1, n) | |
106 G.add_edge(n, k + 2) | |
107 G.add_edge(2 * k + 1, 1) | |
108 for n in range(k + 2, 2 * k + 2): | |
109 G.add_edge(n, 2 * k + 2) | |
110 G.add_edge(n, n + 1) | |
111 G.add_edge(2 * k + 3, k + 2) | |
112 for n in range(2 * k + 3, 3 * k + 3): | |
113 G.add_edge(2 * k + 2, n) | |
114 G.add_edge(n, 3 * k + 3) | |
115 G.add_edge(3 * k + 3, 2 * k + 2) | |
116 return G | |
117 | |
118 def test_worst_case_graph(self): | |
119 # see figure 1 in Johnson's paper | |
120 for k in range(3, 10): | |
121 G = self.worst_case_graph(k) | |
122 l = len(list(nx.simple_cycles(G))) | |
123 assert l == 3 * k | |
124 | |
125 def test_recursive_simple_and_not(self): | |
126 for k in range(2, 10): | |
127 G = self.worst_case_graph(k) | |
128 cc = sorted(nx.simple_cycles(G)) | |
129 rcc = sorted(nx.recursive_simple_cycles(G)) | |
130 assert len(cc) == len(rcc) | |
131 for c in cc: | |
132 assert any(self.is_cyclic_permutation(c, r) for r in rcc) | |
133 for rc in rcc: | |
134 assert any(self.is_cyclic_permutation(rc, c) for c in cc) | |
135 | |
136 def test_simple_graph_with_reported_bug(self): | |
137 G = nx.DiGraph() | |
138 edges = [ | |
139 (0, 2), | |
140 (0, 3), | |
141 (1, 0), | |
142 (1, 3), | |
143 (2, 1), | |
144 (2, 4), | |
145 (3, 2), | |
146 (3, 4), | |
147 (4, 0), | |
148 (4, 1), | |
149 (4, 5), | |
150 (5, 0), | |
151 (5, 1), | |
152 (5, 2), | |
153 (5, 3), | |
154 ] | |
155 G.add_edges_from(edges) | |
156 cc = sorted(nx.simple_cycles(G)) | |
157 assert len(cc) == 26 | |
158 rcc = sorted(nx.recursive_simple_cycles(G)) | |
159 assert len(cc) == len(rcc) | |
160 for c in cc: | |
161 assert any(self.is_cyclic_permutation(c, rc) for rc in rcc) | |
162 for rc in rcc: | |
163 assert any(self.is_cyclic_permutation(rc, c) for c in cc) | |
164 | |
165 | |
166 # These tests might fail with hash randomization since they depend on | |
167 # edge_dfs. For more information, see the comments in: | |
168 # networkx/algorithms/traversal/tests/test_edgedfs.py | |
169 | |
170 | |
171 class TestFindCycle: | |
172 @classmethod | |
173 def setup_class(cls): | |
174 cls.nodes = [0, 1, 2, 3] | |
175 cls.edges = [(-1, 0), (0, 1), (1, 0), (1, 0), (2, 1), (3, 1)] | |
176 | |
177 def test_graph_nocycle(self): | |
178 G = nx.Graph(self.edges) | |
179 pytest.raises(nx.exception.NetworkXNoCycle, find_cycle, G, self.nodes) | |
180 | |
181 def test_graph_cycle(self): | |
182 G = nx.Graph(self.edges) | |
183 G.add_edge(2, 0) | |
184 x = list(find_cycle(G, self.nodes)) | |
185 x_ = [(0, 1), (1, 2), (2, 0)] | |
186 assert x == x_ | |
187 | |
188 def test_graph_orientation_none(self): | |
189 G = nx.Graph(self.edges) | |
190 G.add_edge(2, 0) | |
191 x = list(find_cycle(G, self.nodes, orientation=None)) | |
192 x_ = [(0, 1), (1, 2), (2, 0)] | |
193 assert x == x_ | |
194 | |
195 def test_graph_orientation_original(self): | |
196 G = nx.Graph(self.edges) | |
197 G.add_edge(2, 0) | |
198 x = list(find_cycle(G, self.nodes, orientation="original")) | |
199 x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 0, FORWARD)] | |
200 assert x == x_ | |
201 | |
202 def test_digraph(self): | |
203 G = nx.DiGraph(self.edges) | |
204 x = list(find_cycle(G, self.nodes)) | |
205 x_ = [(0, 1), (1, 0)] | |
206 assert x == x_ | |
207 | |
208 def test_digraph_orientation_none(self): | |
209 G = nx.DiGraph(self.edges) | |
210 x = list(find_cycle(G, self.nodes, orientation=None)) | |
211 x_ = [(0, 1), (1, 0)] | |
212 assert x == x_ | |
213 | |
214 def test_digraph_orientation_original(self): | |
215 G = nx.DiGraph(self.edges) | |
216 x = list(find_cycle(G, self.nodes, orientation="original")) | |
217 x_ = [(0, 1, FORWARD), (1, 0, FORWARD)] | |
218 assert x == x_ | |
219 | |
220 def test_multigraph(self): | |
221 G = nx.MultiGraph(self.edges) | |
222 x = list(find_cycle(G, self.nodes)) | |
223 x_ = [(0, 1, 0), (1, 0, 1)] # or (1, 0, 2) | |
224 # Hash randomization...could be any edge. | |
225 assert x[0] == x_[0] | |
226 assert x[1][:2] == x_[1][:2] | |
227 | |
228 def test_multidigraph(self): | |
229 G = nx.MultiDiGraph(self.edges) | |
230 x = list(find_cycle(G, self.nodes)) | |
231 x_ = [(0, 1, 0), (1, 0, 0)] # (1, 0, 1) | |
232 assert x[0] == x_[0] | |
233 assert x[1][:2] == x_[1][:2] | |
234 | |
235 def test_digraph_ignore(self): | |
236 G = nx.DiGraph(self.edges) | |
237 x = list(find_cycle(G, self.nodes, orientation="ignore")) | |
238 x_ = [(0, 1, FORWARD), (1, 0, FORWARD)] | |
239 assert x == x_ | |
240 | |
241 def test_digraph_reverse(self): | |
242 G = nx.DiGraph(self.edges) | |
243 x = list(find_cycle(G, self.nodes, orientation="reverse")) | |
244 x_ = [(1, 0, REVERSE), (0, 1, REVERSE)] | |
245 assert x == x_ | |
246 | |
247 def test_multidigraph_ignore(self): | |
248 G = nx.MultiDiGraph(self.edges) | |
249 x = list(find_cycle(G, self.nodes, orientation="ignore")) | |
250 x_ = [(0, 1, 0, FORWARD), (1, 0, 0, FORWARD)] # or (1, 0, 1, 1) | |
251 assert x[0] == x_[0] | |
252 assert x[1][:2] == x_[1][:2] | |
253 assert x[1][3] == x_[1][3] | |
254 | |
255 def test_multidigraph_ignore2(self): | |
256 # Loop traversed an edge while ignoring its orientation. | |
257 G = nx.MultiDiGraph([(0, 1), (1, 2), (1, 2)]) | |
258 x = list(find_cycle(G, [0, 1, 2], orientation="ignore")) | |
259 x_ = [(1, 2, 0, FORWARD), (1, 2, 1, REVERSE)] | |
260 assert x == x_ | |
261 | |
262 def test_multidigraph_original(self): | |
263 # Node 2 doesn't need to be searched again from visited from 4. | |
264 # The goal here is to cover the case when 2 to be researched from 4, | |
265 # when 4 is visited from the first time (so we must make sure that 4 | |
266 # is not visited from 2, and hence, we respect the edge orientation). | |
267 G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 3), (4, 2)]) | |
268 pytest.raises( | |
269 nx.exception.NetworkXNoCycle, | |
270 find_cycle, | |
271 G, | |
272 [0, 1, 2, 3, 4], | |
273 orientation="original", | |
274 ) | |
275 | |
276 def test_dag(self): | |
277 G = nx.DiGraph([(0, 1), (0, 2), (1, 2)]) | |
278 pytest.raises( | |
279 nx.exception.NetworkXNoCycle, find_cycle, G, orientation="original" | |
280 ) | |
281 x = list(find_cycle(G, orientation="ignore")) | |
282 assert x == [(0, 1, FORWARD), (1, 2, FORWARD), (0, 2, REVERSE)] | |
283 | |
284 def test_prev_explored(self): | |
285 # https://github.com/networkx/networkx/issues/2323 | |
286 | |
287 G = nx.DiGraph() | |
288 G.add_edges_from([(1, 0), (2, 0), (1, 2), (2, 1)]) | |
289 pytest.raises(nx.NetworkXNoCycle, find_cycle, G, source=0) | |
290 x = list(nx.find_cycle(G, 1)) | |
291 x_ = [(1, 2), (2, 1)] | |
292 assert x == x_ | |
293 | |
294 x = list(nx.find_cycle(G, 2)) | |
295 x_ = [(2, 1), (1, 2)] | |
296 assert x == x_ | |
297 | |
298 x = list(nx.find_cycle(G)) | |
299 x_ = [(1, 2), (2, 1)] | |
300 assert x == x_ | |
301 | |
302 def test_no_cycle(self): | |
303 # https://github.com/networkx/networkx/issues/2439 | |
304 | |
305 G = nx.DiGraph() | |
306 G.add_edges_from([(1, 2), (2, 0), (3, 1), (3, 2)]) | |
307 pytest.raises(nx.NetworkXNoCycle, find_cycle, G, source=0) | |
308 pytest.raises(nx.NetworkXNoCycle, find_cycle, G) | |
309 | |
310 | |
311 def assert_basis_equal(a, b): | |
312 assert sorted(a) == sorted(b) | |
313 | |
314 | |
315 class TestMinimumCycles: | |
316 @classmethod | |
317 def setup_class(cls): | |
318 T = nx.Graph() | |
319 nx.add_cycle(T, [1, 2, 3, 4], weight=1) | |
320 T.add_edge(2, 4, weight=5) | |
321 cls.diamond_graph = T | |
322 | |
323 def test_unweighted_diamond(self): | |
324 mcb = minimum_cycle_basis(self.diamond_graph) | |
325 assert_basis_equal([sorted(c) for c in mcb], [[1, 2, 4], [2, 3, 4]]) | |
326 | |
327 def test_weighted_diamond(self): | |
328 mcb = minimum_cycle_basis(self.diamond_graph, weight="weight") | |
329 assert_basis_equal([sorted(c) for c in mcb], [[1, 2, 4], [1, 2, 3, 4]]) | |
330 | |
331 def test_dimensionality(self): | |
332 # checks |MCB|=|E|-|V|+|NC| | |
333 ntrial = 10 | |
334 for _ in range(ntrial): | |
335 rg = nx.erdos_renyi_graph(10, 0.3) | |
336 nnodes = rg.number_of_nodes() | |
337 nedges = rg.number_of_edges() | |
338 ncomp = nx.number_connected_components(rg) | |
339 | |
340 dim_mcb = len(minimum_cycle_basis(rg)) | |
341 assert dim_mcb == nedges - nnodes + ncomp | |
342 | |
343 def test_complete_graph(self): | |
344 cg = nx.complete_graph(5) | |
345 mcb = minimum_cycle_basis(cg) | |
346 assert all([len(cycle) == 3 for cycle in mcb]) | |
347 | |
348 def test_tree_graph(self): | |
349 tg = nx.balanced_tree(3, 3) | |
350 assert not minimum_cycle_basis(tg) |