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)