Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_planarity.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 as nx | |
3 from networkx.algorithms.planarity import get_counterexample | |
4 from networkx.algorithms.planarity import get_counterexample_recursive | |
5 from networkx.algorithms.planarity import check_planarity_recursive | |
6 | |
7 | |
8 class TestLRPlanarity: | |
9 """Nose Unit tests for the :mod:`networkx.algorithms.planarity` module. | |
10 | |
11 Tests three things: | |
12 1. Check that the result is correct | |
13 (returns planar if and only if the graph is actually planar) | |
14 2. In case a counter example is returned: Check if it is correct | |
15 3. In case an embedding is returned: Check if its actually an embedding | |
16 """ | |
17 | |
18 @staticmethod | |
19 def check_graph(G, is_planar=None): | |
20 """Raises an exception if the lr_planarity check returns a wrong result | |
21 | |
22 Parameters | |
23 ---------- | |
24 G : NetworkX graph | |
25 is_planar : bool | |
26 The expected result of the planarity check. | |
27 If set to None only counter example or embedding are verified. | |
28 | |
29 """ | |
30 | |
31 # obtain results of planarity check | |
32 is_planar_lr, result = nx.check_planarity(G, True) | |
33 is_planar_lr_rec, result_rec = check_planarity_recursive(G, True) | |
34 | |
35 if is_planar is not None: | |
36 # set a message for the assert | |
37 if is_planar: | |
38 msg = "Wrong planarity check result. Should be planar." | |
39 else: | |
40 msg = "Wrong planarity check result. Should be non-planar." | |
41 | |
42 # check if the result is as expected | |
43 assert is_planar == is_planar_lr, msg | |
44 assert is_planar == is_planar_lr_rec, msg | |
45 | |
46 if is_planar_lr: | |
47 # check embedding | |
48 check_embedding(G, result) | |
49 check_embedding(G, result_rec) | |
50 else: | |
51 # check counter example | |
52 check_counterexample(G, result) | |
53 check_counterexample(G, result_rec) | |
54 | |
55 def test_simple_planar_graph(self): | |
56 e = [ | |
57 (1, 2), | |
58 (2, 3), | |
59 (3, 4), | |
60 (4, 6), | |
61 (6, 7), | |
62 (7, 1), | |
63 (1, 5), | |
64 (5, 2), | |
65 (2, 4), | |
66 (4, 5), | |
67 (5, 7), | |
68 ] | |
69 self.check_graph(nx.Graph(e), is_planar=True) | |
70 | |
71 def test_planar_with_selfloop(self): | |
72 e = [ | |
73 (1, 1), | |
74 (2, 2), | |
75 (3, 3), | |
76 (4, 4), | |
77 (5, 5), | |
78 (1, 2), | |
79 (1, 3), | |
80 (1, 5), | |
81 (2, 5), | |
82 (2, 4), | |
83 (3, 4), | |
84 (3, 5), | |
85 (4, 5), | |
86 ] | |
87 self.check_graph(nx.Graph(e), is_planar=True) | |
88 | |
89 def test_k3_3(self): | |
90 self.check_graph(nx.complete_bipartite_graph(3, 3), is_planar=False) | |
91 | |
92 def test_k5(self): | |
93 self.check_graph(nx.complete_graph(5), is_planar=False) | |
94 | |
95 def test_multiple_components_planar(self): | |
96 e = [(1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4)] | |
97 self.check_graph(nx.Graph(e), is_planar=True) | |
98 | |
99 def test_multiple_components_non_planar(self): | |
100 G = nx.complete_graph(5) | |
101 # add another planar component to the non planar component | |
102 # G stays non planar | |
103 G.add_edges_from([(6, 7), (7, 8), (8, 6)]) | |
104 self.check_graph(G, is_planar=False) | |
105 | |
106 def test_non_planar_with_selfloop(self): | |
107 G = nx.complete_graph(5) | |
108 # add self loops | |
109 for i in range(5): | |
110 G.add_edge(i, i) | |
111 self.check_graph(G, is_planar=False) | |
112 | |
113 def test_non_planar1(self): | |
114 # tests a graph that has no subgraph directly isomorph to K5 or K3_3 | |
115 e = [ | |
116 (1, 5), | |
117 (1, 6), | |
118 (1, 7), | |
119 (2, 6), | |
120 (2, 3), | |
121 (3, 5), | |
122 (3, 7), | |
123 (4, 5), | |
124 (4, 6), | |
125 (4, 7), | |
126 ] | |
127 self.check_graph(nx.Graph(e), is_planar=False) | |
128 | |
129 def test_loop(self): | |
130 # test a graph with a selfloop | |
131 e = [(1, 2), (2, 2)] | |
132 G = nx.Graph(e) | |
133 self.check_graph(G, is_planar=True) | |
134 | |
135 def test_comp(self): | |
136 # test multiple component graph | |
137 e = [(1, 2), (3, 4)] | |
138 G = nx.Graph(e) | |
139 G.remove_edge(1, 2) | |
140 self.check_graph(G, is_planar=True) | |
141 | |
142 def test_goldner_harary(self): | |
143 # test goldner-harary graph (a maximal planar graph) | |
144 e = [ | |
145 (1, 2), | |
146 (1, 3), | |
147 (1, 4), | |
148 (1, 5), | |
149 (1, 7), | |
150 (1, 8), | |
151 (1, 10), | |
152 (1, 11), | |
153 (2, 3), | |
154 (2, 4), | |
155 (2, 6), | |
156 (2, 7), | |
157 (2, 9), | |
158 (2, 10), | |
159 (2, 11), | |
160 (3, 4), | |
161 (4, 5), | |
162 (4, 6), | |
163 (4, 7), | |
164 (5, 7), | |
165 (6, 7), | |
166 (7, 8), | |
167 (7, 9), | |
168 (7, 10), | |
169 (8, 10), | |
170 (9, 10), | |
171 (10, 11), | |
172 ] | |
173 G = nx.Graph(e) | |
174 self.check_graph(G, is_planar=True) | |
175 | |
176 def test_planar_multigraph(self): | |
177 G = nx.MultiGraph([(1, 2), (1, 2), (1, 2), (1, 2), (2, 3), (3, 1)]) | |
178 self.check_graph(G, is_planar=True) | |
179 | |
180 def test_non_planar_multigraph(self): | |
181 G = nx.MultiGraph(nx.complete_graph(5)) | |
182 G.add_edges_from([(1, 2)] * 5) | |
183 self.check_graph(G, is_planar=False) | |
184 | |
185 def test_planar_digraph(self): | |
186 G = nx.DiGraph([(1, 2), (2, 3), (2, 4), (4, 1), (4, 2), (1, 4), (3, 2)]) | |
187 self.check_graph(G, is_planar=True) | |
188 | |
189 def test_non_planar_digraph(self): | |
190 G = nx.DiGraph(nx.complete_graph(5)) | |
191 G.remove_edge(1, 2) | |
192 G.remove_edge(4, 1) | |
193 self.check_graph(G, is_planar=False) | |
194 | |
195 def test_single_component(self): | |
196 # Test a graph with only a single node | |
197 G = nx.Graph() | |
198 G.add_node(1) | |
199 self.check_graph(G, is_planar=True) | |
200 | |
201 def test_graph1(self): | |
202 G = nx.OrderedGraph( | |
203 [ | |
204 (3, 10), | |
205 (2, 13), | |
206 (1, 13), | |
207 (7, 11), | |
208 (0, 8), | |
209 (8, 13), | |
210 (0, 2), | |
211 (0, 7), | |
212 (0, 10), | |
213 (1, 7), | |
214 ] | |
215 ) | |
216 self.check_graph(G, is_planar=True) | |
217 | |
218 def test_graph2(self): | |
219 G = nx.OrderedGraph( | |
220 [ | |
221 (1, 2), | |
222 (4, 13), | |
223 (0, 13), | |
224 (4, 5), | |
225 (7, 10), | |
226 (1, 7), | |
227 (0, 3), | |
228 (2, 6), | |
229 (5, 6), | |
230 (7, 13), | |
231 (4, 8), | |
232 (0, 8), | |
233 (0, 9), | |
234 (2, 13), | |
235 (6, 7), | |
236 (3, 6), | |
237 (2, 8), | |
238 ] | |
239 ) | |
240 self.check_graph(G, is_planar=False) | |
241 | |
242 def test_graph3(self): | |
243 G = nx.OrderedGraph( | |
244 [ | |
245 (0, 7), | |
246 (3, 11), | |
247 (3, 4), | |
248 (8, 9), | |
249 (4, 11), | |
250 (1, 7), | |
251 (1, 13), | |
252 (1, 11), | |
253 (3, 5), | |
254 (5, 7), | |
255 (1, 3), | |
256 (0, 4), | |
257 (5, 11), | |
258 (5, 13), | |
259 ] | |
260 ) | |
261 self.check_graph(G, is_planar=False) | |
262 | |
263 def test_counterexample_planar(self): | |
264 with pytest.raises(nx.NetworkXException): | |
265 # Try to get a counterexample of a planar graph | |
266 G = nx.Graph() | |
267 G.add_node(1) | |
268 get_counterexample(G) | |
269 | |
270 def test_counterexample_planar_recursive(self): | |
271 with pytest.raises(nx.NetworkXException): | |
272 # Try to get a counterexample of a planar graph | |
273 G = nx.Graph() | |
274 G.add_node(1) | |
275 get_counterexample_recursive(G) | |
276 | |
277 | |
278 def check_embedding(G, embedding): | |
279 """Raises an exception if the combinatorial embedding is not correct | |
280 | |
281 Parameters | |
282 ---------- | |
283 G : NetworkX graph | |
284 embedding : a dict mapping nodes to a list of edges | |
285 This specifies the ordering of the outgoing edges from a node for | |
286 a combinatorial embedding | |
287 | |
288 Notes | |
289 ----- | |
290 Checks the following things: | |
291 - The type of the embedding is correct | |
292 - The nodes and edges match the original graph | |
293 - Every half edge has its matching opposite half edge | |
294 - No intersections of edges (checked by Euler's formula) | |
295 """ | |
296 | |
297 if not isinstance(embedding, nx.PlanarEmbedding): | |
298 raise nx.NetworkXException("Bad embedding. Not of type nx.PlanarEmbedding") | |
299 | |
300 # Check structure | |
301 embedding.check_structure() | |
302 | |
303 # Check that graphs are equivalent | |
304 | |
305 assert set(G.nodes) == set( | |
306 embedding.nodes | |
307 ), "Bad embedding. Nodes don't match the original graph." | |
308 | |
309 # Check that the edges are equal | |
310 g_edges = set() | |
311 for edge in G.edges: | |
312 if edge[0] != edge[1]: | |
313 g_edges.add((edge[0], edge[1])) | |
314 g_edges.add((edge[1], edge[0])) | |
315 assert g_edges == set( | |
316 embedding.edges | |
317 ), "Bad embedding. Edges don't match the original graph." | |
318 | |
319 | |
320 def check_counterexample(G, sub_graph): | |
321 """Raises an exception if the counterexample is wrong. | |
322 | |
323 Parameters | |
324 ---------- | |
325 G : NetworkX graph | |
326 subdivision_nodes : set | |
327 A set of nodes inducing a subgraph as a counterexample | |
328 """ | |
329 # 1. Create the sub graph | |
330 sub_graph = nx.Graph(sub_graph) | |
331 | |
332 # 2. Remove self loops | |
333 for u in sub_graph: | |
334 if sub_graph.has_edge(u, u): | |
335 sub_graph.remove_edge(u, u) | |
336 | |
337 # keep track of nodes we might need to contract | |
338 contract = list(sub_graph) | |
339 | |
340 # 3. Contract Edges | |
341 while len(contract) > 0: | |
342 contract_node = contract.pop() | |
343 if contract_node not in sub_graph: | |
344 # Node was already contracted | |
345 continue | |
346 degree = sub_graph.degree[contract_node] | |
347 # Check if we can remove the node | |
348 if degree == 2: | |
349 # Get the two neighbors | |
350 neighbors = iter(sub_graph[contract_node]) | |
351 u = next(neighbors) | |
352 v = next(neighbors) | |
353 # Save nodes for later | |
354 contract.append(u) | |
355 contract.append(v) | |
356 # Contract edge | |
357 sub_graph.remove_node(contract_node) | |
358 sub_graph.add_edge(u, v) | |
359 | |
360 # 4. Check for isomorphism with K5 or K3_3 graphs | |
361 if len(sub_graph) == 5: | |
362 if not nx.is_isomorphic(nx.complete_graph(5), sub_graph): | |
363 raise nx.NetworkXException("Bad counter example.") | |
364 elif len(sub_graph) == 6: | |
365 if not nx.is_isomorphic(nx.complete_bipartite_graph(3, 3), sub_graph): | |
366 raise nx.NetworkXException("Bad counter example.") | |
367 else: | |
368 raise nx.NetworkXException("Bad counter example.") | |
369 | |
370 | |
371 class TestPlanarEmbeddingClass: | |
372 def test_get_data(self): | |
373 embedding = self.get_star_embedding(3) | |
374 data = embedding.get_data() | |
375 data_cmp = {0: [2, 1], 1: [0], 2: [0]} | |
376 assert data == data_cmp | |
377 | |
378 def test_missing_edge_orientation(self): | |
379 with pytest.raises(nx.NetworkXException): | |
380 embedding = nx.PlanarEmbedding() | |
381 embedding.add_edge(1, 2) | |
382 embedding.add_edge(2, 1) | |
383 # Invalid structure because the orientation of the edge was not set | |
384 embedding.check_structure() | |
385 | |
386 def test_invalid_edge_orientation(self): | |
387 with pytest.raises(nx.NetworkXException): | |
388 embedding = nx.PlanarEmbedding() | |
389 embedding.add_half_edge_first(1, 2) | |
390 embedding.add_half_edge_first(2, 1) | |
391 embedding.add_edge(1, 3) | |
392 embedding.check_structure() | |
393 | |
394 def test_missing_half_edge(self): | |
395 with pytest.raises(nx.NetworkXException): | |
396 embedding = nx.PlanarEmbedding() | |
397 embedding.add_half_edge_first(1, 2) | |
398 # Invalid structure because other half edge is missing | |
399 embedding.check_structure() | |
400 | |
401 def test_not_fulfilling_euler_formula(self): | |
402 with pytest.raises(nx.NetworkXException): | |
403 embedding = nx.PlanarEmbedding() | |
404 for i in range(5): | |
405 for j in range(5): | |
406 if i != j: | |
407 embedding.add_half_edge_first(i, j) | |
408 embedding.check_structure() | |
409 | |
410 def test_missing_reference(self): | |
411 with pytest.raises(nx.NetworkXException): | |
412 embedding = nx.PlanarEmbedding() | |
413 embedding.add_half_edge_cw(1, 2, 3) | |
414 | |
415 def test_connect_components(self): | |
416 embedding = nx.PlanarEmbedding() | |
417 embedding.connect_components(1, 2) | |
418 | |
419 def test_successful_face_traversal(self): | |
420 embedding = nx.PlanarEmbedding() | |
421 embedding.add_half_edge_first(1, 2) | |
422 embedding.add_half_edge_first(2, 1) | |
423 face = embedding.traverse_face(1, 2) | |
424 assert face == [1, 2] | |
425 | |
426 def test_unsuccessful_face_traversal(self): | |
427 with pytest.raises(nx.NetworkXException): | |
428 embedding = nx.PlanarEmbedding() | |
429 embedding.add_edge(1, 2, ccw=2, cw=3) | |
430 embedding.add_edge(2, 1, ccw=1, cw=3) | |
431 embedding.traverse_face(1, 2) | |
432 | |
433 @staticmethod | |
434 def get_star_embedding(n): | |
435 embedding = nx.PlanarEmbedding() | |
436 for i in range(1, n): | |
437 embedding.add_half_edge_first(0, i) | |
438 embedding.add_half_edge_first(i, 0) | |
439 return embedding |