1import networkx as nx 2from collections import defaultdict 3 4 5__all__ = ["combinatorial_embedding_to_pos"] 6 7 8def 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 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) 138 139 140def 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 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 307def 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 336def 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 405def 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 465