Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_minors.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.minors` module.""" | |
2 import pytest | |
3 | |
4 import networkx as nx | |
5 from networkx.testing.utils import assert_edges_equal, assert_nodes_equal | |
6 from networkx.utils import arbitrary_element | |
7 | |
8 | |
9 class TestQuotient: | |
10 """Unit tests for computing quotient graphs.""" | |
11 | |
12 def test_quotient_graph_complete_multipartite(self): | |
13 """Tests that the quotient graph of the complete *n*-partite graph | |
14 under the "same neighbors" node relation is the complete graph on *n* | |
15 nodes. | |
16 | |
17 """ | |
18 G = nx.complete_multipartite_graph(2, 3, 4) | |
19 # Two nodes are equivalent if they are not adjacent but have the same | |
20 # neighbor set. | |
21 | |
22 def same_neighbors(u, v): | |
23 return u not in G[v] and v not in G[u] and G[u] == G[v] | |
24 | |
25 expected = nx.complete_graph(3) | |
26 actual = nx.quotient_graph(G, same_neighbors) | |
27 # It won't take too long to run a graph isomorphism algorithm on such | |
28 # small graphs. | |
29 assert nx.is_isomorphic(expected, actual) | |
30 | |
31 def test_quotient_graph_complete_bipartite(self): | |
32 """Tests that the quotient graph of the complete bipartite graph under | |
33 the "same neighbors" node relation is `K_2`. | |
34 | |
35 """ | |
36 G = nx.complete_bipartite_graph(2, 3) | |
37 # Two nodes are equivalent if they are not adjacent but have the same | |
38 # neighbor set. | |
39 | |
40 def same_neighbors(u, v): | |
41 return u not in G[v] and v not in G[u] and G[u] == G[v] | |
42 | |
43 expected = nx.complete_graph(2) | |
44 actual = nx.quotient_graph(G, same_neighbors) | |
45 # It won't take too long to run a graph isomorphism algorithm on such | |
46 # small graphs. | |
47 assert nx.is_isomorphic(expected, actual) | |
48 | |
49 def test_quotient_graph_edge_relation(self): | |
50 """Tests for specifying an alternate edge relation for the quotient | |
51 graph. | |
52 | |
53 """ | |
54 G = nx.path_graph(5) | |
55 | |
56 def identity(u, v): | |
57 return u == v | |
58 | |
59 def same_parity(b, c): | |
60 return arbitrary_element(b) % 2 == arbitrary_element(c) % 2 | |
61 | |
62 actual = nx.quotient_graph(G, identity, same_parity) | |
63 expected = nx.Graph() | |
64 expected.add_edges_from([(0, 2), (0, 4), (2, 4)]) | |
65 expected.add_edge(1, 3) | |
66 assert nx.is_isomorphic(actual, expected) | |
67 | |
68 def test_condensation_as_quotient(self): | |
69 """This tests that the condensation of a graph can be viewed as the | |
70 quotient graph under the "in the same connected component" equivalence | |
71 relation. | |
72 | |
73 """ | |
74 # This example graph comes from the file `test_strongly_connected.py`. | |
75 G = nx.DiGraph() | |
76 G.add_edges_from( | |
77 [ | |
78 (1, 2), | |
79 (2, 3), | |
80 (2, 11), | |
81 (2, 12), | |
82 (3, 4), | |
83 (4, 3), | |
84 (4, 5), | |
85 (5, 6), | |
86 (6, 5), | |
87 (6, 7), | |
88 (7, 8), | |
89 (7, 9), | |
90 (7, 10), | |
91 (8, 9), | |
92 (9, 7), | |
93 (10, 6), | |
94 (11, 2), | |
95 (11, 4), | |
96 (11, 6), | |
97 (12, 6), | |
98 (12, 11), | |
99 ] | |
100 ) | |
101 scc = list(nx.strongly_connected_components(G)) | |
102 C = nx.condensation(G, scc) | |
103 component_of = C.graph["mapping"] | |
104 # Two nodes are equivalent if they are in the same connected component. | |
105 | |
106 def same_component(u, v): | |
107 return component_of[u] == component_of[v] | |
108 | |
109 Q = nx.quotient_graph(G, same_component) | |
110 assert nx.is_isomorphic(C, Q) | |
111 | |
112 def test_path(self): | |
113 G = nx.path_graph(6) | |
114 partition = [{0, 1}, {2, 3}, {4, 5}] | |
115 M = nx.quotient_graph(G, partition, relabel=True) | |
116 assert_nodes_equal(M, [0, 1, 2]) | |
117 assert_edges_equal(M.edges(), [(0, 1), (1, 2)]) | |
118 for n in M: | |
119 assert M.nodes[n]["nedges"] == 1 | |
120 assert M.nodes[n]["nnodes"] == 2 | |
121 assert M.nodes[n]["density"] == 1 | |
122 | |
123 def test_multigraph_path(self): | |
124 G = nx.MultiGraph(nx.path_graph(6)) | |
125 partition = [{0, 1}, {2, 3}, {4, 5}] | |
126 M = nx.quotient_graph(G, partition, relabel=True) | |
127 assert_nodes_equal(M, [0, 1, 2]) | |
128 assert_edges_equal(M.edges(), [(0, 1), (1, 2)]) | |
129 for n in M: | |
130 assert M.nodes[n]["nedges"] == 1 | |
131 assert M.nodes[n]["nnodes"] == 2 | |
132 assert M.nodes[n]["density"] == 1 | |
133 | |
134 def test_directed_path(self): | |
135 G = nx.DiGraph() | |
136 nx.add_path(G, range(6)) | |
137 partition = [{0, 1}, {2, 3}, {4, 5}] | |
138 M = nx.quotient_graph(G, partition, relabel=True) | |
139 assert_nodes_equal(M, [0, 1, 2]) | |
140 assert_edges_equal(M.edges(), [(0, 1), (1, 2)]) | |
141 for n in M: | |
142 assert M.nodes[n]["nedges"] == 1 | |
143 assert M.nodes[n]["nnodes"] == 2 | |
144 assert M.nodes[n]["density"] == 0.5 | |
145 | |
146 def test_directed_multigraph_path(self): | |
147 G = nx.MultiDiGraph() | |
148 nx.add_path(G, range(6)) | |
149 partition = [{0, 1}, {2, 3}, {4, 5}] | |
150 M = nx.quotient_graph(G, partition, relabel=True) | |
151 assert_nodes_equal(M, [0, 1, 2]) | |
152 assert_edges_equal(M.edges(), [(0, 1), (1, 2)]) | |
153 for n in M: | |
154 assert M.nodes[n]["nedges"] == 1 | |
155 assert M.nodes[n]["nnodes"] == 2 | |
156 assert M.nodes[n]["density"] == 0.5 | |
157 | |
158 def test_overlapping_blocks(self): | |
159 with pytest.raises(nx.NetworkXException): | |
160 G = nx.path_graph(6) | |
161 partition = [{0, 1, 2}, {2, 3}, {4, 5}] | |
162 nx.quotient_graph(G, partition) | |
163 | |
164 def test_weighted_path(self): | |
165 G = nx.path_graph(6) | |
166 for i in range(5): | |
167 G[i][i + 1]["weight"] = i + 1 | |
168 partition = [{0, 1}, {2, 3}, {4, 5}] | |
169 M = nx.quotient_graph(G, partition, relabel=True) | |
170 assert_nodes_equal(M, [0, 1, 2]) | |
171 assert_edges_equal(M.edges(), [(0, 1), (1, 2)]) | |
172 assert M[0][1]["weight"] == 2 | |
173 assert M[1][2]["weight"] == 4 | |
174 for n in M: | |
175 assert M.nodes[n]["nedges"] == 1 | |
176 assert M.nodes[n]["nnodes"] == 2 | |
177 assert M.nodes[n]["density"] == 1 | |
178 | |
179 def test_barbell(self): | |
180 G = nx.barbell_graph(3, 0) | |
181 partition = [{0, 1, 2}, {3, 4, 5}] | |
182 M = nx.quotient_graph(G, partition, relabel=True) | |
183 assert_nodes_equal(M, [0, 1]) | |
184 assert_edges_equal(M.edges(), [(0, 1)]) | |
185 for n in M: | |
186 assert M.nodes[n]["nedges"] == 3 | |
187 assert M.nodes[n]["nnodes"] == 3 | |
188 assert M.nodes[n]["density"] == 1 | |
189 | |
190 def test_barbell_plus(self): | |
191 G = nx.barbell_graph(3, 0) | |
192 # Add an extra edge joining the bells. | |
193 G.add_edge(0, 5) | |
194 partition = [{0, 1, 2}, {3, 4, 5}] | |
195 M = nx.quotient_graph(G, partition, relabel=True) | |
196 assert_nodes_equal(M, [0, 1]) | |
197 assert_edges_equal(M.edges(), [(0, 1)]) | |
198 assert M[0][1]["weight"] == 2 | |
199 for n in M: | |
200 assert M.nodes[n]["nedges"] == 3 | |
201 assert M.nodes[n]["nnodes"] == 3 | |
202 assert M.nodes[n]["density"] == 1 | |
203 | |
204 def test_blockmodel(self): | |
205 G = nx.path_graph(6) | |
206 partition = [[0, 1], [2, 3], [4, 5]] | |
207 M = nx.quotient_graph(G, partition, relabel=True) | |
208 assert_nodes_equal(M.nodes(), [0, 1, 2]) | |
209 assert_edges_equal(M.edges(), [(0, 1), (1, 2)]) | |
210 for n in M.nodes(): | |
211 assert M.nodes[n]["nedges"] == 1 | |
212 assert M.nodes[n]["nnodes"] == 2 | |
213 assert M.nodes[n]["density"] == 1.0 | |
214 | |
215 def test_multigraph_blockmodel(self): | |
216 G = nx.MultiGraph(nx.path_graph(6)) | |
217 partition = [[0, 1], [2, 3], [4, 5]] | |
218 M = nx.quotient_graph(G, partition, create_using=nx.MultiGraph(), relabel=True) | |
219 assert_nodes_equal(M.nodes(), [0, 1, 2]) | |
220 assert_edges_equal(M.edges(), [(0, 1), (1, 2)]) | |
221 for n in M.nodes(): | |
222 assert M.nodes[n]["nedges"] == 1 | |
223 assert M.nodes[n]["nnodes"] == 2 | |
224 assert M.nodes[n]["density"] == 1.0 | |
225 | |
226 def test_quotient_graph_incomplete_partition(self): | |
227 G = nx.path_graph(6) | |
228 partition = [] | |
229 H = nx.quotient_graph(G, partition, relabel=True) | |
230 assert_nodes_equal(H.nodes(), []) | |
231 assert_edges_equal(H.edges(), []) | |
232 | |
233 partition = [[0, 1], [2, 3], [5]] | |
234 H = nx.quotient_graph(G, partition, relabel=True) | |
235 assert_nodes_equal(H.nodes(), [0, 1, 2]) | |
236 assert_edges_equal(H.edges(), [(0, 1)]) | |
237 | |
238 | |
239 class TestContraction: | |
240 """Unit tests for node and edge contraction functions.""" | |
241 | |
242 def test_undirected_node_contraction(self): | |
243 """Tests for node contraction in an undirected graph.""" | |
244 G = nx.cycle_graph(4) | |
245 actual = nx.contracted_nodes(G, 0, 1) | |
246 expected = nx.cycle_graph(3) | |
247 expected.add_edge(0, 0) | |
248 assert nx.is_isomorphic(actual, expected) | |
249 | |
250 def test_directed_node_contraction(self): | |
251 """Tests for node contraction in a directed graph.""" | |
252 G = nx.DiGraph(nx.cycle_graph(4)) | |
253 actual = nx.contracted_nodes(G, 0, 1) | |
254 expected = nx.DiGraph(nx.cycle_graph(3)) | |
255 expected.add_edge(0, 0) | |
256 expected.add_edge(0, 0) | |
257 assert nx.is_isomorphic(actual, expected) | |
258 | |
259 def test_undirected_node_contraction_no_copy(self): | |
260 """Tests for node contraction in an undirected graph | |
261 by making changes in place.""" | |
262 G = nx.cycle_graph(4) | |
263 actual = nx.contracted_nodes(G, 0, 1, copy=False) | |
264 expected = nx.cycle_graph(3) | |
265 expected.add_edge(0, 0) | |
266 assert nx.is_isomorphic(actual, G) | |
267 assert nx.is_isomorphic(actual, expected) | |
268 | |
269 def test_directed_node_contraction_no_copy(self): | |
270 """Tests for node contraction in a directed graph | |
271 by making changes in place.""" | |
272 G = nx.DiGraph(nx.cycle_graph(4)) | |
273 actual = nx.contracted_nodes(G, 0, 1, copy=False) | |
274 expected = nx.DiGraph(nx.cycle_graph(3)) | |
275 expected.add_edge(0, 0) | |
276 expected.add_edge(0, 0) | |
277 assert nx.is_isomorphic(actual, G) | |
278 assert nx.is_isomorphic(actual, expected) | |
279 | |
280 def test_create_multigraph(self): | |
281 """Tests that using a MultiGraph creates multiple edges.""" | |
282 G = nx.path_graph(3, create_using=nx.MultiGraph()) | |
283 G.add_edge(0, 1) | |
284 G.add_edge(0, 0) | |
285 G.add_edge(0, 2) | |
286 actual = nx.contracted_nodes(G, 0, 2) | |
287 expected = nx.MultiGraph() | |
288 expected.add_edge(0, 1) | |
289 expected.add_edge(0, 1) | |
290 expected.add_edge(0, 1) | |
291 expected.add_edge(0, 0) | |
292 expected.add_edge(0, 0) | |
293 assert_edges_equal(actual.edges, expected.edges) | |
294 | |
295 def test_multigraph_keys(self): | |
296 """Tests that multiedge keys are reset in new graph.""" | |
297 G = nx.path_graph(3, create_using=nx.MultiGraph()) | |
298 G.add_edge(0, 1, 5) | |
299 G.add_edge(0, 0, 0) | |
300 G.add_edge(0, 2, 5) | |
301 actual = nx.contracted_nodes(G, 0, 2) | |
302 expected = nx.MultiGraph() | |
303 expected.add_edge(0, 1, 0) | |
304 expected.add_edge(0, 1, 5) | |
305 expected.add_edge(0, 1, 2) # keyed as 2 b/c 2 edges already in G | |
306 expected.add_edge(0, 0, 0) | |
307 expected.add_edge(0, 0, 1) # this comes from (0, 2, 5) | |
308 assert_edges_equal(actual.edges, expected.edges) | |
309 | |
310 def test_node_attributes(self): | |
311 """Tests that node contraction preserves node attributes.""" | |
312 G = nx.cycle_graph(4) | |
313 # Add some data to the two nodes being contracted. | |
314 G.nodes[0]["foo"] = "bar" | |
315 G.nodes[1]["baz"] = "xyzzy" | |
316 actual = nx.contracted_nodes(G, 0, 1) | |
317 # We expect that contracting the nodes 0 and 1 in C_4 yields K_3, but | |
318 # with nodes labeled 0, 2, and 3, and with a self-loop on 0. | |
319 expected = nx.complete_graph(3) | |
320 expected = nx.relabel_nodes(expected, {1: 2, 2: 3}) | |
321 expected.add_edge(0, 0) | |
322 cdict = {1: {"baz": "xyzzy"}} | |
323 expected.nodes[0].update(dict(foo="bar", contraction=cdict)) | |
324 assert nx.is_isomorphic(actual, expected) | |
325 assert actual.nodes == expected.nodes | |
326 | |
327 def test_without_self_loops(self): | |
328 """Tests for node contraction without preserving self-loops.""" | |
329 G = nx.cycle_graph(4) | |
330 actual = nx.contracted_nodes(G, 0, 1, self_loops=False) | |
331 expected = nx.complete_graph(3) | |
332 assert nx.is_isomorphic(actual, expected) | |
333 | |
334 def test_contract_selfloop_graph(self): | |
335 """Tests for node contraction when nodes have selfloops.""" | |
336 G = nx.cycle_graph(4) | |
337 G.add_edge(0, 0) | |
338 actual = nx.contracted_nodes(G, 0, 1) | |
339 expected = nx.complete_graph([0, 2, 3]) | |
340 expected.add_edge(0, 0) | |
341 expected.add_edge(0, 0) | |
342 assert_edges_equal(actual.edges, expected.edges) | |
343 actual = nx.contracted_nodes(G, 1, 0) | |
344 expected = nx.complete_graph([1, 2, 3]) | |
345 expected.add_edge(1, 1) | |
346 expected.add_edge(1, 1) | |
347 assert_edges_equal(actual.edges, expected.edges) | |
348 | |
349 def test_undirected_edge_contraction(self): | |
350 """Tests for edge contraction in an undirected graph.""" | |
351 G = nx.cycle_graph(4) | |
352 actual = nx.contracted_edge(G, (0, 1)) | |
353 expected = nx.complete_graph(3) | |
354 expected.add_edge(0, 0) | |
355 assert nx.is_isomorphic(actual, expected) | |
356 | |
357 def test_nonexistent_edge(self): | |
358 """Tests that attempting to contract a non-existent edge raises an | |
359 exception. | |
360 | |
361 """ | |
362 with pytest.raises(ValueError): | |
363 G = nx.cycle_graph(4) | |
364 nx.contracted_edge(G, (0, 2)) |