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
16using namespace boost;
17
18struct 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
31struct NoVertexIndexUpdater
32{
33 template < typename Graph > void reset(Graph&) {}
34};
35
36template < typename Graph, typename VertexIndexUpdater >
37void 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
74template < typename Graph, typename VertexIndexUpdater >
75void 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
115template < typename Graph, typename VertexIndexUpdater >
116void 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
158int 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

source code of boost/libs/graph/test/basic_planarity_test.cpp