Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/planarity.py @ 1:56ad4e20f292 draft

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