Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_dag.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 itertools import combinations, permutations | |
2 | |
3 import pytest | |
4 | |
5 import networkx as nx | |
6 from networkx.testing.utils import assert_edges_equal | |
7 from networkx.utils import consume | |
8 from networkx.utils import pairwise | |
9 | |
10 | |
11 class TestDagLongestPath: | |
12 """Unit tests computing the longest path in a directed acyclic graph.""" | |
13 | |
14 def test_empty(self): | |
15 G = nx.DiGraph() | |
16 assert nx.dag_longest_path(G) == [] | |
17 | |
18 def test_unweighted1(self): | |
19 edges = [(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (3, 7)] | |
20 G = nx.DiGraph(edges) | |
21 assert nx.dag_longest_path(G) == [1, 2, 3, 5, 6] | |
22 | |
23 def test_unweighted2(self): | |
24 edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 3), (1, 5), (3, 5)] | |
25 G = nx.DiGraph(edges) | |
26 assert nx.dag_longest_path(G) == [1, 2, 3, 4, 5] | |
27 | |
28 def test_weighted(self): | |
29 G = nx.DiGraph() | |
30 edges = [(1, 2, -5), (2, 3, 1), (3, 4, 1), (4, 5, 0), (3, 5, 4), (1, 6, 2)] | |
31 G.add_weighted_edges_from(edges) | |
32 assert nx.dag_longest_path(G) == [2, 3, 5] | |
33 | |
34 def test_undirected_not_implemented(self): | |
35 G = nx.Graph() | |
36 pytest.raises(nx.NetworkXNotImplemented, nx.dag_longest_path, G) | |
37 | |
38 def test_unorderable_nodes(self): | |
39 """Tests that computing the longest path does not depend on | |
40 nodes being orderable. | |
41 | |
42 For more information, see issue #1989. | |
43 | |
44 """ | |
45 # Create the directed path graph on four nodes in a diamond shape, | |
46 # with nodes represented as (unorderable) Python objects. | |
47 nodes = [object() for n in range(4)] | |
48 G = nx.DiGraph() | |
49 G.add_edge(nodes[0], nodes[1]) | |
50 G.add_edge(nodes[0], nodes[2]) | |
51 G.add_edge(nodes[2], nodes[3]) | |
52 G.add_edge(nodes[1], nodes[3]) | |
53 | |
54 # this will raise NotImplementedError when nodes need to be ordered | |
55 nx.dag_longest_path(G) | |
56 | |
57 | |
58 class TestDagLongestPathLength: | |
59 """Unit tests for computing the length of a longest path in a | |
60 directed acyclic graph. | |
61 | |
62 """ | |
63 | |
64 def test_unweighted(self): | |
65 edges = [(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (5, 7)] | |
66 G = nx.DiGraph(edges) | |
67 assert nx.dag_longest_path_length(G) == 4 | |
68 | |
69 edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 3), (1, 5), (3, 5)] | |
70 G = nx.DiGraph(edges) | |
71 assert nx.dag_longest_path_length(G) == 4 | |
72 | |
73 # test degenerate graphs | |
74 G = nx.DiGraph() | |
75 G.add_node(1) | |
76 assert nx.dag_longest_path_length(G) == 0 | |
77 | |
78 def test_undirected_not_implemented(self): | |
79 G = nx.Graph() | |
80 pytest.raises(nx.NetworkXNotImplemented, nx.dag_longest_path_length, G) | |
81 | |
82 def test_weighted(self): | |
83 edges = [(1, 2, -5), (2, 3, 1), (3, 4, 1), (4, 5, 0), (3, 5, 4), (1, 6, 2)] | |
84 G = nx.DiGraph() | |
85 G.add_weighted_edges_from(edges) | |
86 assert nx.dag_longest_path_length(G) == 5 | |
87 | |
88 | |
89 class TestDAG: | |
90 @classmethod | |
91 def setup_class(cls): | |
92 pass | |
93 | |
94 def test_topological_sort1(self): | |
95 DG = nx.DiGraph([(1, 2), (1, 3), (2, 3)]) | |
96 | |
97 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]: | |
98 assert tuple(algorithm(DG)) == (1, 2, 3) | |
99 | |
100 DG.add_edge(3, 2) | |
101 | |
102 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]: | |
103 pytest.raises(nx.NetworkXUnfeasible, consume, algorithm(DG)) | |
104 | |
105 DG.remove_edge(2, 3) | |
106 | |
107 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]: | |
108 assert tuple(algorithm(DG)) == (1, 3, 2) | |
109 | |
110 DG.remove_edge(3, 2) | |
111 | |
112 assert tuple(nx.topological_sort(DG)) in {(1, 2, 3), (1, 3, 2)} | |
113 assert tuple(nx.lexicographical_topological_sort(DG)) == (1, 2, 3) | |
114 | |
115 def test_is_directed_acyclic_graph(self): | |
116 G = nx.generators.complete_graph(2) | |
117 assert not nx.is_directed_acyclic_graph(G) | |
118 assert not nx.is_directed_acyclic_graph(G.to_directed()) | |
119 assert not nx.is_directed_acyclic_graph(nx.Graph([(3, 4), (4, 5)])) | |
120 assert nx.is_directed_acyclic_graph(nx.DiGraph([(3, 4), (4, 5)])) | |
121 | |
122 def test_topological_sort2(self): | |
123 DG = nx.DiGraph( | |
124 { | |
125 1: [2], | |
126 2: [3], | |
127 3: [4], | |
128 4: [5], | |
129 5: [1], | |
130 11: [12], | |
131 12: [13], | |
132 13: [14], | |
133 14: [15], | |
134 } | |
135 ) | |
136 pytest.raises(nx.NetworkXUnfeasible, consume, nx.topological_sort(DG)) | |
137 | |
138 assert not nx.is_directed_acyclic_graph(DG) | |
139 | |
140 DG.remove_edge(1, 2) | |
141 consume(nx.topological_sort(DG)) | |
142 assert nx.is_directed_acyclic_graph(DG) | |
143 | |
144 def test_topological_sort3(self): | |
145 DG = nx.DiGraph() | |
146 DG.add_edges_from([(1, i) for i in range(2, 5)]) | |
147 DG.add_edges_from([(2, i) for i in range(5, 9)]) | |
148 DG.add_edges_from([(6, i) for i in range(9, 12)]) | |
149 DG.add_edges_from([(4, i) for i in range(12, 15)]) | |
150 | |
151 def validate(order): | |
152 assert isinstance(order, list) | |
153 assert set(order) == set(DG) | |
154 for u, v in combinations(order, 2): | |
155 assert not nx.has_path(DG, v, u) | |
156 | |
157 validate(list(nx.topological_sort(DG))) | |
158 | |
159 DG.add_edge(14, 1) | |
160 pytest.raises(nx.NetworkXUnfeasible, consume, nx.topological_sort(DG)) | |
161 | |
162 def test_topological_sort4(self): | |
163 G = nx.Graph() | |
164 G.add_edge(1, 2) | |
165 # Only directed graphs can be topologically sorted. | |
166 pytest.raises(nx.NetworkXError, consume, nx.topological_sort(G)) | |
167 | |
168 def test_topological_sort5(self): | |
169 G = nx.DiGraph() | |
170 G.add_edge(0, 1) | |
171 assert list(nx.topological_sort(G)) == [0, 1] | |
172 | |
173 def test_topological_sort6(self): | |
174 for algorithm in [nx.topological_sort, nx.lexicographical_topological_sort]: | |
175 | |
176 def runtime_error(): | |
177 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) | |
178 first = True | |
179 for x in algorithm(DG): | |
180 if first: | |
181 first = False | |
182 DG.add_edge(5 - x, 5) | |
183 | |
184 def unfeasible_error(): | |
185 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) | |
186 first = True | |
187 for x in algorithm(DG): | |
188 if first: | |
189 first = False | |
190 DG.remove_node(4) | |
191 | |
192 def runtime_error2(): | |
193 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) | |
194 first = True | |
195 for x in algorithm(DG): | |
196 if first: | |
197 first = False | |
198 DG.remove_node(2) | |
199 | |
200 pytest.raises(RuntimeError, runtime_error) | |
201 pytest.raises(RuntimeError, runtime_error2) | |
202 pytest.raises(nx.NetworkXUnfeasible, unfeasible_error) | |
203 | |
204 def test_all_topological_sorts_1(self): | |
205 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 5)]) | |
206 assert list(nx.all_topological_sorts(DG)) == [[1, 2, 3, 4, 5]] | |
207 | |
208 def test_all_topological_sorts_2(self): | |
209 DG = nx.DiGraph([(1, 3), (2, 1), (2, 4), (4, 3), (4, 5)]) | |
210 assert sorted(nx.all_topological_sorts(DG)) == [ | |
211 [2, 1, 4, 3, 5], | |
212 [2, 1, 4, 5, 3], | |
213 [2, 4, 1, 3, 5], | |
214 [2, 4, 1, 5, 3], | |
215 [2, 4, 5, 1, 3], | |
216 ] | |
217 | |
218 def test_all_topological_sorts_3(self): | |
219 def unfeasible(): | |
220 DG = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 2), (4, 5)]) | |
221 # convert to list to execute generator | |
222 list(nx.all_topological_sorts(DG)) | |
223 | |
224 def not_implemented(): | |
225 G = nx.Graph([(1, 2), (2, 3)]) | |
226 # convert to list to execute generator | |
227 list(nx.all_topological_sorts(G)) | |
228 | |
229 def not_implemted_2(): | |
230 G = nx.MultiGraph([(1, 2), (1, 2), (2, 3)]) | |
231 list(nx.all_topological_sorts(G)) | |
232 | |
233 pytest.raises(nx.NetworkXUnfeasible, unfeasible) | |
234 pytest.raises(nx.NetworkXNotImplemented, not_implemented) | |
235 pytest.raises(nx.NetworkXNotImplemented, not_implemted_2) | |
236 | |
237 def test_all_topological_sorts_4(self): | |
238 DG = nx.DiGraph() | |
239 for i in range(7): | |
240 DG.add_node(i) | |
241 assert sorted(map(list, permutations(DG.nodes))) == sorted( | |
242 nx.all_topological_sorts(DG) | |
243 ) | |
244 | |
245 def test_all_topological_sorts_multigraph_1(self): | |
246 DG = nx.MultiDiGraph([(1, 2), (1, 2), (2, 3), (3, 4), (3, 5), (3, 5), (3, 5)]) | |
247 assert sorted(nx.all_topological_sorts(DG)) == sorted( | |
248 [[1, 2, 3, 4, 5], [1, 2, 3, 5, 4]] | |
249 ) | |
250 | |
251 def test_all_topological_sorts_multigraph_2(self): | |
252 N = 9 | |
253 edges = [] | |
254 for i in range(1, N): | |
255 edges.extend([(i, i + 1)] * i) | |
256 DG = nx.MultiDiGraph(edges) | |
257 assert list(nx.all_topological_sorts(DG)) == [list(range(1, N + 1))] | |
258 | |
259 def test_ancestors(self): | |
260 G = nx.DiGraph() | |
261 ancestors = nx.algorithms.dag.ancestors | |
262 G.add_edges_from([(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)]) | |
263 assert ancestors(G, 6) == {1, 2, 4, 5} | |
264 assert ancestors(G, 3) == {1, 4} | |
265 assert ancestors(G, 1) == set() | |
266 pytest.raises(nx.NetworkXError, ancestors, G, 8) | |
267 | |
268 def test_descendants(self): | |
269 G = nx.DiGraph() | |
270 descendants = nx.algorithms.dag.descendants | |
271 G.add_edges_from([(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)]) | |
272 assert descendants(G, 1) == {2, 3, 6} | |
273 assert descendants(G, 4) == {2, 3, 5, 6} | |
274 assert descendants(G, 3) == set() | |
275 pytest.raises(nx.NetworkXError, descendants, G, 8) | |
276 | |
277 def test_transitive_closure(self): | |
278 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) | |
279 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] | |
280 assert_edges_equal(nx.transitive_closure(G).edges(), solution) | |
281 G = nx.DiGraph([(1, 2), (2, 3), (2, 4)]) | |
282 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)] | |
283 assert_edges_equal(nx.transitive_closure(G).edges(), solution) | |
284 G = nx.DiGraph([(1, 2), (2, 3), (3, 1)]) | |
285 solution = [(1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1)] | |
286 soln = sorted(solution + [(n, n) for n in G]) | |
287 assert_edges_equal(sorted(nx.transitive_closure(G).edges()), soln) | |
288 G = nx.Graph([(1, 2), (2, 3), (3, 4)]) | |
289 pytest.raises(nx.NetworkXNotImplemented, nx.transitive_closure, G) | |
290 | |
291 # test if edge data is copied | |
292 G = nx.DiGraph([(1, 2, {"a": 3}), (2, 3, {"b": 0}), (3, 4)]) | |
293 H = nx.transitive_closure(G) | |
294 for u, v in G.edges(): | |
295 assert G.get_edge_data(u, v) == H.get_edge_data(u, v) | |
296 | |
297 k = 10 | |
298 G = nx.DiGraph((i, i + 1, {"f": "b", "weight": i}) for i in range(k)) | |
299 H = nx.transitive_closure(G) | |
300 for u, v in G.edges(): | |
301 assert G.get_edge_data(u, v) == H.get_edge_data(u, v) | |
302 | |
303 def test_reflexive_transitive_closure(self): | |
304 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) | |
305 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] | |
306 soln = sorted(solution + [(n, n) for n in G]) | |
307 assert_edges_equal(nx.transitive_closure(G).edges(), solution) | |
308 assert_edges_equal(nx.transitive_closure(G, False).edges(), solution) | |
309 assert_edges_equal(nx.transitive_closure(G, True).edges(), soln) | |
310 assert_edges_equal(nx.transitive_closure(G, None).edges(), solution) | |
311 | |
312 G = nx.DiGraph([(1, 2), (2, 3), (2, 4)]) | |
313 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)] | |
314 soln = sorted(solution + [(n, n) for n in G]) | |
315 assert_edges_equal(nx.transitive_closure(G).edges(), solution) | |
316 assert_edges_equal(nx.transitive_closure(G, False).edges(), solution) | |
317 assert_edges_equal(nx.transitive_closure(G, True).edges(), soln) | |
318 assert_edges_equal(nx.transitive_closure(G, None).edges(), solution) | |
319 | |
320 G = nx.DiGraph([(1, 2), (2, 3), (3, 1)]) | |
321 solution = sorted([(1, 2), (2, 1), (2, 3), (3, 2), (1, 3), (3, 1)]) | |
322 soln = sorted(solution + [(n, n) for n in G]) | |
323 assert_edges_equal(sorted(nx.transitive_closure(G).edges()), soln) | |
324 assert_edges_equal(sorted(nx.transitive_closure(G, False).edges()), soln) | |
325 assert_edges_equal(sorted(nx.transitive_closure(G, None).edges()), solution) | |
326 assert_edges_equal(sorted(nx.transitive_closure(G, True).edges()), soln) | |
327 | |
328 def test_transitive_closure_dag(self): | |
329 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) | |
330 transitive_closure = nx.algorithms.dag.transitive_closure_dag | |
331 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] | |
332 assert_edges_equal(transitive_closure(G).edges(), solution) | |
333 G = nx.DiGraph([(1, 2), (2, 3), (2, 4)]) | |
334 solution = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)] | |
335 assert_edges_equal(transitive_closure(G).edges(), solution) | |
336 G = nx.Graph([(1, 2), (2, 3), (3, 4)]) | |
337 pytest.raises(nx.NetworkXNotImplemented, transitive_closure, G) | |
338 | |
339 # test if edge data is copied | |
340 G = nx.DiGraph([(1, 2, {"a": 3}), (2, 3, {"b": 0}), (3, 4)]) | |
341 H = transitive_closure(G) | |
342 for u, v in G.edges(): | |
343 assert G.get_edge_data(u, v) == H.get_edge_data(u, v) | |
344 | |
345 k = 10 | |
346 G = nx.DiGraph((i, i + 1, {"foo": "bar", "weight": i}) for i in range(k)) | |
347 H = transitive_closure(G) | |
348 for u, v in G.edges(): | |
349 assert G.get_edge_data(u, v) == H.get_edge_data(u, v) | |
350 | |
351 def test_transitive_reduction(self): | |
352 G = nx.DiGraph([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]) | |
353 transitive_reduction = nx.algorithms.dag.transitive_reduction | |
354 solution = [(1, 2), (2, 3), (3, 4)] | |
355 assert_edges_equal(transitive_reduction(G).edges(), solution) | |
356 G = nx.DiGraph([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)]) | |
357 transitive_reduction = nx.algorithms.dag.transitive_reduction | |
358 solution = [(1, 2), (2, 3), (2, 4)] | |
359 assert_edges_equal(transitive_reduction(G).edges(), solution) | |
360 G = nx.Graph([(1, 2), (2, 3), (3, 4)]) | |
361 pytest.raises(nx.NetworkXNotImplemented, transitive_reduction, G) | |
362 | |
363 def _check_antichains(self, solution, result): | |
364 sol = [frozenset(a) for a in solution] | |
365 res = [frozenset(a) for a in result] | |
366 assert set(sol) == set(res) | |
367 | |
368 def test_antichains(self): | |
369 antichains = nx.algorithms.dag.antichains | |
370 G = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) | |
371 solution = [[], [4], [3], [2], [1]] | |
372 self._check_antichains(list(antichains(G)), solution) | |
373 G = nx.DiGraph([(1, 2), (2, 3), (2, 4), (3, 5), (5, 6), (5, 7)]) | |
374 solution = [ | |
375 [], | |
376 [4], | |
377 [7], | |
378 [7, 4], | |
379 [6], | |
380 [6, 4], | |
381 [6, 7], | |
382 [6, 7, 4], | |
383 [5], | |
384 [5, 4], | |
385 [3], | |
386 [3, 4], | |
387 [2], | |
388 [1], | |
389 ] | |
390 self._check_antichains(list(antichains(G)), solution) | |
391 G = nx.DiGraph([(1, 2), (1, 3), (3, 4), (3, 5), (5, 6)]) | |
392 solution = [ | |
393 [], | |
394 [6], | |
395 [5], | |
396 [4], | |
397 [4, 6], | |
398 [4, 5], | |
399 [3], | |
400 [2], | |
401 [2, 6], | |
402 [2, 5], | |
403 [2, 4], | |
404 [2, 4, 6], | |
405 [2, 4, 5], | |
406 [2, 3], | |
407 [1], | |
408 ] | |
409 self._check_antichains(list(antichains(G)), solution) | |
410 G = nx.DiGraph({0: [1, 2], 1: [4], 2: [3], 3: [4]}) | |
411 solution = [[], [4], [3], [2], [1], [1, 3], [1, 2], [0]] | |
412 self._check_antichains(list(antichains(G)), solution) | |
413 G = nx.DiGraph() | |
414 self._check_antichains(list(antichains(G)), [[]]) | |
415 G = nx.DiGraph() | |
416 G.add_nodes_from([0, 1, 2]) | |
417 solution = [[], [0], [1], [1, 0], [2], [2, 0], [2, 1], [2, 1, 0]] | |
418 self._check_antichains(list(antichains(G)), solution) | |
419 | |
420 def f(x): | |
421 return list(antichains(x)) | |
422 | |
423 G = nx.Graph([(1, 2), (2, 3), (3, 4)]) | |
424 pytest.raises(nx.NetworkXNotImplemented, f, G) | |
425 G = nx.DiGraph([(1, 2), (2, 3), (3, 1)]) | |
426 pytest.raises(nx.NetworkXUnfeasible, f, G) | |
427 | |
428 def test_lexicographical_topological_sort(self): | |
429 G = nx.DiGraph([(1, 2), (2, 3), (1, 4), (1, 5), (2, 6)]) | |
430 assert list(nx.lexicographical_topological_sort(G)) == [1, 2, 3, 4, 5, 6] | |
431 assert list(nx.lexicographical_topological_sort(G, key=lambda x: x)) == [ | |
432 1, | |
433 2, | |
434 3, | |
435 4, | |
436 5, | |
437 6, | |
438 ] | |
439 assert list(nx.lexicographical_topological_sort(G, key=lambda x: -x)) == [ | |
440 1, | |
441 5, | |
442 4, | |
443 2, | |
444 6, | |
445 3, | |
446 ] | |
447 | |
448 def test_lexicographical_topological_sort2(self): | |
449 """ | |
450 Check the case of two or more nodes with same key value. | |
451 Want to avoid exception raised due to comparing nodes directly. | |
452 See Issue #3493 | |
453 """ | |
454 | |
455 class Test_Node: | |
456 def __init__(self, n): | |
457 self.label = n | |
458 self.priority = 1 | |
459 | |
460 def __repr__(self): | |
461 return f"Node({self.label})" | |
462 | |
463 def sorting_key(node): | |
464 return node.priority | |
465 | |
466 test_nodes = [Test_Node(n) for n in range(4)] | |
467 G = nx.DiGraph() | |
468 edges = [(0, 1), (0, 2), (0, 3), (2, 3)] | |
469 G.add_edges_from((test_nodes[a], test_nodes[b]) for a, b in edges) | |
470 | |
471 sorting = list(nx.lexicographical_topological_sort(G, key=sorting_key)) | |
472 assert sorting == test_nodes | |
473 | |
474 | |
475 def test_is_aperiodic_cycle(): | |
476 G = nx.DiGraph() | |
477 nx.add_cycle(G, [1, 2, 3, 4]) | |
478 assert not nx.is_aperiodic(G) | |
479 | |
480 | |
481 def test_is_aperiodic_cycle2(): | |
482 G = nx.DiGraph() | |
483 nx.add_cycle(G, [1, 2, 3, 4]) | |
484 nx.add_cycle(G, [3, 4, 5, 6, 7]) | |
485 assert nx.is_aperiodic(G) | |
486 | |
487 | |
488 def test_is_aperiodic_cycle3(): | |
489 G = nx.DiGraph() | |
490 nx.add_cycle(G, [1, 2, 3, 4]) | |
491 nx.add_cycle(G, [3, 4, 5, 6]) | |
492 assert not nx.is_aperiodic(G) | |
493 | |
494 | |
495 def test_is_aperiodic_cycle4(): | |
496 G = nx.DiGraph() | |
497 nx.add_cycle(G, [1, 2, 3, 4]) | |
498 G.add_edge(1, 3) | |
499 assert nx.is_aperiodic(G) | |
500 | |
501 | |
502 def test_is_aperiodic_selfloop(): | |
503 G = nx.DiGraph() | |
504 nx.add_cycle(G, [1, 2, 3, 4]) | |
505 G.add_edge(1, 1) | |
506 assert nx.is_aperiodic(G) | |
507 | |
508 | |
509 def test_is_aperiodic_raise(): | |
510 G = nx.Graph() | |
511 pytest.raises(nx.NetworkXError, nx.is_aperiodic, G) | |
512 | |
513 | |
514 def test_is_aperiodic_bipartite(): | |
515 # Bipartite graph | |
516 G = nx.DiGraph(nx.davis_southern_women_graph()) | |
517 assert not nx.is_aperiodic(G) | |
518 | |
519 | |
520 def test_is_aperiodic_rary_tree(): | |
521 G = nx.full_rary_tree(3, 27, create_using=nx.DiGraph()) | |
522 assert not nx.is_aperiodic(G) | |
523 | |
524 | |
525 def test_is_aperiodic_disconnected(): | |
526 # disconnected graph | |
527 G = nx.DiGraph() | |
528 nx.add_cycle(G, [1, 2, 3, 4]) | |
529 nx.add_cycle(G, [5, 6, 7, 8]) | |
530 assert not nx.is_aperiodic(G) | |
531 G.add_edge(1, 3) | |
532 G.add_edge(5, 7) | |
533 assert nx.is_aperiodic(G) | |
534 | |
535 | |
536 def test_is_aperiodic_disconnected2(): | |
537 G = nx.DiGraph() | |
538 nx.add_cycle(G, [0, 1, 2]) | |
539 G.add_edge(3, 3) | |
540 assert not nx.is_aperiodic(G) | |
541 | |
542 | |
543 class TestDagToBranching: | |
544 """Unit tests for the :func:`networkx.dag_to_branching` function.""" | |
545 | |
546 def test_single_root(self): | |
547 """Tests that a directed acyclic graph with a single degree | |
548 zero node produces an arborescence. | |
549 | |
550 """ | |
551 G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3)]) | |
552 B = nx.dag_to_branching(G) | |
553 expected = nx.DiGraph([(0, 1), (1, 3), (0, 2), (2, 4)]) | |
554 assert nx.is_arborescence(B) | |
555 assert nx.is_isomorphic(B, expected) | |
556 | |
557 def test_multiple_roots(self): | |
558 """Tests that a directed acyclic graph with multiple degree zero | |
559 nodes creates an arborescence with multiple (weakly) connected | |
560 components. | |
561 | |
562 """ | |
563 G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3), (5, 2)]) | |
564 B = nx.dag_to_branching(G) | |
565 expected = nx.DiGraph([(0, 1), (1, 3), (0, 2), (2, 4), (5, 6), (6, 7)]) | |
566 assert nx.is_branching(B) | |
567 assert not nx.is_arborescence(B) | |
568 assert nx.is_isomorphic(B, expected) | |
569 | |
570 # # Attributes are not copied by this function. If they were, this would | |
571 # # be a good test to uncomment. | |
572 # def test_copy_attributes(self): | |
573 # """Tests that node attributes are copied in the branching.""" | |
574 # G = nx.DiGraph([(0, 1), (0, 2), (1, 3), (2, 3)]) | |
575 # for v in G: | |
576 # G.node[v]['label'] = str(v) | |
577 # B = nx.dag_to_branching(G) | |
578 # # Determine the root node of the branching. | |
579 # root = next(v for v, d in B.in_degree() if d == 0) | |
580 # assert_equal(B.node[root]['label'], '0') | |
581 # children = B[root] | |
582 # # Get the left and right children, nodes 1 and 2, respectively. | |
583 # left, right = sorted(children, key=lambda v: B.node[v]['label']) | |
584 # assert_equal(B.node[left]['label'], '1') | |
585 # assert_equal(B.node[right]['label'], '2') | |
586 # # Get the left grandchild. | |
587 # children = B[left] | |
588 # assert_equal(len(children), 1) | |
589 # left_grandchild = arbitrary_element(children) | |
590 # assert_equal(B.node[left_grandchild]['label'], '3') | |
591 # # Get the right grandchild. | |
592 # children = B[right] | |
593 # assert_equal(len(children), 1) | |
594 # right_grandchild = arbitrary_element(children) | |
595 # assert_equal(B.node[right_grandchild]['label'], '3') | |
596 | |
597 def test_already_arborescence(self): | |
598 """Tests that a directed acyclic graph that is already an | |
599 arborescence produces an isomorphic arborescence as output. | |
600 | |
601 """ | |
602 A = nx.balanced_tree(2, 2, create_using=nx.DiGraph()) | |
603 B = nx.dag_to_branching(A) | |
604 assert nx.is_isomorphic(A, B) | |
605 | |
606 def test_already_branching(self): | |
607 """Tests that a directed acyclic graph that is already a | |
608 branching produces an isomorphic branching as output. | |
609 | |
610 """ | |
611 T1 = nx.balanced_tree(2, 2, create_using=nx.DiGraph()) | |
612 T2 = nx.balanced_tree(2, 2, create_using=nx.DiGraph()) | |
613 G = nx.disjoint_union(T1, T2) | |
614 B = nx.dag_to_branching(G) | |
615 assert nx.is_isomorphic(G, B) | |
616 | |
617 def test_not_acyclic(self): | |
618 """Tests that a non-acyclic graph causes an exception.""" | |
619 with pytest.raises(nx.HasACycle): | |
620 G = nx.DiGraph(pairwise("abc", cyclic=True)) | |
621 nx.dag_to_branching(G) | |
622 | |
623 def test_undirected(self): | |
624 with pytest.raises(nx.NetworkXNotImplemented): | |
625 nx.dag_to_branching(nx.Graph()) | |
626 | |
627 def test_multigraph(self): | |
628 with pytest.raises(nx.NetworkXNotImplemented): | |
629 nx.dag_to_branching(nx.MultiGraph()) | |
630 | |
631 def test_multidigraph(self): | |
632 with pytest.raises(nx.NetworkXNotImplemented): | |
633 nx.dag_to_branching(nx.MultiDiGraph()) |