Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.5 KB)

1
import networkx as nx
2
from nose.tools import assert_equals, assert_true, raises
3
from networkx.algorithms.planarity import get_counterexample
4
from networkx.algorithms.planarity import get_counterexample_recursive
5
from networkx.algorithms.planarity import check_planarity_recursive
6

    
7

    
8
class TestLRPlanarity:
9
    """Nose Unit tests for the :mod:`networkx.algorithms.planarity` module.
10

11
    Tests three things:
12
    1. Check that the result is correct
13
        (returns planar if and only if the graph is actually planar)
14
    2. In case a counter example is returned: Check if it is correct
15
    3. In case an embedding is returned: Check if its actually an embedding
16
    """
17

    
18
    @staticmethod
19
    def check_graph(G, is_planar=None):
20
        """Raises an exception if the lr_planarity check returns a wrong result
21

22
        Parameters
23
        ----------
24
        G : NetworkX graph
25
        is_planar : bool
26
            The expected result of the planarity check.
27
            If set to None only counter example or embedding are verified.
28

29
        """
30

    
31
        # obtain results of planarity check
32
        is_planar_lr, result = nx.check_planarity(G, True)
33
        is_planar_lr_rec, result_rec = check_planarity_recursive(G, True)
34

    
35
        if is_planar is not None:
36
            # set a message for the assert
37
            if is_planar:
38
                msg = "Wrong planarity check result. Should be planar."
39
            else:
40
                msg = "Wrong planarity check result. Should be non-planar."
41

    
42
            # check if the result is as expected
43
            assert_equals(is_planar, is_planar_lr, msg)
44
            assert_equals(is_planar, is_planar_lr_rec, msg)
45

    
46
        if is_planar_lr:
47
            # check embedding
48
            check_embedding(G, result)
49
            check_embedding(G, result_rec)
50
        else:
51
            # check counter example
52
            check_counterexample(G, result)
53
            check_counterexample(G, result_rec)
54

    
55
    def test_simple_planar_graph(self):
56
        e = [(1, 2), (2, 3), (3, 4), (4, 6), (6, 7), (7, 1), (1, 5),
57
             (5, 2), (2, 4), (4, 5), (5, 7)]
58
        self.check_graph(nx.Graph(e), is_planar=True)
59

    
60
    def test_planar_with_selfloop(self):
61
        e = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 3),
62
             (1, 5), (2, 5), (2, 4), (3, 4), (3, 5), (4, 5)]
63
        self.check_graph(nx.Graph(e), is_planar=True)
64

    
65
    def test_k3_3(self):
66
        self.check_graph(nx.complete_bipartite_graph(3, 3), is_planar=False)
67

    
68
    def test_k5(self):
69
        self.check_graph(nx.complete_graph(5), is_planar=False)
70

    
71
    def test_multiple_components_planar(self):
72
        e = [(1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4)]
73
        self.check_graph(nx.Graph(e), is_planar=True)
74

    
75
    def test_multiple_components_non_planar(self):
76
        G = nx.complete_graph(5)
77
        # add another planar component to the non planar component
78
        # G stays non planar
79
        G.add_edges_from([(6, 7), (7, 8), (8, 6)])
80
        self.check_graph(G, is_planar=False)
81

    
82
    def test_non_planar_with_selfloop(self):
83
        G = nx.complete_graph(5)
84
        # add self loops
85
        for i in range(5):
86
            G.add_edge(i, i)
87
        self.check_graph(G, is_planar=False)
88

    
89
    def test_non_planar1(self):
90
        # tests a graph that has no subgraph directly isomorph to K5 or K3_3
91
        e = [(1, 5), (1, 6), (1, 7), (2, 6), (2, 3), (3, 5), (3, 7), (4, 5),
92
             (4, 6), (4, 7)]
93
        self.check_graph(nx.Graph(e), is_planar=False)
94

    
95
    def test_loop(self):
96
        # test a graph with a selfloop
97
        e = [(1, 2), (2, 2)]
98
        G = nx.Graph(e)
99
        self.check_graph(G, is_planar=True)
100

    
101
    def test_comp(self):
102
        # test multiple component graph
103
        e = [(1, 2), (3, 4)]
104
        G = nx.Graph(e)
105
        G.remove_edge(1, 2)
106
        self.check_graph(G, is_planar=True)
107

    
108
    def test_goldner_harary(self):
109
        # test goldner-harary graph (a maximal planar graph)
110
        e = [
111
            (1, 2), (1, 3), (1, 4), (1, 5), (1, 7), (1, 8), (1, 10),
112
            (1, 11), (2, 3), (2, 4), (2, 6), (2, 7), (2, 9), (2, 10),
113
            (2, 11), (3, 4), (4, 5), (4, 6), (4, 7), (5, 7), (6, 7),
114
            (7, 8), (7, 9), (7, 10), (8, 10), (9, 10), (10, 11)
115
        ]
116
        G = nx.Graph(e)
117
        self.check_graph(G, is_planar=True)
118

    
119
    def test_planar_multigraph(self):
120
        G = nx.MultiGraph([(1, 2), (1, 2), (1, 2), (1, 2), (2, 3), (3, 1)])
121
        self.check_graph(G, is_planar=True)
122

    
123
    def test_non_planar_multigraph(self):
124
        G = nx.MultiGraph(nx.complete_graph(5))
125
        G.add_edges_from([(1, 2)]*5)
126
        self.check_graph(G, is_planar=False)
127

    
128
    def test_planar_digraph(self):
129
        G = nx.DiGraph([
130
            (1, 2), (2, 3), (2, 4), (4, 1), (4, 2), (1, 4), (3, 2)
131
        ])
132
        self.check_graph(G, is_planar=True)
133

    
134
    def test_non_planar_digraph(self):
135
        G = nx.DiGraph(nx.complete_graph(5))
136
        G.remove_edge(1, 2)
137
        G.remove_edge(4, 1)
138
        self.check_graph(G, is_planar=False)
139

    
140
    def test_single_component(self):
141
        # Test a graph with only a single node
142
        G = nx.Graph()
143
        G.add_node(1)
144
        self.check_graph(G, is_planar=True)
145

    
146
    def test_graph1(self):
147
        G = nx.OrderedGraph([
148
            (3, 10), (2, 13), (1, 13), (7, 11), (0, 8), (8, 13), (0, 2),
149
            (0, 7), (0, 10), (1, 7)
150
        ])
151
        self.check_graph(G, is_planar=True)
152

    
153
    def test_graph2(self):
154
        G = nx.OrderedGraph([
155
            (1, 2), (4, 13), (0, 13), (4, 5), (7, 10), (1, 7), (0, 3), (2, 6),
156
            (5, 6), (7, 13), (4, 8), (0, 8), (0, 9), (2, 13), (6, 7), (3, 6),
157
            (2, 8)
158
        ])
159
        self.check_graph(G, is_planar=False)
160

    
161
    def test_graph3(self):
162
        G = nx.OrderedGraph([
163
            (0, 7), (3, 11), (3, 4), (8, 9), (4, 11), (1, 7), (1, 13), (1, 11),
164
            (3, 5), (5, 7), (1, 3), (0, 4), (5, 11), (5, 13)
165
        ])
166
        self.check_graph(G, is_planar=False)
167

    
168
    @raises(nx.NetworkXException)
169
    def test_counterexample_planar(self):
170
        # Try to get a counterexample of a planar graph
171
        G = nx.Graph()
172
        G.add_node(1)
173
        get_counterexample(G)
174

    
175
    @raises(nx.NetworkXException)
176
    def test_counterexample_planar_recursive(self):
177
        # Try to get a counterexample of a planar graph
178
        G = nx.Graph()
179
        G.add_node(1)
180
        get_counterexample_recursive(G)
181

    
182

    
183
def check_embedding(G, embedding):
184
    """Raises an exception if the combinatorial embedding is not correct
185

186
    Parameters
187
    ----------
188
    G : NetworkX graph
189
    embedding : a dict mapping nodes to a list of edges
190
        This specifies the ordering of the outgoing edges from a node for
191
        a combinatorial embedding
192

193
    Notes
194
    -----
195
    Checks the following things:
196
        - The type of the embedding is correct
197
        - The nodes and edges match the original graph
198
        - Every half edge has its matching opposite half edge
199
        - No intersections of edges (checked by Euler's formula)
200
    """
201

    
202
    if not isinstance(embedding, nx.PlanarEmbedding):
203
        raise nx.NetworkXException(
204
            "Bad embedding. Not of type nx.PlanarEmbedding")
205

    
206
    # Check structure
207
    embedding.check_structure()
208

    
209
    # Check that graphs are equivalent
210

    
211
    assert_equals(set(G.nodes), set(embedding.nodes),
212
                  "Bad embedding. Nodes don't match the original graph.")
213

    
214
    # Check that the edges are equal
215
    g_edges = set()
216
    for edge in G.edges:
217
        if edge[0] != edge[1]:
218
            g_edges.add((edge[0], edge[1]))
219
            g_edges.add((edge[1], edge[0]))
220
    assert_equals(g_edges, set(embedding.edges),
221
                  "Bad embedding. Edges don't match the original graph.")
222

    
223

    
224
def check_counterexample(G, sub_graph):
225
    """Raises an exception if the counterexample is wrong.
226

227
    Parameters
228
    ----------
229
    G : NetworkX graph
230
    subdivision_nodes : set
231
        A set of nodes inducing a subgraph as a counterexample
232
    """
233
    # 1. Create the sub graph
234
    sub_graph = nx.Graph(sub_graph)
235

    
236
    # 2. Remove self loops
237
    for u in sub_graph:
238
        if sub_graph.has_edge(u, u):
239
            sub_graph.remove_edge(u, u)
240

    
241
    # keep track of nodes we might need to contract
242
    contract = list(sub_graph)
243

    
244
    # 3. Contract Edges
245
    while len(contract) > 0:
246
        contract_node = contract.pop()
247
        if contract_node not in sub_graph:
248
            # Node was already contracted
249
            continue
250
        degree = sub_graph.degree[contract_node]
251
        # Check if we can remove the node
252
        if degree == 2:
253
            # Get the two neighbors
254
            neighbors = iter(sub_graph[contract_node])
255
            u = next(neighbors)
256
            v = next(neighbors)
257
            # Save nodes for later
258
            contract.append(u)
259
            contract.append(v)
260
            # Contract edge
261
            sub_graph.remove_node(contract_node)
262
            sub_graph.add_edge(u, v)
263

    
264
    # 4. Check for isomorphism with K5 or K3_3 graphs
265
    if len(sub_graph) == 5:
266
        if not nx.is_isomorphic(nx.complete_graph(5), sub_graph):
267
            raise nx.NetworkXException("Bad counter example.")
268
    elif len(sub_graph) == 6:
269
        if not nx.is_isomorphic(nx.complete_bipartite_graph(3, 3), sub_graph):
270
            raise nx.NetworkXException("Bad counter example.")
271
    else:
272
        raise nx.NetworkXException("Bad counter example.")
273

    
274

    
275
class TestPlanarEmbeddingClass:
276
    def test_get_data(self):
277
        embedding = self.get_star_embedding(3)
278
        data = embedding.get_data()
279
        data_cmp = {0: [2, 1], 1: [0], 2: [0]}
280
        assert_equals(data, data_cmp)
281

    
282
    @raises(nx.NetworkXException)
283
    def test_missing_edge_orientation(self):
284
        embedding = nx.PlanarEmbedding()
285
        embedding.add_edge(1, 2)
286
        embedding.add_edge(2, 1)
287
        # Invalid structure because the orientation of the edge was not set
288
        embedding.check_structure()
289

    
290
    @raises(nx.NetworkXException)
291
    def test_invalid_edge_orientation(self):
292
        embedding = nx.PlanarEmbedding()
293
        embedding.add_half_edge_first(1, 2)
294
        embedding.add_half_edge_first(2, 1)
295
        embedding.add_edge(1, 3)
296
        embedding.check_structure()
297

    
298
    @raises(nx.NetworkXException)
299
    def test_missing_half_edge(self):
300
        embedding = nx.PlanarEmbedding()
301
        embedding.add_half_edge_first(1, 2)
302
        # Invalid structure because other half edge is missing
303
        embedding.check_structure()
304

    
305
    @raises(nx.NetworkXException)
306
    def test_not_fulfilling_euler_formula(self):
307
        embedding = nx.PlanarEmbedding()
308
        for i in range(5):
309
            for j in range(5):
310
                if i != j:
311
                    embedding.add_half_edge_first(i, j)
312
        embedding.check_structure()
313

    
314
    @raises(nx.NetworkXException)
315
    def test_missing_reference(self):
316
        embedding = nx.PlanarEmbedding()
317
        embedding.add_half_edge_cw(1, 2, 3)
318

    
319
    def test_connect_components(self):
320
        embedding = nx.PlanarEmbedding()
321
        embedding.connect_components(1, 2)
322

    
323
    def test_successful_face_traversal(self):
324
        embedding = nx.PlanarEmbedding()
325
        embedding.add_half_edge_first(1, 2)
326
        embedding.add_half_edge_first(2, 1)
327
        face = embedding.traverse_face(1, 2)
328
        assert_equals(face, [1, 2])
329

    
330
    @raises(nx.NetworkXException)
331
    def test_unsuccessful_face_traversal(self):
332
        embedding = nx.PlanarEmbedding()
333
        embedding.add_edge(1, 2, ccw=2, cw=3)
334
        embedding.add_edge(2, 1, ccw=1, cw=3)
335
        embedding.traverse_face(1, 2)
336

    
337
    @staticmethod
338
    def get_star_embedding(n):
339
        embedding = nx.PlanarEmbedding()
340
        for i in range(1, n):
341
            embedding.add_half_edge_first(0, i)
342
            embedding.add_half_edge_first(i, 0)
343
        return embedding