Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/planarity.py @ 0:4f3585e2f14b draft default tip

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