1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | |
9 | #include <boost/graph/adjacency_list.hpp> |
10 | #include <boost/graph/properties.hpp> |
11 | #include <boost/graph/boyer_myrvold_planar_test.hpp> |
12 | #include <boost/property_map/property_map.hpp> |
13 | #include <boost/property_map/vector_property_map.hpp> |
14 | #include <boost/core/lightweight_test.hpp> |
15 | |
16 | using namespace boost; |
17 | |
18 | struct VertexIndexUpdater |
19 | { |
20 | template < typename Graph > void reset(Graph& g) |
21 | { |
22 | typename property_map< Graph, vertex_index_t >::type index |
23 | = get(vertex_index, g); |
24 | typename graph_traits< Graph >::vertex_iterator vi, vi_end; |
25 | typename graph_traits< Graph >::vertices_size_type cnt = 0; |
26 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
27 | put(index, *vi, cnt++); |
28 | } |
29 | }; |
30 | |
31 | struct NoVertexIndexUpdater |
32 | { |
33 | template < typename Graph > void reset(Graph&) {} |
34 | }; |
35 | |
36 | template < typename Graph, typename VertexIndexUpdater > |
37 | void test_K_5(VertexIndexUpdater vertex_index) |
38 | { |
39 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; |
40 | |
41 | Graph g; |
42 | vertex_t v1 = add_vertex(g); |
43 | vertex_t v2 = add_vertex(g); |
44 | vertex_t v3 = add_vertex(g); |
45 | vertex_t v4 = add_vertex(g); |
46 | vertex_t v5 = add_vertex(g); |
47 | vertex_index.reset(g); |
48 | |
49 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
50 | add_edge(v1, v2, g); |
51 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
52 | add_edge(v1, v3, g); |
53 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
54 | add_edge(v1, v4, g); |
55 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
56 | add_edge(v1, v5, g); |
57 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
58 | add_edge(v2, v3, g); |
59 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
60 | add_edge(v2, v4, g); |
61 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
62 | add_edge(v2, v5, g); |
63 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
64 | add_edge(v3, v4, g); |
65 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
66 | add_edge(v3, v5, g); |
67 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
68 | |
69 | // This edge should make the graph non-planar |
70 | add_edge(v4, v5, g); |
71 | BOOST_TEST(!boyer_myrvold_planarity_test(g)); |
72 | } |
73 | |
74 | template < typename Graph, typename VertexIndexUpdater > |
75 | void test_K_3_3(VertexIndexUpdater vertex_index) |
76 | { |
77 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; |
78 | |
79 | Graph g; |
80 | vertex_t v1 = add_vertex(g); |
81 | vertex_t v2 = add_vertex(g); |
82 | vertex_t v3 = add_vertex(g); |
83 | vertex_t v4 = add_vertex(g); |
84 | vertex_t v5 = add_vertex(g); |
85 | vertex_t v6 = add_vertex(g); |
86 | vertex_index.reset(g); |
87 | |
88 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
89 | add_edge(v1, v4, g); |
90 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
91 | add_edge(v1, v5, g); |
92 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
93 | add_edge(v1, v6, g); |
94 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
95 | add_edge(v2, v4, g); |
96 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
97 | add_edge(v2, v5, g); |
98 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
99 | add_edge(v2, v6, g); |
100 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
101 | add_edge(v3, v4, g); |
102 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
103 | add_edge(v3, v5, g); |
104 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
105 | |
106 | // This edge should make the graph non-planar |
107 | add_edge(v3, v6, g); |
108 | BOOST_TEST(!boyer_myrvold_planarity_test(g)); |
109 | } |
110 | |
111 | // This test creates a maximal planar graph on num_vertices vertices, |
112 | // then, if num_vertices is at least 5, adds an additional edge to |
113 | // create a non-planar graph. |
114 | |
115 | template < typename Graph, typename VertexIndexUpdater > |
116 | void test_maximal_planar( |
117 | VertexIndexUpdater vertex_index, std::size_t num_vertices) |
118 | { |
119 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; |
120 | |
121 | Graph g; |
122 | std::vector< vertex_t > vmap; |
123 | for (std::size_t i = 0; i < num_vertices; ++i) |
124 | vmap.push_back(add_vertex(g)); |
125 | |
126 | vertex_index.reset(g); |
127 | |
128 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
129 | // create a cycle |
130 | for (std::size_t i = 0; i < num_vertices; ++i) |
131 | { |
132 | add_edge(vmap[i], vmap[(i + 1) % num_vertices], g); |
133 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
134 | } |
135 | |
136 | // triangulate the interior of the cycle. |
137 | for (std::size_t i = 2; i < num_vertices - 1; ++i) |
138 | { |
139 | add_edge(vmap[0], vmap[i], g); |
140 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
141 | } |
142 | |
143 | // triangulate the exterior of the cycle. |
144 | for (std::size_t i = 3; i < num_vertices; ++i) |
145 | { |
146 | add_edge(vmap[1], vmap[i], g); |
147 | BOOST_TEST(boyer_myrvold_planarity_test(g)); |
148 | } |
149 | |
150 | // Now add an additional edge, forcing the graph to be non-planar. |
151 | if (num_vertices > 4) |
152 | { |
153 | add_edge(vmap[2], vmap[4], g); |
154 | BOOST_TEST(!boyer_myrvold_planarity_test(g)); |
155 | } |
156 | } |
157 | |
158 | int main(int, char*[]) |
159 | { |
160 | typedef adjacency_list< vecS, vecS, undirectedS, |
161 | property< vertex_index_t, int > > |
162 | VVgraph_t; |
163 | |
164 | typedef adjacency_list< vecS, listS, undirectedS, |
165 | property< vertex_index_t, int > > |
166 | VLgraph_t; |
167 | |
168 | typedef adjacency_list< listS, vecS, undirectedS, |
169 | property< vertex_index_t, int > > |
170 | LVgraph_t; |
171 | |
172 | typedef adjacency_list< listS, listS, undirectedS, |
173 | property< vertex_index_t, int > > |
174 | LLgraph_t; |
175 | |
176 | typedef adjacency_list< setS, setS, undirectedS, |
177 | property< vertex_index_t, int > > |
178 | SSgraph_t; |
179 | |
180 | test_K_5< VVgraph_t >(vertex_index: NoVertexIndexUpdater()); |
181 | test_K_3_3< VVgraph_t >(vertex_index: NoVertexIndexUpdater()); |
182 | test_maximal_planar< VVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 3); |
183 | test_maximal_planar< VVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 6); |
184 | test_maximal_planar< VVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 10); |
185 | test_maximal_planar< VVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 20); |
186 | test_maximal_planar< VVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 50); |
187 | |
188 | test_K_5< VLgraph_t >(vertex_index: VertexIndexUpdater()); |
189 | test_K_3_3< VLgraph_t >(vertex_index: VertexIndexUpdater()); |
190 | test_maximal_planar< VLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 3); |
191 | test_maximal_planar< VLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 6); |
192 | test_maximal_planar< VLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 10); |
193 | test_maximal_planar< VLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 20); |
194 | test_maximal_planar< VLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 50); |
195 | |
196 | test_K_5< LVgraph_t >(vertex_index: NoVertexIndexUpdater()); |
197 | test_K_3_3< LVgraph_t >(vertex_index: NoVertexIndexUpdater()); |
198 | test_maximal_planar< LVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 3); |
199 | test_maximal_planar< LVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 6); |
200 | test_maximal_planar< LVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 10); |
201 | test_maximal_planar< LVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 20); |
202 | test_maximal_planar< LVgraph_t >(vertex_index: NoVertexIndexUpdater(), num_vertices: 50); |
203 | |
204 | test_K_5< LLgraph_t >(vertex_index: VertexIndexUpdater()); |
205 | test_K_3_3< LLgraph_t >(vertex_index: VertexIndexUpdater()); |
206 | test_maximal_planar< LLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 3); |
207 | test_maximal_planar< LLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 6); |
208 | test_maximal_planar< LLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 10); |
209 | test_maximal_planar< LLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 20); |
210 | test_maximal_planar< LLgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 50); |
211 | |
212 | test_K_5< SSgraph_t >(vertex_index: VertexIndexUpdater()); |
213 | test_K_3_3< SSgraph_t >(vertex_index: VertexIndexUpdater()); |
214 | test_maximal_planar< SSgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 3); |
215 | test_maximal_planar< SSgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 6); |
216 | test_maximal_planar< SSgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 10); |
217 | test_maximal_planar< SSgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 20); |
218 | test_maximal_planar< SSgraph_t >(vertex_index: VertexIndexUpdater(), num_vertices: 50); |
219 | |
220 | return boost::report_errors(); |
221 | } |
222 | |