Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1from collections import defaultdict
2from copy import deepcopy
4import networkx as nx
6__all__ = ["check_planarity", "is_planar", "PlanarEmbedding"]
9@nx._dispatchable
10def is_planar(G):
11 """Returns True if and only if `G` is planar.
13 A graph is *planar* iff it can be drawn in a plane without
14 any edge intersections.
16 Parameters
17 ----------
18 G : NetworkX graph
20 Returns
21 -------
22 bool
23 Whether the graph is planar.
25 Examples
26 --------
27 >>> G = nx.Graph([(0, 1), (0, 2)])
28 >>> nx.is_planar(G)
29 True
30 >>> nx.is_planar(nx.complete_graph(5))
31 False
33 See Also
34 --------
35 check_planarity :
36 Check if graph is planar *and* return a `PlanarEmbedding` instance if True.
37 """
39 return check_planarity(G, counterexample=False)[0]
42@nx._dispatchable(returns_graph=True)
43def check_planarity(G, counterexample=False):
44 """Check if a graph is planar and return a counterexample or an embedding.
46 A graph is planar iff it can be drawn in a plane without
47 any edge intersections.
49 Parameters
50 ----------
51 G : NetworkX graph
52 counterexample : bool
53 A Kuratowski subgraph (to proof non planarity) is only returned if set
54 to true.
56 Returns
57 -------
58 (is_planar, certificate) : (bool, NetworkX graph) tuple
59 is_planar is true if the graph is planar.
60 If the graph is planar `certificate` is a PlanarEmbedding
61 otherwise it is a Kuratowski subgraph.
63 Examples
64 --------
65 >>> G = nx.Graph([(0, 1), (0, 2)])
66 >>> is_planar, P = nx.check_planarity(G)
67 >>> print(is_planar)
68 True
70 When `G` is planar, a `PlanarEmbedding` instance is returned:
72 >>> P.get_data()
73 {0: [1, 2], 1: [0], 2: [0]}
75 Notes
76 -----
77 A (combinatorial) embedding consists of cyclic orderings of the incident
78 edges at each vertex. Given such an embedding there are multiple approaches
79 discussed in literature to drawing the graph (subject to various
80 constraints, e.g. integer coordinates), see e.g. [2].
82 The planarity check algorithm and extraction of the combinatorial embedding
83 is based on the Left-Right Planarity Test [1].
85 A counterexample is only generated if the corresponding parameter is set,
86 because the complexity of the counterexample generation is higher.
88 See also
89 --------
90 is_planar :
91 Check for planarity without creating a `PlanarEmbedding` or counterexample.
93 References
94 ----------
95 .. [1] Ulrik Brandes:
96 The Left-Right Planarity Test
97 2009
98 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.9208
99 .. [2] Takao Nishizeki, Md Saidur Rahman:
100 Planar graph drawing
101 Lecture Notes Series on Computing: Volume 12
102 2004
103 """
105 planarity_state = LRPlanarity(G)
106 embedding = planarity_state.lr_planarity()
107 if embedding is None:
108 # graph is not planar
109 if counterexample:
110 return False, get_counterexample(G)
111 else:
112 return False, None
113 else:
114 # graph is planar
115 return True, embedding
118@nx._dispatchable(returns_graph=True)
119def check_planarity_recursive(G, counterexample=False):
120 """Recursive version of :meth:`check_planarity`."""
121 planarity_state = LRPlanarity(G)
122 embedding = planarity_state.lr_planarity_recursive()
123 if embedding is None:
124 # graph is not planar
125 if counterexample:
126 return False, get_counterexample_recursive(G)
127 else:
128 return False, None
129 else:
130 # graph is planar
131 return True, embedding
134@nx._dispatchable(returns_graph=True)
135def get_counterexample(G):
136 """Obtains a Kuratowski subgraph.
138 Raises nx.NetworkXException if G is planar.
140 The function removes edges such that the graph is still not planar.
141 At some point the removal of any edge would make the graph planar.
142 This subgraph must be a Kuratowski subgraph.
144 Parameters
145 ----------
146 G : NetworkX graph
148 Returns
149 -------
150 subgraph : NetworkX graph
151 A Kuratowski subgraph that proves that G is not planar.
153 """
154 # copy graph
155 G = nx.Graph(G)
157 if check_planarity(G)[0]:
158 raise nx.NetworkXException("G is planar - no counter example.")
160 # find Kuratowski subgraph
161 subgraph = nx.Graph()
162 for u in G:
163 nbrs = list(G[u])
164 for v in nbrs:
165 G.remove_edge(u, v)
166 if check_planarity(G)[0]:
167 G.add_edge(u, v)
168 subgraph.add_edge(u, v)
170 return subgraph
173@nx._dispatchable(returns_graph=True)
174def get_counterexample_recursive(G):
175 """Recursive version of :meth:`get_counterexample`."""
177 # copy graph
178 G = nx.Graph(G)
180 if check_planarity_recursive(G)[0]:
181 raise nx.NetworkXException("G is planar - no counter example.")
183 # find Kuratowski subgraph
184 subgraph = nx.Graph()
185 for u in G:
186 nbrs = list(G[u])
187 for v in nbrs:
188 G.remove_edge(u, v)
189 if check_planarity_recursive(G)[0]:
190 G.add_edge(u, v)
191 subgraph.add_edge(u, v)
193 return subgraph
196class Interval:
197 """Represents a set of return edges.
199 All return edges in an interval induce a same constraint on the contained
200 edges, which means that all edges must either have a left orientation or
201 all edges must have a right orientation.
202 """
204 def __init__(self, low=None, high=None):
205 self.low = low
206 self.high = high
208 def empty(self):
209 """Check if the interval is empty"""
210 return self.low is None and self.high is None
212 def copy(self):
213 """Returns a copy of this interval"""
214 return Interval(self.low, self.high)
216 def conflicting(self, b, planarity_state):
217 """Returns True if interval I conflicts with edge b"""
218 return (
219 not self.empty()
220 and planarity_state.lowpt[self.high] > planarity_state.lowpt[b]
221 )
224class ConflictPair:
225 """Represents a different constraint between two intervals.
227 The edges in the left interval must have a different orientation than
228 the one in the right interval.
229 """
231 def __init__(self, left=Interval(), right=Interval()):
232 self.left = left
233 self.right = right
235 def swap(self):
236 """Swap left and right intervals"""
237 temp = self.left
238 self.left = self.right
239 self.right = temp
241 def lowest(self, planarity_state):
242 """Returns the lowest lowpoint of a conflict pair"""
243 if self.left.empty():
244 return planarity_state.lowpt[self.right.low]
245 if self.right.empty():
246 return planarity_state.lowpt[self.left.low]
247 return min(
248 planarity_state.lowpt[self.left.low], planarity_state.lowpt[self.right.low]
249 )
252def top_of_stack(l):
253 """Returns the element on top of the stack."""
254 if not l:
255 return None
256 return l[-1]
259class LRPlanarity:
260 """A class to maintain the state during planarity check."""
262 __slots__ = [
263 "G",
264 "roots",
265 "height",
266 "lowpt",
267 "lowpt2",
268 "nesting_depth",
269 "parent_edge",
270 "DG",
271 "adjs",
272 "ordered_adjs",
273 "ref",
274 "side",
275 "S",
276 "stack_bottom",
277 "lowpt_edge",
278 "left_ref",
279 "right_ref",
280 "embedding",
281 ]
283 def __init__(self, G):
284 # copy G without adding self-loops
285 self.G = nx.Graph()
286 self.G.add_nodes_from(G.nodes)
287 for e in G.edges:
288 if e[0] != e[1]:
289 self.G.add_edge(e[0], e[1])
291 self.roots = []
293 # distance from tree root
294 self.height = defaultdict(lambda: None)
296 self.lowpt = {} # height of lowest return point of an edge
297 self.lowpt2 = {} # height of second lowest return point
298 self.nesting_depth = {} # for nesting order
300 # None -> missing edge
301 self.parent_edge = defaultdict(lambda: None)
303 # oriented DFS graph
304 self.DG = nx.DiGraph()
305 self.DG.add_nodes_from(G.nodes)
307 self.adjs = {}
308 self.ordered_adjs = {}
310 self.ref = defaultdict(lambda: None)
311 self.side = defaultdict(lambda: 1)
313 # stack of conflict pairs
314 self.S = []
315 self.stack_bottom = {}
316 self.lowpt_edge = {}
318 self.left_ref = {}
319 self.right_ref = {}
321 self.embedding = PlanarEmbedding()
323 def lr_planarity(self):
324 """Execute the LR planarity test.
326 Returns
327 -------
328 embedding : dict
329 If the graph is planar an embedding is returned. Otherwise None.
330 """
331 if self.G.order() > 2 and self.G.size() > 3 * self.G.order() - 6:
332 # graph is not planar
333 return None
335 # make adjacency lists for dfs
336 for v in self.G:
337 self.adjs[v] = list(self.G[v])
339 # orientation of the graph by depth first search traversal
340 for v in self.G:
341 if self.height[v] is None:
342 self.height[v] = 0
343 self.roots.append(v)
344 self.dfs_orientation(v)
346 # Free no longer used variables
347 self.G = None
348 self.lowpt2 = None
349 self.adjs = None
351 # testing
352 for v in self.DG: # sort the adjacency lists by nesting depth
353 # note: this sorting leads to non linear time
354 self.ordered_adjs[v] = sorted(
355 self.DG[v], key=lambda x: self.nesting_depth[(v, x)]
356 )
357 for v in self.roots:
358 if not self.dfs_testing(v):
359 return None
361 # Free no longer used variables
362 self.height = None
363 self.lowpt = None
364 self.S = None
365 self.stack_bottom = None
366 self.lowpt_edge = None
368 for e in self.DG.edges:
369 self.nesting_depth[e] = self.sign(e) * self.nesting_depth[e]
371 self.embedding.add_nodes_from(self.DG.nodes)
372 for v in self.DG:
373 # sort the adjacency lists again
374 self.ordered_adjs[v] = sorted(
375 self.DG[v], key=lambda x: self.nesting_depth[(v, x)]
376 )
377 # initialize the embedding
378 previous_node = None
379 for w in self.ordered_adjs[v]:
380 self.embedding.add_half_edge(v, w, ccw=previous_node)
381 previous_node = w
383 # Free no longer used variables
384 self.DG = None
385 self.nesting_depth = None
386 self.ref = None
388 # compute the complete embedding
389 for v in self.roots:
390 self.dfs_embedding(v)
392 # Free no longer used variables
393 self.roots = None
394 self.parent_edge = None
395 self.ordered_adjs = None
396 self.left_ref = None
397 self.right_ref = None
398 self.side = None
400 return self.embedding
402 def lr_planarity_recursive(self):
403 """Recursive version of :meth:`lr_planarity`."""
404 if self.G.order() > 2 and self.G.size() > 3 * self.G.order() - 6:
405 # graph is not planar
406 return None
408 # orientation of the graph by depth first search traversal
409 for v in self.G:
410 if self.height[v] is None:
411 self.height[v] = 0
412 self.roots.append(v)
413 self.dfs_orientation_recursive(v)
415 # Free no longer used variable
416 self.G = None
418 # testing
419 for v in self.DG: # sort the adjacency lists by nesting depth
420 # note: this sorting leads to non linear time
421 self.ordered_adjs[v] = sorted(
422 self.DG[v], key=lambda x: self.nesting_depth[(v, x)]
423 )
424 for v in self.roots:
425 if not self.dfs_testing_recursive(v):
426 return None
428 for e in self.DG.edges:
429 self.nesting_depth[e] = self.sign_recursive(e) * self.nesting_depth[e]
431 self.embedding.add_nodes_from(self.DG.nodes)
432 for v in self.DG:
433 # sort the adjacency lists again
434 self.ordered_adjs[v] = sorted(
435 self.DG[v], key=lambda x: self.nesting_depth[(v, x)]
436 )
437 # initialize the embedding
438 previous_node = None
439 for w in self.ordered_adjs[v]:
440 self.embedding.add_half_edge(v, w, ccw=previous_node)
441 previous_node = w
443 # compute the complete embedding
444 for v in self.roots:
445 self.dfs_embedding_recursive(v)
447 return self.embedding
449 def dfs_orientation(self, v):
450 """Orient the graph by DFS, compute lowpoints and nesting order."""
451 # the recursion stack
452 dfs_stack = [v]
453 # index of next edge to handle in adjacency list of each node
454 ind = defaultdict(lambda: 0)
455 # boolean to indicate whether to skip the initial work for an edge
456 skip_init = defaultdict(lambda: False)
458 while dfs_stack:
459 v = dfs_stack.pop()
460 e = self.parent_edge[v]
462 for w in self.adjs[v][ind[v] :]:
463 vw = (v, w)
465 if not skip_init[vw]:
466 if (v, w) in self.DG.edges or (w, v) in self.DG.edges:
467 ind[v] += 1
468 continue # the edge was already oriented
470 self.DG.add_edge(v, w) # orient the edge
472 self.lowpt[vw] = self.height[v]
473 self.lowpt2[vw] = self.height[v]
474 if self.height[w] is None: # (v, w) is a tree edge
475 self.parent_edge[w] = vw
476 self.height[w] = self.height[v] + 1
478 dfs_stack.append(v) # revisit v after finishing w
479 dfs_stack.append(w) # visit w next
480 skip_init[vw] = True # don't redo this block
481 break # handle next node in dfs_stack (i.e. w)
482 else: # (v, w) is a back edge
483 self.lowpt[vw] = self.height[w]
485 # determine nesting graph
486 self.nesting_depth[vw] = 2 * self.lowpt[vw]
487 if self.lowpt2[vw] < self.height[v]: # chordal
488 self.nesting_depth[vw] += 1
490 # update lowpoints of parent edge e
491 if e is not None:
492 if self.lowpt[vw] < self.lowpt[e]:
493 self.lowpt2[e] = min(self.lowpt[e], self.lowpt2[vw])
494 self.lowpt[e] = self.lowpt[vw]
495 elif self.lowpt[vw] > self.lowpt[e]:
496 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt[vw])
497 else:
498 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt2[vw])
500 ind[v] += 1
502 def dfs_orientation_recursive(self, v):
503 """Recursive version of :meth:`dfs_orientation`."""
504 e = self.parent_edge[v]
505 for w in self.G[v]:
506 if (v, w) in self.DG.edges or (w, v) in self.DG.edges:
507 continue # the edge was already oriented
508 vw = (v, w)
509 self.DG.add_edge(v, w) # orient the edge
511 self.lowpt[vw] = self.height[v]
512 self.lowpt2[vw] = self.height[v]
513 if self.height[w] is None: # (v, w) is a tree edge
514 self.parent_edge[w] = vw
515 self.height[w] = self.height[v] + 1
516 self.dfs_orientation_recursive(w)
517 else: # (v, w) is a back edge
518 self.lowpt[vw] = self.height[w]
520 # determine nesting graph
521 self.nesting_depth[vw] = 2 * self.lowpt[vw]
522 if self.lowpt2[vw] < self.height[v]: # chordal
523 self.nesting_depth[vw] += 1
525 # update lowpoints of parent edge e
526 if e is not None:
527 if self.lowpt[vw] < self.lowpt[e]:
528 self.lowpt2[e] = min(self.lowpt[e], self.lowpt2[vw])
529 self.lowpt[e] = self.lowpt[vw]
530 elif self.lowpt[vw] > self.lowpt[e]:
531 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt[vw])
532 else:
533 self.lowpt2[e] = min(self.lowpt2[e], self.lowpt2[vw])
535 def dfs_testing(self, v):
536 """Test for LR partition."""
537 # the recursion stack
538 dfs_stack = [v]
539 # index of next edge to handle in adjacency list of each node
540 ind = defaultdict(lambda: 0)
541 # boolean to indicate whether to skip the initial work for an edge
542 skip_init = defaultdict(lambda: False)
544 while dfs_stack:
545 v = dfs_stack.pop()
546 e = self.parent_edge[v]
547 # to indicate whether to skip the final block after the for loop
548 skip_final = False
550 for w in self.ordered_adjs[v][ind[v] :]:
551 ei = (v, w)
553 if not skip_init[ei]:
554 self.stack_bottom[ei] = top_of_stack(self.S)
556 if ei == self.parent_edge[w]: # tree edge
557 dfs_stack.append(v) # revisit v after finishing w
558 dfs_stack.append(w) # visit w next
559 skip_init[ei] = True # don't redo this block
560 skip_final = True # skip final work after breaking
561 break # handle next node in dfs_stack (i.e. w)
562 else: # back edge
563 self.lowpt_edge[ei] = ei
564 self.S.append(ConflictPair(right=Interval(ei, ei)))
566 # integrate new return edges
567 if self.lowpt[ei] < self.height[v]:
568 if w == self.ordered_adjs[v][0]: # e_i has return edge
569 self.lowpt_edge[e] = self.lowpt_edge[ei]
570 else: # add constraints of e_i
571 if not self.add_constraints(ei, e):
572 # graph is not planar
573 return False
575 ind[v] += 1
577 if not skip_final:
578 # remove back edges returning to parent
579 if e is not None: # v isn't root
580 self.remove_back_edges(e)
582 return True
584 def dfs_testing_recursive(self, v):
585 """Recursive version of :meth:`dfs_testing`."""
586 e = self.parent_edge[v]
587 for w in self.ordered_adjs[v]:
588 ei = (v, w)
589 self.stack_bottom[ei] = top_of_stack(self.S)
590 if ei == self.parent_edge[w]: # tree edge
591 if not self.dfs_testing_recursive(w):
592 return False
593 else: # back edge
594 self.lowpt_edge[ei] = ei
595 self.S.append(ConflictPair(right=Interval(ei, ei)))
597 # integrate new return edges
598 if self.lowpt[ei] < self.height[v]:
599 if w == self.ordered_adjs[v][0]: # e_i has return edge
600 self.lowpt_edge[e] = self.lowpt_edge[ei]
601 else: # add constraints of e_i
602 if not self.add_constraints(ei, e):
603 # graph is not planar
604 return False
606 # remove back edges returning to parent
607 if e is not None: # v isn't root
608 self.remove_back_edges(e)
609 return True
611 def add_constraints(self, ei, e):
612 P = ConflictPair()
613 # merge return edges of e_i into P.right
614 while True:
615 Q = self.S.pop()
616 if not Q.left.empty():
617 Q.swap()
618 if not Q.left.empty(): # not planar
619 return False
620 if self.lowpt[Q.right.low] > self.lowpt[e]:
621 # merge intervals
622 if P.right.empty(): # topmost interval
623 P.right = Q.right.copy()
624 else:
625 self.ref[P.right.low] = Q.right.high
626 P.right.low = Q.right.low
627 else: # align
628 self.ref[Q.right.low] = self.lowpt_edge[e]
629 if top_of_stack(self.S) == self.stack_bottom[ei]:
630 break
631 # merge conflicting return edges of e_1,...,e_i-1 into P.L
632 while top_of_stack(self.S).left.conflicting(ei, self) or top_of_stack(
633 self.S
634 ).right.conflicting(ei, self):
635 Q = self.S.pop()
636 if Q.right.conflicting(ei, self):
637 Q.swap()
638 if Q.right.conflicting(ei, self): # not planar
639 return False
640 # merge interval below lowpt(e_i) into P.R
641 self.ref[P.right.low] = Q.right.high
642 if Q.right.low is not None:
643 P.right.low = Q.right.low
645 if P.left.empty(): # topmost interval
646 P.left = Q.left.copy()
647 else:
648 self.ref[P.left.low] = Q.left.high
649 P.left.low = Q.left.low
651 if not (P.left.empty() and P.right.empty()):
652 self.S.append(P)
653 return True
655 def remove_back_edges(self, e):
656 u = e[0]
657 # trim back edges ending at parent u
658 # drop entire conflict pairs
659 while self.S and top_of_stack(self.S).lowest(self) == self.height[u]:
660 P = self.S.pop()
661 if P.left.low is not None:
662 self.side[P.left.low] = -1
664 if self.S: # one more conflict pair to consider
665 P = self.S.pop()
666 # trim left interval
667 while P.left.high is not None and P.left.high[1] == u:
668 P.left.high = self.ref[P.left.high]
669 if P.left.high is None and P.left.low is not None:
670 # just emptied
671 self.ref[P.left.low] = P.right.low
672 self.side[P.left.low] = -1
673 P.left.low = None
674 # trim right interval
675 while P.right.high is not None and P.right.high[1] == u:
676 P.right.high = self.ref[P.right.high]
677 if P.right.high is None and P.right.low is not None:
678 # just emptied
679 self.ref[P.right.low] = P.left.low
680 self.side[P.right.low] = -1
681 P.right.low = None
682 self.S.append(P)
684 # side of e is side of a highest return edge
685 if self.lowpt[e] < self.height[u]: # e has return edge
686 hl = top_of_stack(self.S).left.high
687 hr = top_of_stack(self.S).right.high
689 if hl is not None and (hr is None or self.lowpt[hl] > self.lowpt[hr]):
690 self.ref[e] = hl
691 else:
692 self.ref[e] = hr
694 def dfs_embedding(self, v):
695 """Completes the embedding."""
696 # the recursion stack
697 dfs_stack = [v]
698 # index of next edge to handle in adjacency list of each node
699 ind = defaultdict(lambda: 0)
701 while dfs_stack:
702 v = dfs_stack.pop()
704 for w in self.ordered_adjs[v][ind[v] :]:
705 ind[v] += 1
706 ei = (v, w)
708 if ei == self.parent_edge[w]: # tree edge
709 self.embedding.add_half_edge_first(w, v)
710 self.left_ref[v] = w
711 self.right_ref[v] = w
713 dfs_stack.append(v) # revisit v after finishing w
714 dfs_stack.append(w) # visit w next
715 break # handle next node in dfs_stack (i.e. w)
716 else: # back edge
717 if self.side[ei] == 1:
718 self.embedding.add_half_edge(w, v, ccw=self.right_ref[w])
719 else:
720 self.embedding.add_half_edge(w, v, cw=self.left_ref[w])
721 self.left_ref[w] = v
723 def dfs_embedding_recursive(self, v):
724 """Recursive version of :meth:`dfs_embedding`."""
725 for w in self.ordered_adjs[v]:
726 ei = (v, w)
727 if ei == self.parent_edge[w]: # tree edge
728 self.embedding.add_half_edge_first(w, v)
729 self.left_ref[v] = w
730 self.right_ref[v] = w
731 self.dfs_embedding_recursive(w)
732 else: # back edge
733 if self.side[ei] == 1:
734 # place v directly after right_ref[w] in embed. list of w
735 self.embedding.add_half_edge(w, v, ccw=self.right_ref[w])
736 else:
737 # place v directly before left_ref[w] in embed. list of w
738 self.embedding.add_half_edge(w, v, cw=self.left_ref[w])
739 self.left_ref[w] = v
741 def sign(self, e):
742 """Resolve the relative side of an edge to the absolute side."""
743 # the recursion stack
744 dfs_stack = [e]
745 # dict to remember reference edges
746 old_ref = defaultdict(lambda: None)
748 while dfs_stack:
749 e = dfs_stack.pop()
751 if self.ref[e] is not None:
752 dfs_stack.append(e) # revisit e after finishing self.ref[e]
753 dfs_stack.append(self.ref[e]) # visit self.ref[e] next
754 old_ref[e] = self.ref[e] # remember value of self.ref[e]
755 self.ref[e] = None
756 else:
757 self.side[e] *= self.side[old_ref[e]]
759 return self.side[e]
761 def sign_recursive(self, e):
762 """Recursive version of :meth:`sign`."""
763 if self.ref[e] is not None:
764 self.side[e] = self.side[e] * self.sign_recursive(self.ref[e])
765 self.ref[e] = None
766 return self.side[e]
769class PlanarEmbedding(nx.DiGraph):
770 """Represents a planar graph with its planar embedding.
772 The planar embedding is given by a `combinatorial embedding
773 <https://en.wikipedia.org/wiki/Graph_embedding#Combinatorial_embedding>`_.
775 .. note:: `check_planarity` is the preferred way to check if a graph is planar.
777 **Neighbor ordering:**
779 In comparison to a usual graph structure, the embedding also stores the
780 order of all neighbors for every vertex.
781 The order of the neighbors can be given in clockwise (cw) direction or
782 counterclockwise (ccw) direction. This order is stored as edge attributes
783 in the underlying directed graph. For the edge (u, v) the edge attribute
784 'cw' is set to the neighbor of u that follows immediately after v in
785 clockwise direction.
787 In order for a PlanarEmbedding to be valid it must fulfill multiple
788 conditions. It is possible to check if these conditions are fulfilled with
789 the method :meth:`check_structure`.
790 The conditions are:
792 * Edges must go in both directions (because the edge attributes differ)
793 * Every edge must have a 'cw' and 'ccw' attribute which corresponds to a
794 correct planar embedding.
796 As long as a PlanarEmbedding is invalid only the following methods should
797 be called:
799 * :meth:`add_half_edge`
800 * :meth:`connect_components`
802 Even though the graph is a subclass of nx.DiGraph, it can still be used
803 for algorithms that require undirected graphs, because the method
804 :meth:`is_directed` is overridden. This is possible, because a valid
805 PlanarGraph must have edges in both directions.
807 **Half edges:**
809 In methods like `add_half_edge` the term "half-edge" is used, which is
810 a term that is used in `doubly connected edge lists
811 <https://en.wikipedia.org/wiki/Doubly_connected_edge_list>`_. It is used
812 to emphasize that the edge is only in one direction and there exists
813 another half-edge in the opposite direction.
814 While conventional edges always have two faces (including outer face) next
815 to them, it is possible to assign each half-edge *exactly one* face.
816 For a half-edge (u, v) that is oriented such that u is below v then the
817 face that belongs to (u, v) is to the right of this half-edge.
819 See Also
820 --------
821 is_planar :
822 Preferred way to check if an existing graph is planar.
824 check_planarity :
825 A convenient way to create a `PlanarEmbedding`. If not planar,
826 it returns a subgraph that shows this.
828 Examples
829 --------
831 Create an embedding of a star graph (compare `nx.star_graph(3)`):
833 >>> G = nx.PlanarEmbedding()
834 >>> G.add_half_edge(0, 1)
835 >>> G.add_half_edge(0, 2, ccw=1)
836 >>> G.add_half_edge(0, 3, ccw=2)
837 >>> G.add_half_edge(1, 0)
838 >>> G.add_half_edge(2, 0)
839 >>> G.add_half_edge(3, 0)
841 Alternatively the same embedding can also be defined in counterclockwise
842 orientation. The following results in exactly the same PlanarEmbedding:
844 >>> G = nx.PlanarEmbedding()
845 >>> G.add_half_edge(0, 1)
846 >>> G.add_half_edge(0, 3, cw=1)
847 >>> G.add_half_edge(0, 2, cw=3)
848 >>> G.add_half_edge(1, 0)
849 >>> G.add_half_edge(2, 0)
850 >>> G.add_half_edge(3, 0)
852 After creating a graph, it is possible to validate that the PlanarEmbedding
853 object is correct:
855 >>> G.check_structure()
857 """
859 def __init__(self, incoming_graph_data=None, **attr):
860 super().__init__(incoming_graph_data=incoming_graph_data, **attr)
861 self.add_edge = self._forbidden
862 self.add_edges_from = self._forbidden
863 self.add_weighted_edges_from = self._forbidden
865 def _forbidden(self, *args, **kwargs):
866 """Forbidden operation
868 Any edge additions to a PlanarEmbedding should be done using
869 method `add_half_edge`.
870 """
871 raise NotImplementedError(
872 "Use `add_half_edge` method to add edges to a PlanarEmbedding."
873 )
875 def get_data(self):
876 """Converts the adjacency structure into a better readable structure.
878 Returns
879 -------
880 embedding : dict
881 A dict mapping all nodes to a list of neighbors sorted in
882 clockwise order.
884 See Also
885 --------
886 set_data
888 """
889 embedding = {}
890 for v in self:
891 embedding[v] = list(self.neighbors_cw_order(v))
892 return embedding
894 def set_data(self, data):
895 """Inserts edges according to given sorted neighbor list.
897 The input format is the same as the output format of get_data().
899 Parameters
900 ----------
901 data : dict
902 A dict mapping all nodes to a list of neighbors sorted in
903 clockwise order.
905 See Also
906 --------
907 get_data
909 """
910 for v in data:
911 ref = None
912 for w in reversed(data[v]):
913 self.add_half_edge(v, w, cw=ref)
914 ref = w
916 def remove_node(self, n):
917 """Remove node n.
919 Removes the node n and all adjacent edges, updating the
920 PlanarEmbedding to account for any resulting edge removal.
921 Attempting to remove a non-existent node will raise an exception.
923 Parameters
924 ----------
925 n : node
926 A node in the graph
928 Raises
929 ------
930 NetworkXError
931 If n is not in the graph.
933 See Also
934 --------
935 remove_nodes_from
937 """
938 try:
939 for u in self._pred[n]:
940 succs_u = self._succ[u]
941 un_cw = succs_u[n]["cw"]
942 un_ccw = succs_u[n]["ccw"]
943 del succs_u[n]
944 del self._pred[u][n]
945 if n != un_cw:
946 succs_u[un_cw]["ccw"] = un_ccw
947 succs_u[un_ccw]["cw"] = un_cw
948 del self._node[n]
949 del self._succ[n]
950 del self._pred[n]
951 except KeyError as err: # NetworkXError if n not in self
952 raise nx.NetworkXError(
953 f"The node {n} is not in the planar embedding."
954 ) from err
955 nx._clear_cache(self)
957 def remove_nodes_from(self, nodes):
958 """Remove multiple nodes.
960 Parameters
961 ----------
962 nodes : iterable container
963 A container of nodes (list, dict, set, etc.). If a node
964 in the container is not in the graph it is silently ignored.
966 See Also
967 --------
968 remove_node
970 Notes
971 -----
972 When removing nodes from an iterator over the graph you are changing,
973 a `RuntimeError` will be raised with message:
974 `RuntimeError: dictionary changed size during iteration`. This
975 happens when the graph's underlying dictionary is modified during
976 iteration. To avoid this error, evaluate the iterator into a separate
977 object, e.g. by using `list(iterator_of_nodes)`, and pass this
978 object to `G.remove_nodes_from`.
980 """
981 for n in nodes:
982 if n in self._node:
983 self.remove_node(n)
984 # silently skip non-existing nodes
986 def neighbors_cw_order(self, v):
987 """Generator for the neighbors of v in clockwise order.
989 Parameters
990 ----------
991 v : node
993 Yields
994 ------
995 node
997 """
998 succs = self._succ[v]
999 if not succs:
1000 # v has no neighbors
1001 return
1002 start_node = next(reversed(succs))
1003 yield start_node
1004 current_node = succs[start_node]["cw"]
1005 while start_node != current_node:
1006 yield current_node
1007 current_node = succs[current_node]["cw"]
1009 def add_half_edge(self, start_node, end_node, *, cw=None, ccw=None):
1010 """Adds a half-edge from `start_node` to `end_node`.
1012 If the half-edge is not the first one out of `start_node`, a reference
1013 node must be provided either in the clockwise (parameter `cw`) or in
1014 the counterclockwise (parameter `ccw`) direction. Only one of `cw`/`ccw`
1015 can be specified (or neither in the case of the first edge).
1016 Note that specifying a reference in the clockwise (`cw`) direction means
1017 inserting the new edge in the first counterclockwise position with
1018 respect to the reference (and vice-versa).
1020 Parameters
1021 ----------
1022 start_node : node
1023 Start node of inserted edge.
1024 end_node : node
1025 End node of inserted edge.
1026 cw, ccw: node
1027 End node of reference edge.
1028 Omit or pass `None` if adding the first out-half-edge of `start_node`.
1031 Raises
1032 ------
1033 NetworkXException
1034 If the `cw` or `ccw` node is not a successor of `start_node`.
1035 If `start_node` has successors, but neither `cw` or `ccw` is provided.
1036 If both `cw` and `ccw` are specified.
1038 See Also
1039 --------
1040 connect_components
1041 """
1043 succs = self._succ.get(start_node)
1044 if succs:
1045 # there is already some edge out of start_node
1046 leftmost_nbr = next(reversed(self._succ[start_node]))
1047 if cw is not None:
1048 if cw not in succs:
1049 raise nx.NetworkXError("Invalid clockwise reference node.")
1050 if ccw is not None:
1051 raise nx.NetworkXError("Only one of cw/ccw can be specified.")
1052 ref_ccw = succs[cw]["ccw"]
1053 super().add_edge(start_node, end_node, cw=cw, ccw=ref_ccw)
1054 succs[ref_ccw]["cw"] = end_node
1055 succs[cw]["ccw"] = end_node
1056 # when (cw == leftmost_nbr), the newly added neighbor is
1057 # already at the end of dict self._succ[start_node] and
1058 # takes the place of the former leftmost_nbr
1059 move_leftmost_nbr_to_end = cw != leftmost_nbr
1060 elif ccw is not None:
1061 if ccw not in succs:
1062 raise nx.NetworkXError("Invalid counterclockwise reference node.")
1063 ref_cw = succs[ccw]["cw"]
1064 super().add_edge(start_node, end_node, cw=ref_cw, ccw=ccw)
1065 succs[ref_cw]["ccw"] = end_node
1066 succs[ccw]["cw"] = end_node
1067 move_leftmost_nbr_to_end = True
1068 else:
1069 raise nx.NetworkXError(
1070 "Node already has out-half-edge(s), either cw or ccw reference node required."
1071 )
1072 if move_leftmost_nbr_to_end:
1073 # LRPlanarity (via self.add_half_edge_first()) requires that
1074 # we keep track of the leftmost neighbor, which we accomplish
1075 # by keeping it as the last key in dict self._succ[start_node]
1076 succs[leftmost_nbr] = succs.pop(leftmost_nbr)
1078 else:
1079 if cw is not None or ccw is not None:
1080 raise nx.NetworkXError("Invalid reference node.")
1081 # adding the first edge out of start_node
1082 super().add_edge(start_node, end_node, ccw=end_node, cw=end_node)
1084 def check_structure(self):
1085 """Runs without exceptions if this object is valid.
1087 Checks that the following properties are fulfilled:
1089 * Edges go in both directions (because the edge attributes differ).
1090 * Every edge has a 'cw' and 'ccw' attribute which corresponds to a
1091 correct planar embedding.
1093 Running this method verifies that the underlying Graph must be planar.
1095 Raises
1096 ------
1097 NetworkXException
1098 This exception is raised with a short explanation if the
1099 PlanarEmbedding is invalid.
1100 """
1101 # Check fundamental structure
1102 for v in self:
1103 try:
1104 sorted_nbrs = set(self.neighbors_cw_order(v))
1105 except KeyError as err:
1106 msg = f"Bad embedding. Missing orientation for a neighbor of {v}"
1107 raise nx.NetworkXException(msg) from err
1109 unsorted_nbrs = set(self[v])
1110 if sorted_nbrs != unsorted_nbrs:
1111 msg = "Bad embedding. Edge orientations not set correctly."
1112 raise nx.NetworkXException(msg)
1113 for w in self[v]:
1114 # Check if opposite half-edge exists
1115 if not self.has_edge(w, v):
1116 msg = "Bad embedding. Opposite half-edge is missing."
1117 raise nx.NetworkXException(msg)
1119 # Check planarity
1120 counted_half_edges = set()
1121 for component in nx.connected_components(self):
1122 if len(component) == 1:
1123 # Don't need to check single node component
1124 continue
1125 num_nodes = len(component)
1126 num_half_edges = 0
1127 num_faces = 0
1128 for v in component:
1129 for w in self.neighbors_cw_order(v):
1130 num_half_edges += 1
1131 if (v, w) not in counted_half_edges:
1132 # We encountered a new face
1133 num_faces += 1
1134 # Mark all half-edges belonging to this face
1135 self.traverse_face(v, w, counted_half_edges)
1136 num_edges = num_half_edges // 2 # num_half_edges is even
1137 if num_nodes - num_edges + num_faces != 2:
1138 # The result does not match Euler's formula
1139 msg = "Bad embedding. The graph does not match Euler's formula"
1140 raise nx.NetworkXException(msg)
1142 def add_half_edge_ccw(self, start_node, end_node, reference_neighbor):
1143 """Adds a half-edge from start_node to end_node.
1145 The half-edge is added counter clockwise next to the existing half-edge
1146 (start_node, reference_neighbor).
1148 Parameters
1149 ----------
1150 start_node : node
1151 Start node of inserted edge.
1152 end_node : node
1153 End node of inserted edge.
1154 reference_neighbor: node
1155 End node of reference edge.
1157 Raises
1158 ------
1159 NetworkXException
1160 If the reference_neighbor does not exist.
1162 See Also
1163 --------
1164 add_half_edge
1165 add_half_edge_cw
1166 connect_components
1168 """
1169 self.add_half_edge(start_node, end_node, cw=reference_neighbor)
1171 def add_half_edge_cw(self, start_node, end_node, reference_neighbor):
1172 """Adds a half-edge from start_node to end_node.
1174 The half-edge is added clockwise next to the existing half-edge
1175 (start_node, reference_neighbor).
1177 Parameters
1178 ----------
1179 start_node : node
1180 Start node of inserted edge.
1181 end_node : node
1182 End node of inserted edge.
1183 reference_neighbor: node
1184 End node of reference edge.
1186 Raises
1187 ------
1188 NetworkXException
1189 If the reference_neighbor does not exist.
1191 See Also
1192 --------
1193 add_half_edge
1194 add_half_edge_ccw
1195 connect_components
1196 """
1197 self.add_half_edge(start_node, end_node, ccw=reference_neighbor)
1199 def remove_edge(self, u, v):
1200 """Remove the edge between u and v.
1202 Parameters
1203 ----------
1204 u, v : nodes
1205 Remove the half-edges (u, v) and (v, u) and update the
1206 edge ordering around the removed edge.
1208 Raises
1209 ------
1210 NetworkXError
1211 If there is not an edge between u and v.
1213 See Also
1214 --------
1215 remove_edges_from : remove a collection of edges
1216 """
1217 try:
1218 succs_u = self._succ[u]
1219 succs_v = self._succ[v]
1220 uv_cw = succs_u[v]["cw"]
1221 uv_ccw = succs_u[v]["ccw"]
1222 vu_cw = succs_v[u]["cw"]
1223 vu_ccw = succs_v[u]["ccw"]
1224 del succs_u[v]
1225 del self._pred[v][u]
1226 del succs_v[u]
1227 del self._pred[u][v]
1228 if v != uv_cw:
1229 succs_u[uv_cw]["ccw"] = uv_ccw
1230 succs_u[uv_ccw]["cw"] = uv_cw
1231 if u != vu_cw:
1232 succs_v[vu_cw]["ccw"] = vu_ccw
1233 succs_v[vu_ccw]["cw"] = vu_cw
1234 except KeyError as err:
1235 raise nx.NetworkXError(
1236 f"The edge {u}-{v} is not in the planar embedding."
1237 ) from err
1238 nx._clear_cache(self)
1240 def remove_edges_from(self, ebunch):
1241 """Remove all edges specified in ebunch.
1243 Parameters
1244 ----------
1245 ebunch: list or container of edge tuples
1246 Each pair of half-edges between the nodes given in the tuples
1247 will be removed from the graph. The nodes can be passed as:
1249 - 2-tuples (u, v) half-edges (u, v) and (v, u).
1250 - 3-tuples (u, v, k) where k is ignored.
1252 See Also
1253 --------
1254 remove_edge : remove a single edge
1256 Notes
1257 -----
1258 Will fail silently if an edge in ebunch is not in the graph.
1260 Examples
1261 --------
1262 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1263 >>> ebunch = [(1, 2), (2, 3)]
1264 >>> G.remove_edges_from(ebunch)
1265 """
1266 for e in ebunch:
1267 u, v = e[:2] # ignore edge data
1268 # assuming that the PlanarEmbedding is valid, if the half_edge
1269 # (u, v) is in the graph, then so is half_edge (v, u)
1270 if u in self._succ and v in self._succ[u]:
1271 self.remove_edge(u, v)
1273 def connect_components(self, v, w):
1274 """Adds half-edges for (v, w) and (w, v) at some position.
1276 This method should only be called if v and w are in different
1277 components, or it might break the embedding.
1278 This especially means that if `connect_components(v, w)`
1279 is called it is not allowed to call `connect_components(w, v)`
1280 afterwards. The neighbor orientations in both directions are
1281 all set correctly after the first call.
1283 Parameters
1284 ----------
1285 v : node
1286 w : node
1288 See Also
1289 --------
1290 add_half_edge
1291 """
1292 if v in self._succ and self._succ[v]:
1293 ref = next(reversed(self._succ[v]))
1294 else:
1295 ref = None
1296 self.add_half_edge(v, w, cw=ref)
1297 if w in self._succ and self._succ[w]:
1298 ref = next(reversed(self._succ[w]))
1299 else:
1300 ref = None
1301 self.add_half_edge(w, v, cw=ref)
1303 def add_half_edge_first(self, start_node, end_node):
1304 """Add a half-edge and set end_node as start_node's leftmost neighbor.
1306 The new edge is inserted counterclockwise with respect to the current
1307 leftmost neighbor, if there is one.
1309 Parameters
1310 ----------
1311 start_node : node
1312 end_node : node
1314 See Also
1315 --------
1316 add_half_edge
1317 connect_components
1318 """
1319 succs = self._succ.get(start_node)
1320 # the leftmost neighbor is the last entry in the
1321 # self._succ[start_node] dict
1322 leftmost_nbr = next(reversed(succs)) if succs else None
1323 self.add_half_edge(start_node, end_node, cw=leftmost_nbr)
1325 def next_face_half_edge(self, v, w):
1326 """Returns the following half-edge left of a face.
1328 Parameters
1329 ----------
1330 v : node
1331 w : node
1333 Returns
1334 -------
1335 half-edge : tuple
1336 """
1337 new_node = self[w][v]["ccw"]
1338 return w, new_node
1340 def traverse_face(self, v, w, mark_half_edges=None):
1341 """Returns nodes on the face that belong to the half-edge (v, w).
1343 The face that is traversed lies to the right of the half-edge (in an
1344 orientation where v is below w).
1346 Optionally it is possible to pass a set to which all encountered half
1347 edges are added. Before calling this method, this set must not include
1348 any half-edges that belong to the face.
1350 Parameters
1351 ----------
1352 v : node
1353 Start node of half-edge.
1354 w : node
1355 End node of half-edge.
1356 mark_half_edges: set, optional
1357 Set to which all encountered half-edges are added.
1359 Returns
1360 -------
1361 face : list
1362 A list of nodes that lie on this face.
1363 """
1364 if mark_half_edges is None:
1365 mark_half_edges = set()
1367 face_nodes = [v]
1368 mark_half_edges.add((v, w))
1369 prev_node = v
1370 cur_node = w
1371 # Last half-edge is (incoming_node, v)
1372 incoming_node = self[v][w]["cw"]
1374 while cur_node != v or prev_node != incoming_node:
1375 face_nodes.append(cur_node)
1376 prev_node, cur_node = self.next_face_half_edge(prev_node, cur_node)
1377 if (prev_node, cur_node) in mark_half_edges:
1378 raise nx.NetworkXException("Bad planar embedding. Impossible face.")
1379 mark_half_edges.add((prev_node, cur_node))
1381 return face_nodes
1383 def is_directed(self):
1384 """A valid PlanarEmbedding is undirected.
1386 All reverse edges are contained, i.e. for every existing
1387 half-edge (v, w) the half-edge in the opposite direction (w, v) is also
1388 contained.
1389 """
1390 return False
1392 def copy(self, as_view=False):
1393 if as_view is True:
1394 return nx.graphviews.generic_graph_view(self)
1395 G = self.__class__()
1396 G.graph.update(self.graph)
1397 G.add_nodes_from((n, d.copy()) for n, d in self._node.items())
1398 super(self.__class__, G).add_edges_from(
1399 (u, v, datadict.copy())
1400 for u, nbrs in self._adj.items()
1401 for v, datadict in nbrs.items()
1402 )
1403 return G
1405 def to_undirected(self, reciprocal=False, as_view=False):
1406 """
1407 Returns a non-embedding undirected representation of the graph.
1409 This method strips the planar embedding information and provides
1410 a simple undirected graph representation. While creating the undirected graph,
1411 all edge attributes are retained except the ``"cw"`` and ``"ccw"`` attributes
1412 which are removed from the edge data. Those attributes are specific to
1413 the requirements of planar embeddings.
1415 Parameters
1416 ----------
1417 reciprocal : bool (optional)
1418 Not supported for PlanarEmbedding. This parameter raises an exception
1419 if used. All valid embeddings include reciprocal half-edges by definition,
1420 making this parameter unnecessary.
1421 as_view : bool (optional, default=False)
1422 Not supported for PlanarEmbedding. This parameter raises an exception
1423 if used.
1425 Returns
1426 -------
1427 G : Graph
1428 An undirected graph with the same name and nodes as the PlanarEmbedding.
1429 Edges are included with their data, except for the ``"cw"`` and ``"ccw"``
1430 attributes, which are omitted.
1433 Notes
1434 -----
1435 - If edges exist in both directions ``(u, v)`` and ``(v, u)`` in the PlanarEmbedding,
1436 attributes for the resulting undirected edge will be combined, excluding ``"cw"``
1437 and ``"ccw"``.
1438 - A deep copy is made of the other edge attributes as well as the
1439 node and graph attributes, ensuring independence of the resulting graph.
1440 - Subclass-specific data structures used in the original graph may not transfer
1441 to the undirected graph. The resulting graph will be of type ``nx.Graph``.
1442 """
1444 if reciprocal:
1445 raise ValueError(
1446 "'reciprocal=True' is not supported for PlanarEmbedding.\n"
1447 "All valid embeddings include reciprocal half-edges by definition,\n"
1448 "making this parameter unnecessary."
1449 )
1451 if as_view:
1452 raise ValueError("'as_view=True' is not supported for PlanarEmbedding.")
1454 graph_class = self.to_undirected_class()
1455 G = graph_class()
1456 G.graph.update(deepcopy(self.graph))
1457 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1458 G.add_edges_from(
1459 (u, v, {k: deepcopy(v) for k, v in d.items() if k not in {"cw", "ccw"}})
1460 for u, nbrs in self._adj.items()
1461 for v, d in nbrs.items()
1462 )
1463 return G