Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_planar_drawing.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.planar_drawing import triangulate_embedding | |
4 import math | |
5 | |
6 | |
7 def test_graph1(): | |
8 embedding_data = {0: [1, 2, 3], 1: [2, 0], 2: [3, 0, 1], 3: [2, 0]} | |
9 check_embedding_data(embedding_data) | |
10 | |
11 | |
12 def test_graph2(): | |
13 embedding_data = { | |
14 0: [8, 6], | |
15 1: [2, 6, 9], | |
16 2: [8, 1, 7, 9, 6, 4], | |
17 3: [9], | |
18 4: [2], | |
19 5: [6, 8], | |
20 6: [9, 1, 0, 5, 2], | |
21 7: [9, 2], | |
22 8: [0, 2, 5], | |
23 9: [1, 6, 2, 7, 3], | |
24 } | |
25 check_embedding_data(embedding_data) | |
26 | |
27 | |
28 def test_circle_graph(): | |
29 embedding_data = { | |
30 0: [1, 9], | |
31 1: [0, 2], | |
32 2: [1, 3], | |
33 3: [2, 4], | |
34 4: [3, 5], | |
35 5: [4, 6], | |
36 6: [5, 7], | |
37 7: [6, 8], | |
38 8: [7, 9], | |
39 9: [8, 0], | |
40 } | |
41 check_embedding_data(embedding_data) | |
42 | |
43 | |
44 def test_grid_graph(): | |
45 embedding_data = { | |
46 (0, 1): [(0, 0), (1, 1), (0, 2)], | |
47 (1, 2): [(1, 1), (2, 2), (0, 2)], | |
48 (0, 0): [(0, 1), (1, 0)], | |
49 (2, 1): [(2, 0), (2, 2), (1, 1)], | |
50 (1, 1): [(2, 1), (1, 2), (0, 1), (1, 0)], | |
51 (2, 0): [(1, 0), (2, 1)], | |
52 (2, 2): [(1, 2), (2, 1)], | |
53 (1, 0): [(0, 0), (2, 0), (1, 1)], | |
54 (0, 2): [(1, 2), (0, 1)], | |
55 } | |
56 check_embedding_data(embedding_data) | |
57 | |
58 | |
59 def test_one_node_graph(): | |
60 embedding_data = {0: []} | |
61 check_embedding_data(embedding_data) | |
62 | |
63 | |
64 def test_two_node_graph(): | |
65 embedding_data = {0: [1], 1: [0]} | |
66 check_embedding_data(embedding_data) | |
67 | |
68 | |
69 def test_three_node_graph(): | |
70 embedding_data = {0: [1, 2], 1: [0, 2], 2: [0, 1]} | |
71 check_embedding_data(embedding_data) | |
72 | |
73 | |
74 def test_multiple_component_graph1(): | |
75 embedding_data = {0: [], 1: []} | |
76 check_embedding_data(embedding_data) | |
77 | |
78 | |
79 def test_multiple_component_graph2(): | |
80 embedding_data = {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4, 5], 4: [3, 5], 5: [3, 4]} | |
81 check_embedding_data(embedding_data) | |
82 | |
83 | |
84 def test_invalid_half_edge(): | |
85 with pytest.raises(nx.NetworkXException): | |
86 embedding_data = {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2, 4], 4: [1, 2, 3]} | |
87 embedding = nx.PlanarEmbedding() | |
88 embedding.set_data(embedding_data) | |
89 nx.combinatorial_embedding_to_pos(embedding) | |
90 | |
91 | |
92 def test_triangulate_embedding1(): | |
93 embedding = nx.PlanarEmbedding() | |
94 embedding.add_node(1) | |
95 expected_embedding = {1: []} | |
96 check_triangulation(embedding, expected_embedding) | |
97 | |
98 | |
99 def test_triangulate_embedding2(): | |
100 embedding = nx.PlanarEmbedding() | |
101 embedding.connect_components(1, 2) | |
102 expected_embedding = {1: [2], 2: [1]} | |
103 check_triangulation(embedding, expected_embedding) | |
104 | |
105 | |
106 def check_triangulation(embedding, expected_embedding): | |
107 res_embedding, _ = triangulate_embedding(embedding, True) | |
108 assert ( | |
109 res_embedding.get_data() == expected_embedding | |
110 ), "Expected embedding incorrect" | |
111 res_embedding, _ = triangulate_embedding(embedding, False) | |
112 assert ( | |
113 res_embedding.get_data() == expected_embedding | |
114 ), "Expected embedding incorrect" | |
115 | |
116 | |
117 def check_embedding_data(embedding_data): | |
118 """Checks that the planar embedding of the input is correct""" | |
119 embedding = nx.PlanarEmbedding() | |
120 embedding.set_data(embedding_data) | |
121 pos_fully = nx.combinatorial_embedding_to_pos(embedding, False) | |
122 msg = "Planar drawing does not conform to the embedding (fully " "triangulation)" | |
123 assert planar_drawing_conforms_to_embedding(embedding, pos_fully), msg | |
124 check_edge_intersections(embedding, pos_fully) | |
125 pos_internally = nx.combinatorial_embedding_to_pos(embedding, True) | |
126 msg = "Planar drawing does not conform to the embedding (internal " "triangulation)" | |
127 assert planar_drawing_conforms_to_embedding(embedding, pos_internally), msg | |
128 check_edge_intersections(embedding, pos_internally) | |
129 | |
130 | |
131 def is_close(a, b, rel_tol=1e-09, abs_tol=0.0): | |
132 # Check if float numbers are basically equal, for python >=3.5 there is | |
133 # function for that in the standard library | |
134 return abs(a - b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol) | |
135 | |
136 | |
137 def point_in_between(a, b, p): | |
138 # checks if p is on the line between a and b | |
139 x1, y1 = a | |
140 x2, y2 = b | |
141 px, py = p | |
142 dist_1_2 = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) | |
143 dist_1_p = math.sqrt((x1 - px) ** 2 + (y1 - py) ** 2) | |
144 dist_2_p = math.sqrt((x2 - px) ** 2 + (y2 - py) ** 2) | |
145 return is_close(dist_1_p + dist_2_p, dist_1_2) | |
146 | |
147 | |
148 def check_edge_intersections(G, pos): | |
149 """Check all edges in G for intersections. | |
150 | |
151 Raises an exception if an intersection is found. | |
152 | |
153 Parameters | |
154 ---------- | |
155 G : NetworkX graph | |
156 pos : dict | |
157 Maps every node to a tuple (x, y) representing its position | |
158 | |
159 """ | |
160 for a, b in G.edges(): | |
161 for c, d in G.edges(): | |
162 # Check if end points are different | |
163 if a != c and b != d and b != c and a != d: | |
164 x1, y1 = pos[a] | |
165 x2, y2 = pos[b] | |
166 x3, y3 = pos[c] | |
167 x4, y4 = pos[d] | |
168 determinant = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4) | |
169 if determinant != 0: # the lines are not parallel | |
170 # calculate intersection point, see: | |
171 # https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection | |
172 px = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * ( | |
173 x3 * y4 - y3 * x4 | |
174 ) / float(determinant) | |
175 py = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * ( | |
176 x3 * y4 - y3 * x4 | |
177 ) / float(determinant) | |
178 | |
179 # Check if intersection lies between the points | |
180 if point_in_between(pos[a], pos[b], (px, py)) and point_in_between( | |
181 pos[c], pos[d], (px, py) | |
182 ): | |
183 msg = f"There is an intersection at {px},{py}" | |
184 raise nx.NetworkXException(msg) | |
185 | |
186 # Check overlap | |
187 msg = "A node lies on a edge connecting two other nodes" | |
188 if ( | |
189 point_in_between(pos[a], pos[b], pos[c]) | |
190 or point_in_between(pos[a], pos[b], pos[d]) | |
191 or point_in_between(pos[c], pos[d], pos[a]) | |
192 or point_in_between(pos[c], pos[d], pos[b]) | |
193 ): | |
194 raise nx.NetworkXException(msg) | |
195 # No edge intersection found | |
196 | |
197 | |
198 class Vector: | |
199 """Compare vectors by their angle without loss of precision | |
200 | |
201 All vectors in direction [0, 1] are the smallest. | |
202 The vectors grow in clockwise direction. | |
203 """ | |
204 | |
205 __slots__ = ["x", "y", "node", "quadrant"] | |
206 | |
207 def __init__(self, x, y, node): | |
208 self.x = x | |
209 self.y = y | |
210 self.node = node | |
211 if self.x >= 0 and self.y > 0: | |
212 self.quadrant = 1 | |
213 elif self.x > 0 and self.y <= 0: | |
214 self.quadrant = 2 | |
215 elif self.x <= 0 and self.y < 0: | |
216 self.quadrant = 3 | |
217 else: | |
218 self.quadrant = 4 | |
219 | |
220 def __eq__(self, other): | |
221 return self.quadrant == other.quadrant and self.x * other.y == self.y * other.x | |
222 | |
223 def __lt__(self, other): | |
224 if self.quadrant < other.quadrant: | |
225 return True | |
226 elif self.quadrant > other.quadrant: | |
227 return False | |
228 else: | |
229 return self.x * other.y < self.y * other.x | |
230 | |
231 def __ne__(self, other): | |
232 return not self == other | |
233 | |
234 def __le__(self, other): | |
235 return not other < self | |
236 | |
237 def __gt__(self, other): | |
238 return other < self | |
239 | |
240 def __ge__(self, other): | |
241 return not self < other | |
242 | |
243 | |
244 def planar_drawing_conforms_to_embedding(embedding, pos): | |
245 """Checks if pos conforms to the planar embedding | |
246 | |
247 Returns true iff the neighbors are actually oriented in the orientation | |
248 specified of the embedding | |
249 """ | |
250 for v in embedding: | |
251 nbr_vectors = [] | |
252 v_pos = pos[v] | |
253 for nbr in embedding[v]: | |
254 new_vector = Vector(pos[nbr][0] - v_pos[0], pos[nbr][1] - v_pos[1], nbr) | |
255 nbr_vectors.append(new_vector) | |
256 # Sort neighbors according to their phi angle | |
257 nbr_vectors.sort() | |
258 for idx, nbr_vector in enumerate(nbr_vectors): | |
259 cw_vector = nbr_vectors[(idx + 1) % len(nbr_vectors)] | |
260 ccw_vector = nbr_vectors[idx - 1] | |
261 if ( | |
262 embedding[v][nbr_vector.node]["cw"] != cw_vector.node | |
263 or embedding[v][nbr_vector.node]["ccw"] != ccw_vector.node | |
264 ): | |
265 return False | |
266 if cw_vector.node != nbr_vector.node and cw_vector == nbr_vector: | |
267 # Lines overlap | |
268 return False | |
269 if ccw_vector.node != nbr_vector.node and ccw_vector == nbr_vector: | |
270 # Lines overlap | |
271 return False | |
272 return True |