1"""Provides unit tests to verify that the planarity testing algorithm is functioning correctly."""
2
3import unittest
4
5from ..pygraph import UndirectedGraph, is_planar, build_cycle_graph, build_k5_graph, build_k33_graph, build_groetzch_graph, build_franklin_graph, build_chvatal_graph
6from . import utility_functions
7
8
9class IsPlanarTest(unittest.TestCase):
10    def test_empty_graph_is_planar(self):
11        """Does the ''is_planar'' function classify an empty graph as planar?"""
12        graph = UndirectedGraph()
13
14        expected = True
15        planarity = is_planar(graph)
16
17        self.assertEqual(expected, planarity)
18
19    def test_single_node_graph_is_planar(self):
20        """Does the ''is_planar'' function classify a single-node graph as planar?"""
21        graph = utility_functions.build_single_node_graph()
22
23        expected = True
24        planarity = is_planar(graph)
25
26        self.assertEqual(expected, planarity)
27
28    def test_2_node_graph_is_planar(self):
29        """Does the ''is_planar'' function classify a 2-node graph as planar?"""
30        graph = utility_functions.build_2_node_graph()
31
32        expected = True
33        planarity = is_planar(graph)
34
35        self.assertEqual(expected, planarity)
36
37    def test_triangle_graph_is_planar(self):
38        """Does the ''is_planar'' function classify a triangle graph as planar?"""
39        graph = utility_functions.build_triangle_graph()
40
41        expected = True
42        planarity = is_planar(graph)
43
44        self.assertEqual(expected, planarity)
45
46    def test_simple_planar_graph(self):
47        """Does the ''is_planar'' function correctly classify the simple test graph as planar?"""
48        graph = utility_functions.build_simple_test_graph()
49
50        expected = True
51        planarity = is_planar(graph)
52
53        self.assertEqual(expected, planarity)
54
55    def test_disconnected_triangle_graphs_is_planar(self):
56        """Does the ''is_planar'' function correctly classify the disconnected graph
57        composed of triangle graphs as planar?
58        """
59        graph = utility_functions.build_disconnected_test_graph()
60
61        expected = True
62        planarity = is_planar(graph)
63
64        self.assertEqual(expected, planarity)
65
66    def test_tiny_cycle_graph_is_planar(self):
67        """Does the ''is_planar'' function correctly classify a tiny cycle graph as planar?"""
68        graph = build_cycle_graph(4)
69
70        expected = True
71        planarity = is_planar(graph)
72
73        self.assertEqual(expected, planarity)
74
75    def test_small_cycle_graph_is_planar(self):
76        """Does the ''is_planar'' function correctly classify a small cycle graph as planar?"""
77        graph = build_cycle_graph(10)
78
79        expected = True
80        planarity = is_planar(graph)
81
82        self.assertEqual(expected, planarity)
83
84    def test_large_cycle_graph_is_planar(self):
85        """Does the ''is_planar'' function correctly classify a large cycle graph as planar?"""
86        graph = build_cycle_graph(100)
87
88        expected = True
89        planarity = is_planar(graph)
90
91        self.assertEqual(expected, planarity)
92
93    def test_really_large_cycle_graph_is_planar(self):
94        """Does the ''is_planar'' function correctly classify a really large cycle graph as planar?"""
95        try:
96            graph = build_cycle_graph(1000)
97
98            expected = True
99            planarity = is_planar(graph)
100
101            self.assertEqual(expected, planarity)
102        except RuntimeError as e:
103            if e.args[0] == 'maximum recursion depth exceeded':
104                #Large graphs cause recursion errors. Exception caught, as expected.
105                pass
106            else:
107                raise e
108
109
110    def test_k5_graph_not_planar(self):
111        """Does the ''is_planar'' function correctly classify the K5 graph as non-planar?"""
112        graph = build_k5_graph()
113
114        expected = False
115        planarity = is_planar(graph)
116
117        self.assertEqual(expected, planarity)
118
119    def test_k33_graph_not_planar(self):
120        """Does the ''is_planar'' function correctly classify the K3,3 graph as non-planar?"""
121        graph = build_k33_graph()
122
123        expected = False
124        planarity = is_planar(graph)
125
126        self.assertEqual(expected, planarity)
127
128    def test_k5_subgraph_not_planar(self):
129        """Does the ''is_planar'' function correctly classify a graph with a K5 subgraph as non-planar?"""
130        graph = utility_functions.build_non_planar_test_graph_with_k5_subgraph()
131
132        expected = False
133        planarity = is_planar(graph)
134
135        self.assertEqual(expected, planarity)
136
137    def test_disconnected_k5_subgraph_not_planar(self):
138        """Does the ''is_planar'' function correctly classify a graph with a K5 subgraph as non-planar?"""
139        graph = utility_functions.build_non_planar_disconnected_test_graph_with_k5_subgraph()
140
141        expected = False
142        planarity = is_planar(graph)
143
144        self.assertEqual(expected, planarity)
145
146    def test_k33_subgraph_not_planar(self):
147        """Does the ''is_planar'' function correctly classify a graph with a K3,3 subgraph as non-planar?"""
148        graph = utility_functions.build_non_planar_test_graph_with_k33_subgraph()
149
150        expected = False
151        planarity = is_planar(graph)
152
153        self.assertEqual(expected, planarity)
154
155    def test_petersons_graph_not_planar(self):
156        """Does the ''is_planar'' function correctly classify Peterson's graph as non-planar?"""
157        graph = utility_functions.build_petersons_graph()
158
159        expected = False
160        planarity = is_planar(graph)
161
162        self.assertEqual(expected, planarity)
163
164    def test_groetzch_graph_not_planar(self):
165        """Does the ''is_planar'' function correctly classify the Groetzch graph as non-planar?"""
166        graph = build_groetzch_graph()
167
168        expected = False
169        planarity = is_planar(graph)
170
171        self.assertEqual(expected, planarity)
172
173    def test_franklin_graph_not_planar(self):
174        """Does the ''is_planar'' function correctly classify the Franklin graph as non-planar?"""
175        graph = build_franklin_graph()
176
177        expected = False
178        planarity = is_planar(graph)
179
180        self.assertEqual(expected, planarity)
181
182    def test_chvatal_graph_not_planar(self):
183        """Does the ''is_planar'' function correctly classify the Chvatal graph as non-planar?"""
184        graph = build_chvatal_graph()
185
186        expected = False
187        planarity = is_planar(graph)
188
189        self.assertEqual(expected, planarity)
190
191