1from collections import defaultdict 2import networkx as nx 3 4__all__ = ["check_planarity", "PlanarEmbedding"] 5 6 7def check_planarity(G, counterexample=False): 8 """Check if a graph is planar and return a counterexample or an embedding. 9 10 A graph is planar iff it can be drawn in a plane without 11 any edge intersections. 12 13 Parameters 14 ---------- 15 G : NetworkX graph 16 counterexample : bool 17 A Kuratowski subgraph (to proof non planarity) is only returned if set 18 to true. 19 20 Returns 21 ------- 22 (is_planar, certificate) : (bool, NetworkX graph) tuple 23 is_planar is true if the graph is planar. 24 If the graph is planar `certificate` is a PlanarEmbedding 25 otherwise it is a Kuratowski subgraph. 26 27 Notes 28 ----- 29 A (combinatorial) embedding consists of cyclic orderings of the incident 30 edges at each vertex. Given such an embedding there are multiple approaches 31 discussed in literature to drawing the graph (subject to various 32 constraints, e.g. integer coordinates), see e.g. [2]. 33 34 The planarity check algorithm and extraction of the combinatorial embedding 35 is based on the Left-Right Planarity Test [1]. 36 37 A counterexample is only generated if the corresponding parameter is set, 38 because the complexity of the counterexample generation is higher. 39 40 References 41 ---------- 42 .. [1] Ulrik Brandes: 43 The Left-Right Planarity Test 44 2009 45 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.9208 46 .. [2] Takao Nishizeki, Md Saidur Rahman: 47 Planar graph drawing 48 Lecture Notes Series on Computing: Volume 12 49 2004 50 """ 51 52 planarity_state = LRPlanarity(G) 53 embedding = planarity_state.lr_planarity() 54 if embedding is None: 55 # graph is not planar 56 if counterexample: 57 return False, get_counterexample(G) 58 else: 59 return False, None 60 else: 61 # graph is planar 62 return True, embedding 63 64 65def check_planarity_recursive(G, counterexample=False): 66 """Recursive version of :meth:`check_planarity`.""" 67 planarity_state = LRPlanarity(G) 68 embedding = planarity_state.lr_planarity_recursive() 69 if embedding is None: 70 # graph is not planar 71 if counterexample: 72 return False, get_counterexample_recursive(G) 73 else: 74 return False, None 75 else: 76 # graph is planar 77 return True, embedding 78 79 80def get_counterexample(G): 81 """Obtains a Kuratowski subgraph. 82 83 Raises nx.NetworkXException if G is planar. 84 85 The function removes edges such that the graph is still not planar. 86 At some point the removal of any edge would make the graph planar. 87 This subgraph must be a Kuratowski subgraph. 88 89 Parameters 90 ---------- 91 G : NetworkX graph 92 93 Returns 94 ------- 95 subgraph : NetworkX graph 96 A Kuratowski subgraph that proves that G is not planar. 97 98 """ 99 # copy graph 100 G = nx.Graph(G) 101 102 if check_planarity(G)[0]: 103 raise nx.NetworkXException("G is planar - no counter example.") 104 105 # find Kuratowski subgraph 106 subgraph = nx.Graph() 107 for u in G: 108 nbrs = list(G[u]) 109 for v in nbrs: 110 G.remove_edge(u, v) 111 if check_planarity(G)[0]: 112 G.add_edge(u, v) 113 subgraph.add_edge(u, v) 114 115 return subgraph 116 117 118def get_counterexample_recursive(G): 119 """Recursive version of :meth:`get_counterexample`.""" 120 121 # copy graph 122 G = nx.Graph(G) 123 124 if check_planarity_recursive(G)[0]: 125 raise nx.NetworkXException("G is planar - no counter example.") 126 127 # find Kuratowski subgraph 128 subgraph = nx.Graph() 129 for u in G: 130 nbrs = list(G[u]) 131 for v in nbrs: 132 G.remove_edge(u, v) 133 if check_planarity_recursive(G)[0]: 134 G.add_edge(u, v) 135 subgraph.add_edge(u, v) 136 137 return subgraph 138 139 140class Interval: 141 """Represents a set of return edges. 142 143 All return edges in an interval induce a same constraint on the contained 144 edges, which means that all edges must either have a left orientation or 145 all edges must have a right orientation. 146 """ 147 148 def __init__(self, low=None, high=None): 149 self.low = low 150 self.high = high 151 152 def empty(self): 153 """Check if the interval is empty""" 154 return self.low is None and self.high is None 155 156 def copy(self): 157 """Returns a copy of this interval""" 158 return Interval(self.low, self.high) 159 160 def conflicting(self, b, planarity_state): 161 """Returns True if interval I conflicts with edge b""" 162 return ( 163 not self.empty() 164 and planarity_state.lowpt[self.high] > planarity_state.lowpt[b] 165 ) 166 167 168class ConflictPair: 169 """Represents a different constraint between two intervals. 170 171 The edges in the left interval must have a different orientation than 172 the one in the right interval. 173 """ 174 175 def __init__(self, left=Interval(), right=Interval()): 176 self.left = left 177 self.right = right 178 179 def swap(self): 180 """Swap left and right intervals""" 181 temp = self.left 182 self.left = self.right 183 self.right = temp 184 185 def lowest(self, planarity_state): 186 """Returns the lowest lowpoint of a conflict pair""" 187 if self.left.empty(): 188 return planarity_state.lowpt[self.right.low] 189 if self.right.empty(): 190 return planarity_state.lowpt[self.left.low] 191 return min( 192 planarity_state.lowpt[self.left.low], planarity_state.lowpt[self.right.low] 193 ) 194 195 196def top_of_stack(l): 197 """Returns the element on top of the stack.""" 198 if not l: 199 return None 200 return l[-1] 201 202 203class LRPlanarity: 204 """A class to maintain the state during planarity check.""" 205 206 __slots__ = [ 207 "G", 208 "roots", 209 "height", 210 "lowpt", 211 "lowpt2", 212 "nesting_depth", 213 "parent_edge", 214 "DG", 215 "adjs", 216 "ordered_adjs", 217 "ref", 218 "side", 219 "S", 220 "stack_bottom", 221 "lowpt_edge", 222 "left_ref", 223 "right_ref", 224 "embedding", 225 ] 226 227 def __init__(self, G): 228 # copy G without adding self-loops 229 self.G = nx.Graph() 230 self.G.add_nodes_from(G.nodes) 231 for e in G.edges: 232 if e[0] != e[1]: 233 self.G.add_edge(e[0], e[1]) 234 235 self.roots = [] 236 237 # distance from tree root 238 self.height = defaultdict(lambda: None) 239 240 self.lowpt = {} # height of lowest return point of an edge 241 self.lowpt2 = {} # height of second lowest return point 242 self.nesting_depth = {} # for nesting order 243 244 # None -> missing edge 245 self.parent_edge = defaultdict(lambda: None) 246 247 # oriented DFS graph 248 self.DG = nx.DiGraph() 249 self.DG.add_nodes_from(G.nodes) 250 251 self.adjs = {} 252 self.ordered_adjs = {} 253 254 self.ref = defaultdict(lambda: None) 255 self.side = defaultdict(lambda: 1) 256 257 # stack of conflict pairs 258 self.S = [] 259 self.stack_bottom = {} 260 self.lowpt_edge = {} 261 262 self.left_ref = {} 263 self.right_ref = {} 264 265 self.embedding = PlanarEmbedding() 266 267 def lr_planarity(self): 268 """Execute the LR planarity test. 269 270 Returns 271 ------- 272 embedding : dict 273 If the graph is planar an embedding is returned. Otherwise None. 274 """ 275 if self.G.order() > 2 and self.G.size() > 3 * self.G.order() - 6: 276 # graph is not planar 277 return None 278 279 # make adjacency lists for dfs 280 for v in self.G: 281 self.adjs[v] = list(self.G[v]) 282 283 # orientation of the graph by depth first search traversal 284 for v in self.G: 285 if self.height[v] is None: 286 self.height[v] = 0 287 self.roots.append(v) 288 self.dfs_orientation(v) 289 290 # Free no longer used variables 291 self.G = None 292 self.lowpt2 = None 293 self.adjs = None 294 295 # testing 296 for v in self.DG: # sort the adjacency lists by nesting depth 297 # note: this sorting leads to non linear time 298 self.ordered_adjs[v] = sorted( 299 self.DG[v], key=lambda x: self.nesting_depth[(v, x)] 300 ) 301 for v in self.roots: 302 if not self.dfs_testing(v): 303 return None 304 305 # Free no longer used variables 306 self.height = None 307 self.lowpt = None 308 self.S = None 309 self.stack_bottom = None 310 self.lowpt_edge = None 311 312 for e in self.DG.edges: 313 self.nesting_depth[e] = self.sign(e) * self.nesting_depth[e] 314 315 self.embedding.add_nodes_from(self.DG.nodes) 316 for v in self.DG: 317 # sort the adjacency lists again 318 self.ordered_adjs[v] = sorted( 319 self.DG[v], key=lambda x: self.nesting_depth[(v, x)] 320 ) 321 # initialize the embedding 322 previous_node = None 323 for w in self.ordered_adjs[v]: 324 self.embedding.add_half_edge_cw(v, w, previous_node) 325 previous_node = w 326 327 # Free no longer used variables 328 self.DG = None 329 self.nesting_depth = None 330 self.ref = None 331 332 # compute the complete embedding 333 for v in self.roots: 334 self.dfs_embedding(v) 335 336 # Free no longer used variables 337 self.roots = None 338 self.parent_edge = None 339 self.ordered_adjs = None 340 self.left_ref = None 341 self.right_ref = None 342 self.side = None 343 344 return self.embedding 345 346 def lr_planarity_recursive(self): 347 """Recursive version of :meth:`lr_planarity`.""" 348 if self.G.order() > 2 and self.G.size() > 3 * self.G.order() - 6: 349 # graph is not planar 350 return None 351 352 # orientation of the graph by depth first search traversal 353 for v in self.G: 354 if self.height[v] is None: 355 self.height[v] = 0 356 self.roots.append(v) 357 self.dfs_orientation_recursive(v) 358 359 # Free no longer used variable 360 self.G = None 361 362 # testing 363 for v in self.DG: # sort the adjacency lists by nesting depth 364 # note: this sorting leads to non linear time 365 self.ordered_adjs[v] = sorted( 366 self.DG[v], key=lambda x: self.nesting_depth[(v, x)] 367 ) 368 for v in self.roots: 369 if not self.dfs_testing_recursive(v): 370 return None 371 372 for e in self.DG.edges: 373 self.nesting_depth[e] = self.sign_recursive(e) * self.nesting_depth[e] 374 375 self.embedding.add_nodes_from(self.DG.nodes) 376 for v in self.DG: 377 # sort the adjacency lists again 378 self.ordered_adjs[v] = sorted( 379 self.DG[v], key=lambda x: self.nesting_depth[(v, x)] 380 ) 381 # initialize the embedding 382 previous_node = None 383 for w in self.ordered_adjs[v]: 384 self.embedding.add_half_edge_cw(v, w, previous_node) 385 previous_node = w 386 387 # compute the complete embedding 388 for v in self.roots: 389 self.dfs_embedding_recursive(v) 390 391 return self.embedding 392 393 def dfs_orientation(self, v): 394 """Orient the graph by DFS, compute lowpoints and nesting order.""" 395 # the recursion stack 396 dfs_stack = [v] 397 # index of next edge to handle in adjacency list of each node 398 ind = defaultdict(lambda: 0) 399 # boolean to indicate whether to skip the initial work for an edge 400 skip_init = defaultdict(lambda: False) 401 402 while dfs_stack: 403 v = dfs_stack.pop() 404 e = self.parent_edge[v] 405 406 for w in self.adjs[v][ind[v] :]: 407 vw = (v, w) 408 409 if not skip_init[vw]: 410 if (v, w) in self.DG.edges or (w, v) in self.DG.edges: 411 ind[v] += 1 412 continue # the edge was already oriented 413 414 self.DG.add_edge(v, w) # orient the edge 415 416 self.lowpt[vw] = self.height[v] 417 self.lowpt2[vw] = self.height[v] 418 if self.height[w] is None: # (v, w) is a tree edge 419 self.parent_edge[w] = vw 420 self.height[w] = self.height[v] + 1 421 422 dfs_stack.append(v) # revisit v after finishing w 423 dfs_stack.append(w) # visit w next 424 skip_init[vw] = True # don't redo this block 425 break # handle next node in dfs_stack (i.e. w) 426 else: # (v, w) is a back edge 427 self.lowpt[vw] = self.height[w] 428 429 # determine nesting graph 430 self.nesting_depth[vw] = 2 * self.lowpt[vw] 431 if self.lowpt2[vw] < self.height[v]: # chordal 432 self.nesting_depth[vw] += 1 433 434 # update lowpoints of parent edge e 435 if e is not None: 436 if self.lowpt[vw] < self.lowpt[e]: 437 self.lowpt2[e] = min(self.lowpt[e], self.lowpt2[vw]) 438 self.lowpt[e] = self.lowpt[vw] 439 elif self.lowpt[vw] > self.lowpt[e]: 440 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt[vw]) 441 else: 442 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt2[vw]) 443 444 ind[v] += 1 445 446 def dfs_orientation_recursive(self, v): 447 """Recursive version of :meth:`dfs_orientation`.""" 448 e = self.parent_edge[v] 449 for w in self.G[v]: 450 if (v, w) in self.DG.edges or (w, v) in self.DG.edges: 451 continue # the edge was already oriented 452 vw = (v, w) 453 self.DG.add_edge(v, w) # orient the edge 454 455 self.lowpt[vw] = self.height[v] 456 self.lowpt2[vw] = self.height[v] 457 if self.height[w] is None: # (v, w) is a tree edge 458 self.parent_edge[w] = vw 459 self.height[w] = self.height[v] + 1 460 self.dfs_orientation_recursive(w) 461 else: # (v, w) is a back edge 462 self.lowpt[vw] = self.height[w] 463 464 # determine nesting graph 465 self.nesting_depth[vw] = 2 * self.lowpt[vw] 466 if self.lowpt2[vw] < self.height[v]: # chordal 467 self.nesting_depth[vw] += 1 468 469 # update lowpoints of parent edge e 470 if e is not None: 471 if self.lowpt[vw] < self.lowpt[e]: 472 self.lowpt2[e] = min(self.lowpt[e], self.lowpt2[vw]) 473 self.lowpt[e] = self.lowpt[vw] 474 elif self.lowpt[vw] > self.lowpt[e]: 475 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt[vw]) 476 else: 477 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt2[vw]) 478 479 def dfs_testing(self, v): 480 """Test for LR partition.""" 481 # the recursion stack 482 dfs_stack = [v] 483 # index of next edge to handle in adjacency list of each node 484 ind = defaultdict(lambda: 0) 485 # boolean to indicate whether to skip the initial work for an edge 486 skip_init = defaultdict(lambda: False) 487 488 while dfs_stack: 489 v = dfs_stack.pop() 490 e = self.parent_edge[v] 491 # to indicate whether to skip the final block after the for loop 492 skip_final = False 493 494 for w in self.ordered_adjs[v][ind[v] :]: 495 ei = (v, w) 496 497 if not skip_init[ei]: 498 self.stack_bottom[ei] = top_of_stack(self.S) 499 500 if ei == self.parent_edge[w]: # tree edge 501 dfs_stack.append(v) # revisit v after finishing w 502 dfs_stack.append(w) # visit w next 503 skip_init[ei] = True # don't redo this block 504 skip_final = True # skip final work after breaking 505 break # handle next node in dfs_stack (i.e. w) 506 else: # back edge 507 self.lowpt_edge[ei] = ei 508 self.S.append(ConflictPair(right=Interval(ei, ei))) 509 510 # integrate new return edges 511 if self.lowpt[ei] < self.height[v]: 512 if w == self.ordered_adjs[v][0]: # e_i has return edge 513 self.lowpt_edge[e] = self.lowpt_edge[ei] 514 else: # add constraints of e_i 515 if not self.add_constraints(ei, e): 516 # graph is not planar 517 return False 518 519 ind[v] += 1 520 521 if not skip_final: 522 # remove back edges returning to parent 523 if e is not None: # v isn't root 524 self.remove_back_edges(e) 525 526 return True 527 528 def dfs_testing_recursive(self, v): 529 """Recursive version of :meth:`dfs_testing`.""" 530 e = self.parent_edge[v] 531 for w in self.ordered_adjs[v]: 532 ei = (v, w) 533 self.stack_bottom[ei] = top_of_stack(self.S) 534 if ei == self.parent_edge[w]: # tree edge 535 if not self.dfs_testing_recursive(w): 536 return False 537 else: # back edge 538 self.lowpt_edge[ei] = ei 539 self.S.append(ConflictPair(right=Interval(ei, ei))) 540 541 # integrate new return edges 542 if self.lowpt[ei] < self.height[v]: 543 if w == self.ordered_adjs[v][0]: # e_i has return edge 544 self.lowpt_edge[e] = self.lowpt_edge[ei] 545 else: # add constraints of e_i 546 if not self.add_constraints(ei, e): 547 # graph is not planar 548 return False 549 550 # remove back edges returning to parent 551 if e is not None: # v isn't root 552 self.remove_back_edges(e) 553 return True 554 555 def add_constraints(self, ei, e): 556 P = ConflictPair() 557 # merge return edges of e_i into P.right 558 while True: 559 Q = self.S.pop() 560 if not Q.left.empty(): 561 Q.swap() 562 if not Q.left.empty(): # not planar 563 return False 564 if self.lowpt[Q.right.low] > self.lowpt[e]: 565 # merge intervals 566 if P.right.empty(): # topmost interval 567 P.right = Q.right.copy() 568 else: 569 self.ref[P.right.low] = Q.right.high 570 P.right.low = Q.right.low 571 else: # align 572 self.ref[Q.right.low] = self.lowpt_edge[e] 573 if top_of_stack(self.S) == self.stack_bottom[ei]: 574 break 575 # merge conflicting return edges of e_1,...,e_i-1 into P.L 576 while top_of_stack(self.S).left.conflicting(ei, self) or top_of_stack( 577 self.S 578 ).right.conflicting(ei, self): 579 Q = self.S.pop() 580 if Q.right.conflicting(ei, self): 581 Q.swap() 582 if Q.right.conflicting(ei, self): # not planar 583 return False 584 # merge interval below lowpt(e_i) into P.R 585 self.ref[P.right.low] = Q.right.high 586 if Q.right.low is not None: 587 P.right.low = Q.right.low 588 589 if P.left.empty(): # topmost interval 590 P.left = Q.left.copy() 591 else: 592 self.ref[P.left.low] = Q.left.high 593 P.left.low = Q.left.low 594 595 if not (P.left.empty() and P.right.empty()): 596 self.S.append(P) 597 return True 598 599 def remove_back_edges(self, e): 600 u = e[0] 601 # trim back edges ending at parent u 602 # drop entire conflict pairs 603 while self.S and top_of_stack(self.S).lowest(self) == self.height[u]: 604 P = self.S.pop() 605 if P.left.low is not None: 606 self.side[P.left.low] = -1 607 608 if self.S: # one more conflict pair to consider 609 P = self.S.pop() 610 # trim left interval 611 while P.left.high is not None and P.left.high[1] == u: 612 P.left.high = self.ref[P.left.high] 613 if P.left.high is None and P.left.low is not None: 614 # just emptied 615 self.ref[P.left.low] = P.right.low 616 self.side[P.left.low] = -1 617 P.left.low = None 618 # trim right interval 619 while P.right.high is not None and P.right.high[1] == u: 620 P.right.high = self.ref[P.right.high] 621 if P.right.high is None and P.right.low is not None: 622 # just emptied 623 self.ref[P.right.low] = P.left.low 624 self.side[P.right.low] = -1 625 P.right.low = None 626 self.S.append(P) 627 628 # side of e is side of a highest return edge 629 if self.lowpt[e] < self.height[u]: # e has return edge 630 hl = top_of_stack(self.S).left.high 631 hr = top_of_stack(self.S).right.high 632 633 if hl is not None and (hr is None or self.lowpt[hl] > self.lowpt[hr]): 634 self.ref[e] = hl 635 else: 636 self.ref[e] = hr 637 638 def dfs_embedding(self, v): 639 """Completes the embedding.""" 640 # the recursion stack 641 dfs_stack = [v] 642 # index of next edge to handle in adjacency list of each node 643 ind = defaultdict(lambda: 0) 644 645 while dfs_stack: 646 v = dfs_stack.pop() 647 648 for w in self.ordered_adjs[v][ind[v] :]: 649 ind[v] += 1 650 ei = (v, w) 651 652 if ei == self.parent_edge[w]: # tree edge 653 self.embedding.add_half_edge_first(w, v) 654 self.left_ref[v] = w 655 self.right_ref[v] = w 656 657 dfs_stack.append(v) # revisit v after finishing w 658 dfs_stack.append(w) # visit w next 659 break # handle next node in dfs_stack (i.e. w) 660 else: # back edge 661 if self.side[ei] == 1: 662 self.embedding.add_half_edge_cw(w, v, self.right_ref[w]) 663 else: 664 self.embedding.add_half_edge_ccw(w, v, self.left_ref[w]) 665 self.left_ref[w] = v 666 667 def dfs_embedding_recursive(self, v): 668 """Recursive version of :meth:`dfs_embedding`.""" 669 for w in self.ordered_adjs[v]: 670 ei = (v, w) 671 if ei == self.parent_edge[w]: # tree edge 672 self.embedding.add_half_edge_first(w, v) 673 self.left_ref[v] = w 674 self.right_ref[v] = w 675 self.dfs_embedding_recursive(w) 676 else: # back edge 677 if self.side[ei] == 1: 678 # place v directly after right_ref[w] in embed. list of w 679 self.embedding.add_half_edge_cw(w, v, self.right_ref[w]) 680 else: 681 # place v directly before left_ref[w] in embed. list of w 682 self.embedding.add_half_edge_ccw(w, v, self.left_ref[w]) 683 self.left_ref[w] = v 684 685 def sign(self, e): 686 """Resolve the relative side of an edge to the absolute side.""" 687 # the recursion stack 688 dfs_stack = [e] 689 # dict to remember reference edges 690 old_ref = defaultdict(lambda: None) 691 692 while dfs_stack: 693 e = dfs_stack.pop() 694 695 if self.ref[e] is not None: 696 dfs_stack.append(e) # revisit e after finishing self.ref[e] 697 dfs_stack.append(self.ref[e]) # visit self.ref[e] next 698 old_ref[e] = self.ref[e] # remember value of self.ref[e] 699 self.ref[e] = None 700 else: 701 self.side[e] *= self.side[old_ref[e]] 702 703 return self.side[e] 704 705 def sign_recursive(self, e): 706 """Recursive version of :meth:`sign`.""" 707 if self.ref[e] is not None: 708 self.side[e] = self.side[e] * self.sign_recursive(self.ref[e]) 709 self.ref[e] = None 710 return self.side[e] 711 712 713class PlanarEmbedding(nx.DiGraph): 714 """Represents a planar graph with its planar embedding. 715 716 The planar embedding is given by a `combinatorial embedding 717 <https://en.wikipedia.org/wiki/Graph_embedding#Combinatorial_embedding>`_. 718 719 **Neighbor ordering:** 720 721 In comparison to a usual graph structure, the embedding also stores the 722 order of all neighbors for every vertex. 723 The order of the neighbors can be given in clockwise (cw) direction or 724 counterclockwise (ccw) direction. This order is stored as edge attributes 725 in the underlying directed graph. For the edge (u, v) the edge attribute 726 'cw' is set to the neighbor of u that follows immediately after v in 727 clockwise direction. 728 729 In order for a PlanarEmbedding to be valid it must fulfill multiple 730 conditions. It is possible to check if these conditions are fulfilled with 731 the method :meth:`check_structure`. 732 The conditions are: 733 734 * Edges must go in both directions (because the edge attributes differ) 735 * Every edge must have a 'cw' and 'ccw' attribute which corresponds to a 736 correct planar embedding. 737 * A node with non zero degree must have a node attribute 'first_nbr'. 738 739 As long as a PlanarEmbedding is invalid only the following methods should 740 be called: 741 742 * :meth:`add_half_edge_ccw` 743 * :meth:`add_half_edge_cw` 744 * :meth:`connect_components` 745 * :meth:`add_half_edge_first` 746 747 Even though the graph is a subclass of nx.DiGraph, it can still be used 748 for algorithms that require undirected graphs, because the method 749 :meth:`is_directed` is overridden. This is possible, because a valid 750 PlanarGraph must have edges in both directions. 751 752 **Half edges:** 753 754 In methods like `add_half_edge_ccw` the term "half-edge" is used, which is 755 a term that is used in `doubly connected edge lists 756 <https://en.wikipedia.org/wiki/Doubly_connected_edge_list>`_. It is used 757 to emphasize that the edge is only in one direction and there exists 758 another half-edge in the opposite direction. 759 While conventional edges always have two faces (including outer face) next 760 to them, it is possible to assign each half-edge *exactly one* face. 761 For a half-edge (u, v) that is orientated such that u is below v then the 762 face that belongs to (u, v) is to the right of this half-edge. 763 764 Examples 765 -------- 766 767 Create an embedding of a star graph (compare `nx.star_graph(3)`): 768 769 >>> G = nx.PlanarEmbedding() 770 >>> G.add_half_edge_cw(0, 1, None) 771 >>> G.add_half_edge_cw(0, 2, 1) 772 >>> G.add_half_edge_cw(0, 3, 2) 773 >>> G.add_half_edge_cw(1, 0, None) 774 >>> G.add_half_edge_cw(2, 0, None) 775 >>> G.add_half_edge_cw(3, 0, None) 776 777 Alternatively the same embedding can also be defined in counterclockwise 778 orientation. The following results in exactly the same PlanarEmbedding: 779 780 >>> G = nx.PlanarEmbedding() 781 >>> G.add_half_edge_ccw(0, 1, None) 782 >>> G.add_half_edge_ccw(0, 3, 1) 783 >>> G.add_half_edge_ccw(0, 2, 3) 784 >>> G.add_half_edge_ccw(1, 0, None) 785 >>> G.add_half_edge_ccw(2, 0, None) 786 >>> G.add_half_edge_ccw(3, 0, None) 787 788 After creating a graph, it is possible to validate that the PlanarEmbedding 789 object is correct: 790 791 >>> G.check_structure() 792 793 """ 794 795 def get_data(self): 796 """Converts the adjacency structure into a better readable structure. 797 798 Returns 799 ------- 800 embedding : dict 801 A dict mapping all nodes to a list of neighbors sorted in 802 clockwise order. 803 804 See Also 805 -------- 806 set_data 807 808 """ 809 embedding = dict() 810 for v in self: 811 embedding[v] = list(self.neighbors_cw_order(v)) 812 return embedding 813 814 def set_data(self, data): 815 """Inserts edges according to given sorted neighbor list. 816 817 The input format is the same as the output format of get_data(). 818 819 Parameters 820 ---------- 821 data : dict 822 A dict mapping all nodes to a list of neighbors sorted in 823 clockwise order. 824 825 See Also 826 -------- 827 get_data 828 829 """ 830 for v in data: 831 for w in reversed(data[v]): 832 self.add_half_edge_first(v, w) 833 834 def neighbors_cw_order(self, v): 835 """Generator for the neighbors of v in clockwise order. 836 837 Parameters 838 ---------- 839 v : node 840 841 Yields 842 ------ 843 node 844 845 """ 846 if len(self[v]) == 0: 847 # v has no neighbors 848 return 849 start_node = self.nodes[v]["first_nbr"] 850 yield start_node 851 current_node = self[v][start_node]["cw"] 852 while start_node != current_node: 853 yield current_node 854 current_node = self[v][current_node]["cw"] 855 856 def check_structure(self): 857 """Runs without exceptions if this object is valid. 858 859 Checks that the following properties are fulfilled: 860 861 * Edges go in both directions (because the edge attributes differ). 862 * Every edge has a 'cw' and 'ccw' attribute which corresponds to a 863 correct planar embedding. 864 * A node with a degree larger than 0 has a node attribute 'first_nbr'. 865 866 Running this method verifies that the underlying Graph must be planar. 867 868 Raises 869 ------ 870 NetworkXException 871 This exception is raised with a short explanation if the 872 PlanarEmbedding is invalid. 873 """ 874 # Check fundamental structure 875 for v in self: 876 try: 877 sorted_nbrs = set(self.neighbors_cw_order(v)) 878 except KeyError as e: 879 msg = f"Bad embedding. Missing orientation for a neighbor of {v}" 880 raise nx.NetworkXException(msg) from e 881 882 unsorted_nbrs = set(self[v]) 883 if sorted_nbrs != unsorted_nbrs: 884 msg = "Bad embedding. Edge orientations not set correctly." 885 raise nx.NetworkXException(msg) 886 for w in self[v]: 887 # Check if opposite half-edge exists 888 if not self.has_edge(w, v): 889 msg = "Bad embedding. Opposite half-edge is missing." 890 raise nx.NetworkXException(msg) 891 892 # Check planarity 893 counted_half_edges = set() 894 for component in nx.connected_components(self): 895 if len(component) == 1: 896 # Don't need to check single node component 897 continue 898 num_nodes = len(component) 899 num_half_edges = 0 900 num_faces = 0 901 for v in component: 902 for w in self.neighbors_cw_order(v): 903 num_half_edges += 1 904 if (v, w) not in counted_half_edges: 905 # We encountered a new face 906 num_faces += 1 907 # Mark all half-edges belonging to this face 908 self.traverse_face(v, w, counted_half_edges) 909 num_edges = num_half_edges // 2 # num_half_edges is even 910 if num_nodes - num_edges + num_faces != 2: 911 # The result does not match Euler's formula 912 msg = "Bad embedding. The graph does not match Euler's formula" 913 raise nx.NetworkXException(msg) 914 915 def add_half_edge_ccw(self, start_node, end_node, reference_neighbor): 916 """Adds a half-edge from start_node to end_node. 917 918 The half-edge is added counter clockwise next to the existing half-edge 919 (start_node, reference_neighbor). 920 921 Parameters 922 ---------- 923 start_node : node 924 Start node of inserted edge. 925 end_node : node 926 End node of inserted edge. 927 reference_neighbor: node 928 End node of reference edge. 929 930 Raises 931 ------ 932 NetworkXException 933 If the reference_neighbor does not exist. 934 935 See Also 936 -------- 937 add_half_edge_cw 938 connect_components 939 add_half_edge_first 940 941 """ 942 if reference_neighbor is None: 943 # The start node has no neighbors 944 self.add_edge(start_node, end_node) # Add edge to graph 945 self[start_node][end_node]["cw"] = end_node 946 self[start_node][end_node]["ccw"] = end_node 947 self.nodes[start_node]["first_nbr"] = end_node 948 else: 949 ccw_reference = self[start_node][reference_neighbor]["ccw"] 950 self.add_half_edge_cw(start_node, end_node, ccw_reference) 951 952 if reference_neighbor == self.nodes[start_node].get("first_nbr", None): 953 # Update first neighbor 954 self.nodes[start_node]["first_nbr"] = end_node 955 956 def add_half_edge_cw(self, start_node, end_node, reference_neighbor): 957 """Adds a half-edge from start_node to end_node. 958 959 The half-edge is added clockwise next to the existing half-edge 960 (start_node, reference_neighbor). 961 962 Parameters 963 ---------- 964 start_node : node 965 Start node of inserted edge. 966 end_node : node 967 End node of inserted edge. 968 reference_neighbor: node 969 End node of reference edge. 970 971 Raises 972 ------ 973 NetworkXException 974 If the reference_neighbor does not exist. 975 976 See Also 977 -------- 978 add_half_edge_ccw 979 connect_components 980 add_half_edge_first 981 """ 982 self.add_edge(start_node, end_node) # Add edge to graph 983 984 if reference_neighbor is None: 985 # The start node has no neighbors 986 self[start_node][end_node]["cw"] = end_node 987 self[start_node][end_node]["ccw"] = end_node 988 self.nodes[start_node]["first_nbr"] = end_node 989 return 990 991 if reference_neighbor not in self[start_node]: 992 raise nx.NetworkXException( 993 "Cannot add edge. Reference neighbor does not exist" 994 ) 995 996 # Get half-edge at the other side 997 cw_reference = self[start_node][reference_neighbor]["cw"] 998 # Alter half-edge data structures 999 self[start_node][reference_neighbor]["cw"] = end_node 1000 self[start_node][end_node]["cw"] = cw_reference 1001 self[start_node][cw_reference]["ccw"] = end_node 1002 self[start_node][end_node]["ccw"] = reference_neighbor 1003 1004 def connect_components(self, v, w): 1005 """Adds half-edges for (v, w) and (w, v) at some position. 1006 1007 This method should only be called if v and w are in different 1008 components, or it might break the embedding. 1009 This especially means that if `connect_components(v, w)` 1010 is called it is not allowed to call `connect_components(w, v)` 1011 afterwards. The neighbor orientations in both directions are 1012 all set correctly after the first call. 1013 1014 Parameters 1015 ---------- 1016 v : node 1017 w : node 1018 1019 See Also 1020 -------- 1021 add_half_edge_ccw 1022 add_half_edge_cw 1023 add_half_edge_first 1024 """ 1025 self.add_half_edge_first(v, w) 1026 self.add_half_edge_first(w, v) 1027 1028 def add_half_edge_first(self, start_node, end_node): 1029 """The added half-edge is inserted at the first position in the order. 1030 1031 Parameters 1032 ---------- 1033 start_node : node 1034 end_node : node 1035 1036 See Also 1037 -------- 1038 add_half_edge_ccw 1039 add_half_edge_cw 1040 connect_components 1041 """ 1042 if start_node in self and "first_nbr" in self.nodes[start_node]: 1043 reference = self.nodes[start_node]["first_nbr"] 1044 else: 1045 reference = None 1046 self.add_half_edge_ccw(start_node, end_node, reference) 1047 1048 def next_face_half_edge(self, v, w): 1049 """Returns the following half-edge left of a face. 1050 1051 Parameters 1052 ---------- 1053 v : node 1054 w : node 1055 1056 Returns 1057 ------- 1058 half-edge : tuple 1059 """ 1060 new_node = self[w][v]["ccw"] 1061 return w, new_node 1062 1063 def traverse_face(self, v, w, mark_half_edges=None): 1064 """Returns nodes on the face that belong to the half-edge (v, w). 1065 1066 The face that is traversed lies to the right of the half-edge (in an 1067 orientation where v is below w). 1068 1069 Optionally it is possible to pass a set to which all encountered half 1070 edges are added. Before calling this method, this set must not include 1071 any half-edges that belong to the face. 1072 1073 Parameters 1074 ---------- 1075 v : node 1076 Start node of half-edge. 1077 w : node 1078 End node of half-edge. 1079 mark_half_edges: set, optional 1080 Set to which all encountered half-edges are added. 1081 1082 Returns 1083 ------- 1084 face : list 1085 A list of nodes that lie on this face. 1086 """ 1087 if mark_half_edges is None: 1088 mark_half_edges = set() 1089 1090 face_nodes = [v] 1091 mark_half_edges.add((v, w)) 1092 prev_node = v 1093 cur_node = w 1094 # Last half-edge is (incoming_node, v) 1095 incoming_node = self[v][w]["cw"] 1096 1097 while cur_node != v or prev_node != incoming_node: 1098 face_nodes.append(cur_node) 1099 prev_node, cur_node = self.next_face_half_edge(prev_node, cur_node) 1100 if (prev_node, cur_node) in mark_half_edges: 1101 raise nx.NetworkXException("Bad planar embedding. Impossible face.") 1102 mark_half_edges.add((prev_node, cur_node)) 1103 1104 return face_nodes 1105 1106 def is_directed(self): 1107 """A valid PlanarEmbedding is undirected. 1108 1109 All reverse edges are contained, i.e. for every existing 1110 half-edge (v, w) the half-edge in the opposite direction (w, v) is also 1111 contained. 1112 """ 1113 return False 1114