Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/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 networkx as nx | |
2 from collections import defaultdict | |
3 | |
4 | |
5 __all__ = ["combinatorial_embedding_to_pos"] | |
6 | |
7 | |
8 def combinatorial_embedding_to_pos(embedding, fully_triangulate=False): | |
9 """Assigns every node a (x, y) position based on the given embedding | |
10 | |
11 The algorithm iteratively inserts nodes of the input graph in a certain | |
12 order and rearranges previously inserted nodes so that the planar drawing | |
13 stays valid. This is done efficiently by only maintaining relative | |
14 positions during the node placements and calculating the absolute positions | |
15 at the end. For more information see [1]_. | |
16 | |
17 Parameters | |
18 ---------- | |
19 embedding : nx.PlanarEmbedding | |
20 This defines the order of the edges | |
21 | |
22 fully_triangulate : bool | |
23 If set to True the algorithm adds edges to a copy of the input | |
24 embedding and makes it chordal. | |
25 | |
26 Returns | |
27 ------- | |
28 pos : dict | |
29 Maps each node to a tuple that defines the (x, y) position | |
30 | |
31 References | |
32 ---------- | |
33 .. [1] M. Chrobak and T.H. Payne: | |
34 A Linear-time Algorithm for Drawing a Planar Graph on a Grid 1989 | |
35 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.6677 | |
36 | |
37 """ | |
38 if len(embedding.nodes()) < 4: | |
39 # Position the node in any triangle | |
40 default_positions = [(0, 0), (2, 0), (1, 1)] | |
41 pos = {} | |
42 for i, v in enumerate(embedding.nodes()): | |
43 pos[v] = default_positions[i] | |
44 return pos | |
45 | |
46 embedding, outer_face = triangulate_embedding(embedding, fully_triangulate) | |
47 | |
48 # The following dicts map a node to another node | |
49 # If a node is not in the key set it means that the node is not yet in G_k | |
50 # If a node maps to None then the corresponding subtree does not exist | |
51 left_t_child = {} | |
52 right_t_child = {} | |
53 | |
54 # The following dicts map a node to an integer | |
55 delta_x = {} | |
56 y_coordinate = {} | |
57 | |
58 node_list = get_canonical_ordering(embedding, outer_face) | |
59 | |
60 # 1. Phase: Compute relative positions | |
61 | |
62 # Initialization | |
63 v1, v2, v3 = node_list[0][0], node_list[1][0], node_list[2][0] | |
64 | |
65 delta_x[v1] = 0 | |
66 y_coordinate[v1] = 0 | |
67 right_t_child[v1] = v3 | |
68 left_t_child[v1] = None | |
69 | |
70 delta_x[v2] = 1 | |
71 y_coordinate[v2] = 0 | |
72 right_t_child[v2] = None | |
73 left_t_child[v2] = None | |
74 | |
75 delta_x[v3] = 1 | |
76 y_coordinate[v3] = 1 | |
77 right_t_child[v3] = v2 | |
78 left_t_child[v3] = None | |
79 | |
80 for k in range(3, len(node_list)): | |
81 vk, contour_neighbors = node_list[k] | |
82 wp = contour_neighbors[0] | |
83 wp1 = contour_neighbors[1] | |
84 wq = contour_neighbors[-1] | |
85 wq1 = contour_neighbors[-2] | |
86 adds_mult_tri = len(contour_neighbors) > 2 | |
87 | |
88 # Stretch gaps: | |
89 delta_x[wp1] += 1 | |
90 delta_x[wq] += 1 | |
91 | |
92 delta_x_wp_wq = sum(delta_x[x] for x in contour_neighbors[1:]) | |
93 | |
94 # Adjust offsets | |
95 delta_x[vk] = (-y_coordinate[wp] + delta_x_wp_wq + y_coordinate[wq]) // 2 | |
96 y_coordinate[vk] = (y_coordinate[wp] + delta_x_wp_wq + y_coordinate[wq]) // 2 | |
97 delta_x[wq] = delta_x_wp_wq - delta_x[vk] | |
98 if adds_mult_tri: | |
99 delta_x[wp1] -= delta_x[vk] | |
100 | |
101 # Install v_k: | |
102 right_t_child[wp] = vk | |
103 right_t_child[vk] = wq | |
104 if adds_mult_tri: | |
105 left_t_child[vk] = wp1 | |
106 right_t_child[wq1] = None | |
107 else: | |
108 left_t_child[vk] = None | |
109 | |
110 # 2. Phase: Set absolute positions | |
111 pos = dict() | |
112 pos[v1] = (0, y_coordinate[v1]) | |
113 remaining_nodes = [v1] | |
114 while remaining_nodes: | |
115 parent_node = remaining_nodes.pop() | |
116 | |
117 # Calculate position for left child | |
118 set_position( | |
119 parent_node, left_t_child, remaining_nodes, delta_x, y_coordinate, pos | |
120 ) | |
121 # Calculate position for right child | |
122 set_position( | |
123 parent_node, right_t_child, remaining_nodes, delta_x, y_coordinate, pos | |
124 ) | |
125 return pos | |
126 | |
127 | |
128 def set_position(parent, tree, remaining_nodes, delta_x, y_coordinate, pos): | |
129 """Helper method to calculate the absolute position of nodes.""" | |
130 child = tree[parent] | |
131 parent_node_x = pos[parent][0] | |
132 if child is not None: | |
133 # Calculate pos of child | |
134 child_x = parent_node_x + delta_x[child] | |
135 pos[child] = (child_x, y_coordinate[child]) | |
136 # Remember to calculate pos of its children | |
137 remaining_nodes.append(child) | |
138 | |
139 | |
140 def get_canonical_ordering(embedding, outer_face): | |
141 """Returns a canonical ordering of the nodes | |
142 | |
143 The canonical ordering of nodes (v1, ..., vn) must fulfill the following | |
144 conditions: | |
145 (See Lemma 1 in [2]_) | |
146 | |
147 - For the subgraph G_k of the input graph induced by v1, ..., vk it holds: | |
148 - 2-connected | |
149 - internally triangulated | |
150 - the edge (v1, v2) is part of the outer face | |
151 - For a node v(k+1) the following holds: | |
152 - The node v(k+1) is part of the outer face of G_k | |
153 - It has at least two neighbors in G_k | |
154 - All neighbors of v(k+1) in G_k lie consecutively on the outer face of | |
155 G_k (excluding the edge (v1, v2)). | |
156 | |
157 The algorithm used here starts with G_n (containing all nodes). It first | |
158 selects the nodes v1 and v2. And then tries to find the order of the other | |
159 nodes by checking which node can be removed in order to fulfill the | |
160 conditions mentioned above. This is done by calculating the number of | |
161 chords of nodes on the outer face. For more information see [1]_. | |
162 | |
163 Parameters | |
164 ---------- | |
165 embedding : nx.PlanarEmbedding | |
166 The embedding must be triangulated | |
167 outer_face : list | |
168 The nodes on the outer face of the graph | |
169 | |
170 Returns | |
171 ------- | |
172 ordering : list | |
173 A list of tuples `(vk, wp_wq)`. Here `vk` is the node at this position | |
174 in the canonical ordering. The element `wp_wq` is a list of nodes that | |
175 make up the outer face of G_k. | |
176 | |
177 References | |
178 ---------- | |
179 .. [1] Steven Chaplick. | |
180 Canonical Orders of Planar Graphs and (some of) Their Applications 2015 | |
181 https://wuecampus2.uni-wuerzburg.de/moodle/pluginfile.php/545727/mod_resource/content/0/vg-ss15-vl03-canonical-orders-druckversion.pdf | |
182 .. [2] M. Chrobak and T.H. Payne: | |
183 A Linear-time Algorithm for Drawing a Planar Graph on a Grid 1989 | |
184 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.6677 | |
185 | |
186 """ | |
187 v1 = outer_face[0] | |
188 v2 = outer_face[1] | |
189 chords = defaultdict(int) # Maps nodes to the number of their chords | |
190 marked_nodes = set() | |
191 ready_to_pick = set(outer_face) | |
192 | |
193 # Initialize outer_face_ccw_nbr (do not include v1 -> v2) | |
194 outer_face_ccw_nbr = {} | |
195 prev_nbr = v2 | |
196 for idx in range(2, len(outer_face)): | |
197 outer_face_ccw_nbr[prev_nbr] = outer_face[idx] | |
198 prev_nbr = outer_face[idx] | |
199 outer_face_ccw_nbr[prev_nbr] = v1 | |
200 | |
201 # Initialize outer_face_cw_nbr (do not include v2 -> v1) | |
202 outer_face_cw_nbr = {} | |
203 prev_nbr = v1 | |
204 for idx in range(len(outer_face) - 1, 0, -1): | |
205 outer_face_cw_nbr[prev_nbr] = outer_face[idx] | |
206 prev_nbr = outer_face[idx] | |
207 | |
208 def is_outer_face_nbr(x, y): | |
209 if x not in outer_face_ccw_nbr: | |
210 return outer_face_cw_nbr[x] == y | |
211 if x not in outer_face_cw_nbr: | |
212 return outer_face_ccw_nbr[x] == y | |
213 return outer_face_ccw_nbr[x] == y or outer_face_cw_nbr[x] == y | |
214 | |
215 def is_on_outer_face(x): | |
216 return x not in marked_nodes and (x in outer_face_ccw_nbr.keys() or x == v1) | |
217 | |
218 # Initialize number of chords | |
219 for v in outer_face: | |
220 for nbr in embedding.neighbors_cw_order(v): | |
221 if is_on_outer_face(nbr) and not is_outer_face_nbr(v, nbr): | |
222 chords[v] += 1 | |
223 ready_to_pick.discard(v) | |
224 | |
225 # Initialize canonical_ordering | |
226 canonical_ordering = [None] * len(embedding.nodes()) # type: list | |
227 canonical_ordering[0] = (v1, []) | |
228 canonical_ordering[1] = (v2, []) | |
229 ready_to_pick.discard(v1) | |
230 ready_to_pick.discard(v2) | |
231 | |
232 for k in range(len(embedding.nodes()) - 1, 1, -1): | |
233 # 1. Pick v from ready_to_pick | |
234 v = ready_to_pick.pop() | |
235 marked_nodes.add(v) | |
236 | |
237 # v has exactly two neighbors on the outer face (wp and wq) | |
238 wp = None | |
239 wq = None | |
240 # Iterate over neighbors of v to find wp and wq | |
241 nbr_iterator = iter(embedding.neighbors_cw_order(v)) | |
242 while True: | |
243 nbr = next(nbr_iterator) | |
244 if nbr in marked_nodes: | |
245 # Only consider nodes that are not yet removed | |
246 continue | |
247 if is_on_outer_face(nbr): | |
248 # nbr is either wp or wq | |
249 if nbr == v1: | |
250 wp = v1 | |
251 elif nbr == v2: | |
252 wq = v2 | |
253 else: | |
254 if outer_face_cw_nbr[nbr] == v: | |
255 # nbr is wp | |
256 wp = nbr | |
257 else: | |
258 # nbr is wq | |
259 wq = nbr | |
260 if wp is not None and wq is not None: | |
261 # We don't need to iterate any further | |
262 break | |
263 | |
264 # Obtain new nodes on outer face (neighbors of v from wp to wq) | |
265 wp_wq = [wp] | |
266 nbr = wp | |
267 while nbr != wq: | |
268 # Get next next neighbor (clockwise on the outer face) | |
269 next_nbr = embedding[v][nbr]["ccw"] | |
270 wp_wq.append(next_nbr) | |
271 # Update outer face | |
272 outer_face_cw_nbr[nbr] = next_nbr | |
273 outer_face_ccw_nbr[next_nbr] = nbr | |
274 # Move to next neighbor of v | |
275 nbr = next_nbr | |
276 | |
277 if len(wp_wq) == 2: | |
278 # There was a chord between wp and wq, decrease number of chords | |
279 chords[wp] -= 1 | |
280 if chords[wp] == 0: | |
281 ready_to_pick.add(wp) | |
282 chords[wq] -= 1 | |
283 if chords[wq] == 0: | |
284 ready_to_pick.add(wq) | |
285 else: | |
286 # Update all chords involving w_(p+1) to w_(q-1) | |
287 new_face_nodes = set(wp_wq[1:-1]) | |
288 for w in new_face_nodes: | |
289 # If we do not find a chord for w later we can pick it next | |
290 ready_to_pick.add(w) | |
291 for nbr in embedding.neighbors_cw_order(w): | |
292 if is_on_outer_face(nbr) and not is_outer_face_nbr(w, nbr): | |
293 # There is a chord involving w | |
294 chords[w] += 1 | |
295 ready_to_pick.discard(w) | |
296 if nbr not in new_face_nodes: | |
297 # Also increase chord for the neighbor | |
298 # We only iterator over new_face_nodes | |
299 chords[nbr] += 1 | |
300 ready_to_pick.discard(nbr) | |
301 # Set the canonical ordering node and the list of contour neighbors | |
302 canonical_ordering[k] = (v, wp_wq) | |
303 | |
304 return canonical_ordering | |
305 | |
306 | |
307 def triangulate_face(embedding, v1, v2): | |
308 """Triangulates the face given by half edge (v, w) | |
309 | |
310 Parameters | |
311 ---------- | |
312 embedding : nx.PlanarEmbedding | |
313 v1 : node | |
314 The half-edge (v1, v2) belongs to the face that gets triangulated | |
315 v2 : node | |
316 """ | |
317 _, v3 = embedding.next_face_half_edge(v1, v2) | |
318 _, v4 = embedding.next_face_half_edge(v2, v3) | |
319 if v1 == v2 or v1 == v3: | |
320 # The component has less than 3 nodes | |
321 return | |
322 while v1 != v4: | |
323 # Add edge if not already present on other side | |
324 if embedding.has_edge(v1, v3): | |
325 # Cannot triangulate at this position | |
326 v1, v2, v3 = v2, v3, v4 | |
327 else: | |
328 # Add edge for triangulation | |
329 embedding.add_half_edge_cw(v1, v3, v2) | |
330 embedding.add_half_edge_ccw(v3, v1, v2) | |
331 v1, v2, v3 = v1, v3, v4 | |
332 # Get next node | |
333 _, v4 = embedding.next_face_half_edge(v2, v3) | |
334 | |
335 | |
336 def triangulate_embedding(embedding, fully_triangulate=True): | |
337 """Triangulates the embedding. | |
338 | |
339 Traverses faces of the embedding and adds edges to a copy of the | |
340 embedding to triangulate it. | |
341 The method also ensures that the resulting graph is 2-connected by adding | |
342 edges if the same vertex is contained twice on a path around a face. | |
343 | |
344 Parameters | |
345 ---------- | |
346 embedding : nx.PlanarEmbedding | |
347 The input graph must contain at least 3 nodes. | |
348 | |
349 fully_triangulate : bool | |
350 If set to False the face with the most nodes is chooses as outer face. | |
351 This outer face does not get triangulated. | |
352 | |
353 Returns | |
354 ------- | |
355 (embedding, outer_face) : (nx.PlanarEmbedding, list) tuple | |
356 The element `embedding` is a new embedding containing all edges from | |
357 the input embedding and the additional edges to triangulate the graph. | |
358 The element `outer_face` is a list of nodes that lie on the outer face. | |
359 If the graph is fully triangulated these are three arbitrary connected | |
360 nodes. | |
361 | |
362 """ | |
363 if len(embedding.nodes) <= 1: | |
364 return embedding, list(embedding.nodes) | |
365 embedding = nx.PlanarEmbedding(embedding) | |
366 | |
367 # Get a list with a node for each connected component | |
368 component_nodes = [next(iter(x)) for x in nx.connected_components(embedding)] | |
369 | |
370 # 1. Make graph a single component (add edge between components) | |
371 for i in range(len(component_nodes) - 1): | |
372 v1 = component_nodes[i] | |
373 v2 = component_nodes[i + 1] | |
374 embedding.connect_components(v1, v2) | |
375 | |
376 # 2. Calculate faces, ensure 2-connectedness and determine outer face | |
377 outer_face = [] # A face with the most number of nodes | |
378 face_list = [] | |
379 edges_visited = set() # Used to keep track of already visited faces | |
380 for v in embedding.nodes(): | |
381 for w in embedding.neighbors_cw_order(v): | |
382 new_face = make_bi_connected(embedding, v, w, edges_visited) | |
383 if new_face: | |
384 # Found a new face | |
385 face_list.append(new_face) | |
386 if len(new_face) > len(outer_face): | |
387 # The face is a candidate to be the outer face | |
388 outer_face = new_face | |
389 | |
390 # 3. Triangulate (internal) faces | |
391 for face in face_list: | |
392 if face is not outer_face or fully_triangulate: | |
393 # Triangulate this face | |
394 triangulate_face(embedding, face[0], face[1]) | |
395 | |
396 if fully_triangulate: | |
397 v1 = outer_face[0] | |
398 v2 = outer_face[1] | |
399 v3 = embedding[v2][v1]["ccw"] | |
400 outer_face = [v1, v2, v3] | |
401 | |
402 return embedding, outer_face | |
403 | |
404 | |
405 def make_bi_connected(embedding, starting_node, outgoing_node, edges_counted): | |
406 """Triangulate a face and make it 2-connected | |
407 | |
408 This method also adds all edges on the face to `edges_counted`. | |
409 | |
410 Parameters | |
411 ---------- | |
412 embedding: nx.PlanarEmbedding | |
413 The embedding that defines the faces | |
414 starting_node : node | |
415 A node on the face | |
416 outgoing_node : node | |
417 A node such that the half edge (starting_node, outgoing_node) belongs | |
418 to the face | |
419 edges_counted: set | |
420 Set of all half-edges that belong to a face that have been visited | |
421 | |
422 Returns | |
423 ------- | |
424 face_nodes: list | |
425 A list of all nodes at the border of this face | |
426 """ | |
427 | |
428 # Check if the face has already been calculated | |
429 if (starting_node, outgoing_node) in edges_counted: | |
430 # This face was already counted | |
431 return [] | |
432 edges_counted.add((starting_node, outgoing_node)) | |
433 | |
434 # Add all edges to edges_counted which have this face to their left | |
435 v1 = starting_node | |
436 v2 = outgoing_node | |
437 face_list = [starting_node] # List of nodes around the face | |
438 face_set = set(face_list) # Set for faster queries | |
439 _, v3 = embedding.next_face_half_edge(v1, v2) | |
440 | |
441 # Move the nodes v1, v2, v3 around the face: | |
442 while v2 != starting_node or v3 != outgoing_node: | |
443 if v1 == v2: | |
444 raise nx.NetworkXException("Invalid half-edge") | |
445 # cycle is not completed yet | |
446 if v2 in face_set: | |
447 # v2 encountered twice: Add edge to ensure 2-connectedness | |
448 embedding.add_half_edge_cw(v1, v3, v2) | |
449 embedding.add_half_edge_ccw(v3, v1, v2) | |
450 edges_counted.add((v2, v3)) | |
451 edges_counted.add((v3, v1)) | |
452 v2 = v1 | |
453 else: | |
454 face_set.add(v2) | |
455 face_list.append(v2) | |
456 | |
457 # set next edge | |
458 v1 = v2 | |
459 v2, v3 = embedding.next_face_half_edge(v2, v3) | |
460 | |
461 # remember that this edge has been counted | |
462 edges_counted.add((v1, v2)) | |
463 | |
464 return face_list |