Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tree/tests/test_mst.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 """Unit tests for the :mod:`networkx.algorithms.tree.mst` module.""" | |
2 | |
3 import pytest | |
4 | |
5 import networkx as nx | |
6 from networkx.testing import assert_nodes_equal, assert_edges_equal | |
7 | |
8 | |
9 def test_unknown_algorithm(): | |
10 with pytest.raises(ValueError): | |
11 nx.minimum_spanning_tree(nx.Graph(), algorithm="random") | |
12 | |
13 | |
14 class MinimumSpanningTreeTestBase: | |
15 """Base class for test classes for minimum spanning tree algorithms. | |
16 | |
17 This class contains some common tests that will be inherited by | |
18 subclasses. Each subclass must have a class attribute | |
19 :data:`algorithm` that is a string representing the algorithm to | |
20 run, as described under the ``algorithm`` keyword argument for the | |
21 :func:`networkx.minimum_spanning_edges` function. Subclasses can | |
22 then implement any algorithm-specific tests. | |
23 | |
24 """ | |
25 | |
26 def setup_method(self, method): | |
27 """Creates an example graph and stores the expected minimum and | |
28 maximum spanning tree edges. | |
29 | |
30 """ | |
31 # This stores the class attribute `algorithm` in an instance attribute. | |
32 self.algo = self.algorithm | |
33 # This example graph comes from Wikipedia: | |
34 # https://en.wikipedia.org/wiki/Kruskal's_algorithm | |
35 edges = [ | |
36 (0, 1, 7), | |
37 (0, 3, 5), | |
38 (1, 2, 8), | |
39 (1, 3, 9), | |
40 (1, 4, 7), | |
41 (2, 4, 5), | |
42 (3, 4, 15), | |
43 (3, 5, 6), | |
44 (4, 5, 8), | |
45 (4, 6, 9), | |
46 (5, 6, 11), | |
47 ] | |
48 self.G = nx.Graph() | |
49 self.G.add_weighted_edges_from(edges) | |
50 self.minimum_spanning_edgelist = [ | |
51 (0, 1, {"weight": 7}), | |
52 (0, 3, {"weight": 5}), | |
53 (1, 4, {"weight": 7}), | |
54 (2, 4, {"weight": 5}), | |
55 (3, 5, {"weight": 6}), | |
56 (4, 6, {"weight": 9}), | |
57 ] | |
58 self.maximum_spanning_edgelist = [ | |
59 (0, 1, {"weight": 7}), | |
60 (1, 2, {"weight": 8}), | |
61 (1, 3, {"weight": 9}), | |
62 (3, 4, {"weight": 15}), | |
63 (4, 6, {"weight": 9}), | |
64 (5, 6, {"weight": 11}), | |
65 ] | |
66 | |
67 def test_minimum_edges(self): | |
68 edges = nx.minimum_spanning_edges(self.G, algorithm=self.algo) | |
69 # Edges from the spanning edges functions don't come in sorted | |
70 # orientation, so we need to sort each edge individually. | |
71 actual = sorted((min(u, v), max(u, v), d) for u, v, d in edges) | |
72 assert_edges_equal(actual, self.minimum_spanning_edgelist) | |
73 | |
74 def test_maximum_edges(self): | |
75 edges = nx.maximum_spanning_edges(self.G, algorithm=self.algo) | |
76 # Edges from the spanning edges functions don't come in sorted | |
77 # orientation, so we need to sort each edge individually. | |
78 actual = sorted((min(u, v), max(u, v), d) for u, v, d in edges) | |
79 assert_edges_equal(actual, self.maximum_spanning_edgelist) | |
80 | |
81 def test_without_data(self): | |
82 edges = nx.minimum_spanning_edges(self.G, algorithm=self.algo, data=False) | |
83 # Edges from the spanning edges functions don't come in sorted | |
84 # orientation, so we need to sort each edge individually. | |
85 actual = sorted((min(u, v), max(u, v)) for u, v in edges) | |
86 expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist] | |
87 assert_edges_equal(actual, expected) | |
88 | |
89 def test_nan_weights(self): | |
90 # Edge weights NaN never appear in the spanning tree. see #2164 | |
91 G = self.G | |
92 G.add_edge(0, 12, weight=float("nan")) | |
93 edges = nx.minimum_spanning_edges( | |
94 G, algorithm=self.algo, data=False, ignore_nan=True | |
95 ) | |
96 actual = sorted((min(u, v), max(u, v)) for u, v in edges) | |
97 expected = [(u, v) for u, v, d in self.minimum_spanning_edgelist] | |
98 assert_edges_equal(actual, expected) | |
99 # Now test for raising exception | |
100 edges = nx.minimum_spanning_edges( | |
101 G, algorithm=self.algo, data=False, ignore_nan=False | |
102 ) | |
103 with pytest.raises(ValueError): | |
104 list(edges) | |
105 # test default for ignore_nan as False | |
106 edges = nx.minimum_spanning_edges(G, algorithm=self.algo, data=False) | |
107 with pytest.raises(ValueError): | |
108 list(edges) | |
109 | |
110 def test_nan_weights_order(self): | |
111 # now try again with a nan edge at the beginning of G.nodes | |
112 edges = [ | |
113 (0, 1, 7), | |
114 (0, 3, 5), | |
115 (1, 2, 8), | |
116 (1, 3, 9), | |
117 (1, 4, 7), | |
118 (2, 4, 5), | |
119 (3, 4, 15), | |
120 (3, 5, 6), | |
121 (4, 5, 8), | |
122 (4, 6, 9), | |
123 (5, 6, 11), | |
124 ] | |
125 G = nx.Graph() | |
126 G.add_weighted_edges_from([(u + 1, v + 1, wt) for u, v, wt in edges]) | |
127 G.add_edge(0, 7, weight=float("nan")) | |
128 edges = nx.minimum_spanning_edges( | |
129 G, algorithm=self.algo, data=False, ignore_nan=True | |
130 ) | |
131 actual = sorted((min(u, v), max(u, v)) for u, v in edges) | |
132 shift = [(u + 1, v + 1) for u, v, d in self.minimum_spanning_edgelist] | |
133 assert_edges_equal(actual, shift) | |
134 | |
135 def test_isolated_node(self): | |
136 # now try again with an isolated node | |
137 edges = [ | |
138 (0, 1, 7), | |
139 (0, 3, 5), | |
140 (1, 2, 8), | |
141 (1, 3, 9), | |
142 (1, 4, 7), | |
143 (2, 4, 5), | |
144 (3, 4, 15), | |
145 (3, 5, 6), | |
146 (4, 5, 8), | |
147 (4, 6, 9), | |
148 (5, 6, 11), | |
149 ] | |
150 G = nx.Graph() | |
151 G.add_weighted_edges_from([(u + 1, v + 1, wt) for u, v, wt in edges]) | |
152 G.add_node(0) | |
153 edges = nx.minimum_spanning_edges( | |
154 G, algorithm=self.algo, data=False, ignore_nan=True | |
155 ) | |
156 actual = sorted((min(u, v), max(u, v)) for u, v in edges) | |
157 shift = [(u + 1, v + 1) for u, v, d in self.minimum_spanning_edgelist] | |
158 assert_edges_equal(actual, shift) | |
159 | |
160 def test_minimum_tree(self): | |
161 T = nx.minimum_spanning_tree(self.G, algorithm=self.algo) | |
162 actual = sorted(T.edges(data=True)) | |
163 assert_edges_equal(actual, self.minimum_spanning_edgelist) | |
164 | |
165 def test_maximum_tree(self): | |
166 T = nx.maximum_spanning_tree(self.G, algorithm=self.algo) | |
167 actual = sorted(T.edges(data=True)) | |
168 assert_edges_equal(actual, self.maximum_spanning_edgelist) | |
169 | |
170 def test_disconnected(self): | |
171 G = nx.Graph([(0, 1, dict(weight=1)), (2, 3, dict(weight=2))]) | |
172 T = nx.minimum_spanning_tree(G, algorithm=self.algo) | |
173 assert_nodes_equal(list(T), list(range(4))) | |
174 assert_edges_equal(list(T.edges()), [(0, 1), (2, 3)]) | |
175 | |
176 def test_empty_graph(self): | |
177 G = nx.empty_graph(3) | |
178 T = nx.minimum_spanning_tree(G, algorithm=self.algo) | |
179 assert_nodes_equal(sorted(T), list(range(3))) | |
180 assert T.number_of_edges() == 0 | |
181 | |
182 def test_attributes(self): | |
183 G = nx.Graph() | |
184 G.add_edge(1, 2, weight=1, color="red", distance=7) | |
185 G.add_edge(2, 3, weight=1, color="green", distance=2) | |
186 G.add_edge(1, 3, weight=10, color="blue", distance=1) | |
187 G.graph["foo"] = "bar" | |
188 T = nx.minimum_spanning_tree(G, algorithm=self.algo) | |
189 assert T.graph == G.graph | |
190 assert_nodes_equal(T, G) | |
191 for u, v in T.edges(): | |
192 assert T.adj[u][v] == G.adj[u][v] | |
193 | |
194 def test_weight_attribute(self): | |
195 G = nx.Graph() | |
196 G.add_edge(0, 1, weight=1, distance=7) | |
197 G.add_edge(0, 2, weight=30, distance=1) | |
198 G.add_edge(1, 2, weight=1, distance=1) | |
199 G.add_node(3) | |
200 T = nx.minimum_spanning_tree(G, algorithm=self.algo, weight="distance") | |
201 assert_nodes_equal(sorted(T), list(range(4))) | |
202 assert_edges_equal(sorted(T.edges()), [(0, 2), (1, 2)]) | |
203 T = nx.maximum_spanning_tree(G, algorithm=self.algo, weight="distance") | |
204 assert_nodes_equal(sorted(T), list(range(4))) | |
205 assert_edges_equal(sorted(T.edges()), [(0, 1), (0, 2)]) | |
206 | |
207 | |
208 class TestBoruvka(MinimumSpanningTreeTestBase): | |
209 """Unit tests for computing a minimum (or maximum) spanning tree | |
210 using Borůvka's algorithm. | |
211 | |
212 """ | |
213 | |
214 algorithm = "boruvka" | |
215 | |
216 def test_unicode_name(self): | |
217 """Tests that using a Unicode string can correctly indicate | |
218 Borůvka's algorithm. | |
219 | |
220 """ | |
221 edges = nx.minimum_spanning_edges(self.G, algorithm="borůvka") | |
222 # Edges from the spanning edges functions don't come in sorted | |
223 # orientation, so we need to sort each edge individually. | |
224 actual = sorted((min(u, v), max(u, v), d) for u, v, d in edges) | |
225 assert_edges_equal(actual, self.minimum_spanning_edgelist) | |
226 | |
227 | |
228 class MultigraphMSTTestBase(MinimumSpanningTreeTestBase): | |
229 # Abstract class | |
230 | |
231 def test_multigraph_keys_min(self): | |
232 """Tests that the minimum spanning edges of a multigraph | |
233 preserves edge keys. | |
234 | |
235 """ | |
236 G = nx.MultiGraph() | |
237 G.add_edge(0, 1, key="a", weight=2) | |
238 G.add_edge(0, 1, key="b", weight=1) | |
239 min_edges = nx.minimum_spanning_edges | |
240 mst_edges = min_edges(G, algorithm=self.algo, data=False) | |
241 assert_edges_equal([(0, 1, "b")], list(mst_edges)) | |
242 | |
243 def test_multigraph_keys_max(self): | |
244 """Tests that the maximum spanning edges of a multigraph | |
245 preserves edge keys. | |
246 | |
247 """ | |
248 G = nx.MultiGraph() | |
249 G.add_edge(0, 1, key="a", weight=2) | |
250 G.add_edge(0, 1, key="b", weight=1) | |
251 max_edges = nx.maximum_spanning_edges | |
252 mst_edges = max_edges(G, algorithm=self.algo, data=False) | |
253 assert_edges_equal([(0, 1, "a")], list(mst_edges)) | |
254 | |
255 | |
256 class TestKruskal(MultigraphMSTTestBase): | |
257 """Unit tests for computing a minimum (or maximum) spanning tree | |
258 using Kruskal's algorithm. | |
259 | |
260 """ | |
261 | |
262 algorithm = "kruskal" | |
263 | |
264 | |
265 class TestPrim(MultigraphMSTTestBase): | |
266 """Unit tests for computing a minimum (or maximum) spanning tree | |
267 using Prim's algorithm. | |
268 | |
269 """ | |
270 | |
271 algorithm = "prim" | |
272 | |
273 def test_multigraph_keys_tree(self): | |
274 G = nx.MultiGraph() | |
275 G.add_edge(0, 1, key="a", weight=2) | |
276 G.add_edge(0, 1, key="b", weight=1) | |
277 T = nx.minimum_spanning_tree(G) | |
278 assert_edges_equal([(0, 1, 1)], list(T.edges(data="weight"))) | |
279 | |
280 def test_multigraph_keys_tree_max(self): | |
281 G = nx.MultiGraph() | |
282 G.add_edge(0, 1, key="a", weight=2) | |
283 G.add_edge(0, 1, key="b", weight=1) | |
284 T = nx.maximum_spanning_tree(G) | |
285 assert_edges_equal([(0, 1, 2)], list(T.edges(data="weight"))) |