Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / planarity.py @ 5cef0f13

History | View | Annotate | Download (37.3 KB)

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