Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/planar_drawing.py: 4%
210 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1from collections import defaultdict
3import networkx as nx
5__all__ = ["combinatorial_embedding_to_pos"]
8def combinatorial_embedding_to_pos(embedding, fully_triangulate=False):
9 """Assigns every node a (x, y) position based on the given embedding
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]_.
17 Parameters
18 ----------
19 embedding : nx.PlanarEmbedding
20 This defines the order of the edges
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.
26 Returns
27 -------
28 pos : dict
29 Maps each node to a tuple that defines the (x, y) position
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
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
46 embedding, outer_face = triangulate_embedding(embedding, fully_triangulate)
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 = {}
54 # The following dicts map a node to an integer
55 delta_x = {}
56 y_coordinate = {}
58 node_list = get_canonical_ordering(embedding, outer_face)
60 # 1. Phase: Compute relative positions
62 # Initialization
63 v1, v2, v3 = node_list[0][0], node_list[1][0], node_list[2][0]
65 delta_x[v1] = 0
66 y_coordinate[v1] = 0
67 right_t_child[v1] = v3
68 left_t_child[v1] = None
70 delta_x[v2] = 1
71 y_coordinate[v2] = 0
72 right_t_child[v2] = None
73 left_t_child[v2] = None
75 delta_x[v3] = 1
76 y_coordinate[v3] = 1
77 right_t_child[v3] = v2
78 left_t_child[v3] = None
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
88 # Stretch gaps:
89 delta_x[wp1] += 1
90 delta_x[wq] += 1
92 delta_x_wp_wq = sum(delta_x[x] for x in contour_neighbors[1:])
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]
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
110 # 2. Phase: Set absolute positions
111 pos = {}
112 pos[v1] = (0, y_coordinate[v1])
113 remaining_nodes = [v1]
114 while remaining_nodes:
115 parent_node = remaining_nodes.pop()
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
128def 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)
140def get_canonical_ordering(embedding, outer_face):
141 """Returns a canonical ordering of the nodes
143 The canonical ordering of nodes (v1, ..., vn) must fulfill the following
144 conditions:
145 (See Lemma 1 in [2]_)
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)).
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]_.
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
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.
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
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)
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
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]
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
215 def is_on_outer_face(x):
216 return x not in marked_nodes and (x in outer_face_ccw_nbr or x == v1)
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)
225 # Initialize canonical_ordering
226 canonical_ordering = [None] * len(embedding.nodes())
227 canonical_ordering[0] = (v1, [])
228 canonical_ordering[1] = (v2, [])
229 ready_to_pick.discard(v1)
230 ready_to_pick.discard(v2)
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)
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
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 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
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)
304 return canonical_ordering
307def triangulate_face(embedding, v1, v2):
308 """Triangulates the face given by half edge (v, w)
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 in (v2, 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)
336def triangulate_embedding(embedding, fully_triangulate=True):
337 """Triangulates the embedding.
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.
344 Parameters
345 ----------
346 embedding : nx.PlanarEmbedding
347 The input graph must contain at least 3 nodes.
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.
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.
362 """
363 if len(embedding.nodes) <= 1:
364 return embedding, list(embedding.nodes)
365 embedding = nx.PlanarEmbedding(embedding)
367 # Get a list with a node for each connected component
368 component_nodes = [next(iter(x)) for x in nx.connected_components(embedding)]
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)
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
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])
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]
402 return embedding, outer_face
405def make_bi_connected(embedding, starting_node, outgoing_node, edges_counted):
406 """Triangulate a face and make it 2-connected
408 This method also adds all edges on the face to `edges_counted`.
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
422 Returns
423 -------
424 face_nodes: list
425 A list of all nodes at the border of this face
426 """
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))
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)
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)
457 # set next edge
458 v1 = v2
459 v2, v3 = embedding.next_face_half_edge(v2, v3)
461 # remember that this edge has been counted
462 edges_counted.add((v1, v2))
464 return face_list