Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_euler.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 collections | |
2 | |
3 import pytest | |
4 | |
5 import networkx as nx | |
6 | |
7 | |
8 class TestIsEulerian: | |
9 def test_is_eulerian(self): | |
10 assert nx.is_eulerian(nx.complete_graph(5)) | |
11 assert nx.is_eulerian(nx.complete_graph(7)) | |
12 assert nx.is_eulerian(nx.hypercube_graph(4)) | |
13 assert nx.is_eulerian(nx.hypercube_graph(6)) | |
14 | |
15 assert not nx.is_eulerian(nx.complete_graph(4)) | |
16 assert not nx.is_eulerian(nx.complete_graph(6)) | |
17 assert not nx.is_eulerian(nx.hypercube_graph(3)) | |
18 assert not nx.is_eulerian(nx.hypercube_graph(5)) | |
19 | |
20 assert not nx.is_eulerian(nx.petersen_graph()) | |
21 assert not nx.is_eulerian(nx.path_graph(4)) | |
22 | |
23 def test_is_eulerian2(self): | |
24 # not connected | |
25 G = nx.Graph() | |
26 G.add_nodes_from([1, 2, 3]) | |
27 assert not nx.is_eulerian(G) | |
28 # not strongly connected | |
29 G = nx.DiGraph() | |
30 G.add_nodes_from([1, 2, 3]) | |
31 assert not nx.is_eulerian(G) | |
32 G = nx.MultiDiGraph() | |
33 G.add_edge(1, 2) | |
34 G.add_edge(2, 3) | |
35 G.add_edge(2, 3) | |
36 G.add_edge(3, 1) | |
37 assert not nx.is_eulerian(G) | |
38 | |
39 | |
40 class TestEulerianCircuit: | |
41 def test_eulerian_circuit_cycle(self): | |
42 G = nx.cycle_graph(4) | |
43 | |
44 edges = list(nx.eulerian_circuit(G, source=0)) | |
45 nodes = [u for u, v in edges] | |
46 assert nodes == [0, 3, 2, 1] | |
47 assert edges == [(0, 3), (3, 2), (2, 1), (1, 0)] | |
48 | |
49 edges = list(nx.eulerian_circuit(G, source=1)) | |
50 nodes = [u for u, v in edges] | |
51 assert nodes == [1, 2, 3, 0] | |
52 assert edges == [(1, 2), (2, 3), (3, 0), (0, 1)] | |
53 | |
54 G = nx.complete_graph(3) | |
55 | |
56 edges = list(nx.eulerian_circuit(G, source=0)) | |
57 nodes = [u for u, v in edges] | |
58 assert nodes == [0, 2, 1] | |
59 assert edges == [(0, 2), (2, 1), (1, 0)] | |
60 | |
61 edges = list(nx.eulerian_circuit(G, source=1)) | |
62 nodes = [u for u, v in edges] | |
63 assert nodes == [1, 2, 0] | |
64 assert edges == [(1, 2), (2, 0), (0, 1)] | |
65 | |
66 def test_eulerian_circuit_digraph(self): | |
67 G = nx.DiGraph() | |
68 nx.add_cycle(G, [0, 1, 2, 3]) | |
69 | |
70 edges = list(nx.eulerian_circuit(G, source=0)) | |
71 nodes = [u for u, v in edges] | |
72 assert nodes == [0, 1, 2, 3] | |
73 assert edges == [(0, 1), (1, 2), (2, 3), (3, 0)] | |
74 | |
75 edges = list(nx.eulerian_circuit(G, source=1)) | |
76 nodes = [u for u, v in edges] | |
77 assert nodes == [1, 2, 3, 0] | |
78 assert edges == [(1, 2), (2, 3), (3, 0), (0, 1)] | |
79 | |
80 def test_multigraph(self): | |
81 G = nx.MultiGraph() | |
82 nx.add_cycle(G, [0, 1, 2, 3]) | |
83 G.add_edge(1, 2) | |
84 G.add_edge(1, 2) | |
85 edges = list(nx.eulerian_circuit(G, source=0)) | |
86 nodes = [u for u, v in edges] | |
87 assert nodes == [0, 3, 2, 1, 2, 1] | |
88 assert edges == [(0, 3), (3, 2), (2, 1), (1, 2), (2, 1), (1, 0)] | |
89 | |
90 def test_multigraph_with_keys(self): | |
91 G = nx.MultiGraph() | |
92 nx.add_cycle(G, [0, 1, 2, 3]) | |
93 G.add_edge(1, 2) | |
94 G.add_edge(1, 2) | |
95 edges = list(nx.eulerian_circuit(G, source=0, keys=True)) | |
96 nodes = [u for u, v, k in edges] | |
97 assert nodes == [0, 3, 2, 1, 2, 1] | |
98 assert edges[:2] == [(0, 3, 0), (3, 2, 0)] | |
99 assert collections.Counter(edges[2:5]) == collections.Counter( | |
100 [(2, 1, 0), (1, 2, 1), (2, 1, 2)] | |
101 ) | |
102 assert edges[5:] == [(1, 0, 0)] | |
103 | |
104 def test_not_eulerian(self): | |
105 with pytest.raises(nx.NetworkXError): | |
106 f = list(nx.eulerian_circuit(nx.complete_graph(4))) | |
107 | |
108 | |
109 class TestIsSemiEulerian: | |
110 def test_is_semieulerian(self): | |
111 # Test graphs with Eulerian paths but no cycles return True. | |
112 assert nx.is_semieulerian(nx.path_graph(4)) | |
113 G = nx.path_graph(6, create_using=nx.DiGraph) | |
114 assert nx.is_semieulerian(G) | |
115 | |
116 # Test graphs with Eulerian cycles return False. | |
117 assert not nx.is_semieulerian(nx.complete_graph(5)) | |
118 assert not nx.is_semieulerian(nx.complete_graph(7)) | |
119 assert not nx.is_semieulerian(nx.hypercube_graph(4)) | |
120 assert not nx.is_semieulerian(nx.hypercube_graph(6)) | |
121 | |
122 | |
123 class TestHasEulerianPath: | |
124 def test_has_eulerian_path_cyclic(self): | |
125 # Test graphs with Eulerian cycles return True. | |
126 assert nx.has_eulerian_path(nx.complete_graph(5)) | |
127 assert nx.has_eulerian_path(nx.complete_graph(7)) | |
128 assert nx.has_eulerian_path(nx.hypercube_graph(4)) | |
129 assert nx.has_eulerian_path(nx.hypercube_graph(6)) | |
130 | |
131 def test_has_eulerian_path_non_cyclic(self): | |
132 # Test graphs with Eulerian paths but no cycles return True. | |
133 assert nx.has_eulerian_path(nx.path_graph(4)) | |
134 G = nx.path_graph(6, create_using=nx.DiGraph) | |
135 assert nx.has_eulerian_path(G) | |
136 | |
137 | |
138 class TestFindPathStart: | |
139 def testfind_path_start(self): | |
140 find_path_start = nx.algorithms.euler._find_path_start | |
141 # Test digraphs return correct starting node. | |
142 G = nx.path_graph(6, create_using=nx.DiGraph) | |
143 assert find_path_start(G) == 0 | |
144 edges = [(0, 1), (1, 2), (2, 0), (4, 0)] | |
145 assert find_path_start(nx.DiGraph(edges)) == 4 | |
146 | |
147 # Test graph with no Eulerian path return None. | |
148 edges = [(0, 1), (1, 2), (2, 3), (2, 4)] | |
149 assert find_path_start(nx.DiGraph(edges)) is None | |
150 | |
151 | |
152 class TestEulerianPath: | |
153 def test_eulerian_path(self): | |
154 x = [(4, 0), (0, 1), (1, 2), (2, 0)] | |
155 for e1, e2 in zip(x, nx.eulerian_path(nx.DiGraph(x))): | |
156 assert e1 == e2 | |
157 | |
158 | |
159 class TestEulerize: | |
160 def test_disconnected(self): | |
161 with pytest.raises(nx.NetworkXError): | |
162 G = nx.from_edgelist([(0, 1), (2, 3)]) | |
163 nx.eulerize(G) | |
164 | |
165 def test_null_graph(self): | |
166 with pytest.raises(nx.NetworkXPointlessConcept): | |
167 nx.eulerize(nx.Graph()) | |
168 | |
169 def test_null_multigraph(self): | |
170 with pytest.raises(nx.NetworkXPointlessConcept): | |
171 nx.eulerize(nx.MultiGraph()) | |
172 | |
173 def test_on_empty_graph(self): | |
174 with pytest.raises(nx.NetworkXError): | |
175 nx.eulerize(nx.empty_graph(3)) | |
176 | |
177 def test_on_eulerian(self): | |
178 G = nx.cycle_graph(3) | |
179 H = nx.eulerize(G) | |
180 assert nx.is_isomorphic(G, H) | |
181 | |
182 def test_on_eulerian_multigraph(self): | |
183 G = nx.MultiGraph(nx.cycle_graph(3)) | |
184 G.add_edge(0, 1) | |
185 H = nx.eulerize(G) | |
186 assert nx.is_eulerian(H) | |
187 | |
188 def test_on_complete_graph(self): | |
189 G = nx.complete_graph(4) | |
190 assert nx.is_eulerian(nx.eulerize(G)) | |
191 assert nx.is_eulerian(nx.eulerize(nx.MultiGraph(G))) |