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