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/make_maximal_planar.hpp>
12 #include <boost/graph/boyer_myrvold_planar_test.hpp>
13 #include <boost/property_map/property_map.hpp>
14 #include <boost/property_map/vector_property_map.hpp>
15 #include <boost/test/minimal.hpp>
16
17
18 using namespace boost;
19
20
21 template <typename Graph>
reset_edge_index(Graph & g)22 void reset_edge_index(Graph& g)
23 {
24 typename property_map<Graph, edge_index_t>::type index = get(edge_index, g);
25 typename graph_traits<Graph>::edge_iterator ei, ei_end;
26 typename graph_traits<Graph>::edges_size_type cnt = 0;
27 for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
28 put(index, *ei, cnt++);
29 }
30
31
32 template <typename Graph>
make_cycle(Graph & g,int size)33 void make_cycle(Graph& g, int size)
34 {
35 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
36
37 vertex_t first_vertex = add_vertex(g);
38 vertex_t prev_vertex = first_vertex;
39
40 for(int i = 1; i < size; ++i)
41 {
42 vertex_t curr_vertex = add_vertex(g);
43 add_edge(curr_vertex, prev_vertex, g);
44 prev_vertex = curr_vertex;
45 }
46
47 add_edge(first_vertex, prev_vertex, g);
48 }
49
50
51 struct UpdateVertexIndex
52 {
53 template <typename Graph>
updateUpdateVertexIndex54 void update(Graph& g)
55 {
56 typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
57 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
58 typename graph_traits<Graph>::vertices_size_type cnt = 0;
59 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
60 put(index, *vi, cnt++);
61 }
62 };
63
64
65 struct NoVertexIndexUpdater
66 {
updateNoVertexIndexUpdater67 template <typename Graph> void update(Graph&) {}
68 };
69
70
71
72 template <typename Graph, typename VertexIndexUpdater>
test_cycle(VertexIndexUpdater vertex_index_updater,int size)73 void test_cycle(VertexIndexUpdater vertex_index_updater, int size)
74 {
75
76 Graph g;
77 make_cycle(g, size);
78 vertex_index_updater.update(g);
79 reset_edge_index(g);
80
81 typedef std::vector< typename graph_traits<Graph>::edge_descriptor > edge_vector_t;
82 typedef std::vector< edge_vector_t > embedding_storage_t;
83 typedef iterator_property_map
84 < typename embedding_storage_t::iterator,
85 typename property_map<Graph, vertex_index_t>::type
86 > embedding_t;
87
88 embedding_storage_t embedding_storage(num_vertices(g));
89 embedding_t embedding(embedding_storage.begin(), get(vertex_index, g));
90
91 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
92 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
93 std::copy(out_edges(*vi,g).first, out_edges(*vi,g).second, std::back_inserter(embedding[*vi]));
94
95 BOOST_CHECK(boyer_myrvold_planarity_test(g));
96 make_maximal_planar(g, embedding);
97 reset_edge_index(g);
98
99 // A graph is maximal planar exactly when it's both
100 // planar and has 3 * num_vertices(g) - 6 edges.
101 BOOST_CHECK(num_edges(g) == 3 * num_vertices(g) - 6);
102 BOOST_CHECK(boyer_myrvold_planarity_test(g));
103
104 }
105
106
107
108
109
test_main(int,char * [])110 int test_main(int, char* [])
111 {
112 typedef adjacency_list
113 <vecS,
114 vecS,
115 undirectedS,
116 property<vertex_index_t, int>,
117 property<edge_index_t, int>
118 >
119 VVgraph_t;
120
121 typedef adjacency_list
122 <vecS,
123 listS,
124 undirectedS,
125 property<vertex_index_t, int>,
126 property<edge_index_t, int>
127 >
128 VLgraph_t;
129
130 typedef adjacency_list
131 <listS,
132 vecS,
133 undirectedS,
134 property<vertex_index_t, int>,
135 property<edge_index_t, int>
136 >
137 LVgraph_t;
138
139 typedef adjacency_list
140 <listS,
141 listS,
142 undirectedS,
143 property<vertex_index_t, int>,
144 property<edge_index_t, int>
145 >
146 LLgraph_t;
147
148 typedef adjacency_list
149 <setS,
150 setS,
151 undirectedS,
152 property<vertex_index_t, int>,
153 property<edge_index_t, int>
154 >
155 SSgraph_t;
156
157 test_cycle<VVgraph_t>(NoVertexIndexUpdater(), 10);
158 test_cycle<VVgraph_t>(NoVertexIndexUpdater(), 50);
159
160 test_cycle<VLgraph_t>(UpdateVertexIndex(), 3);
161 test_cycle<VLgraph_t>(UpdateVertexIndex(), 30);
162
163 test_cycle<LVgraph_t>(NoVertexIndexUpdater(), 15);
164 test_cycle<LVgraph_t>(NoVertexIndexUpdater(), 45);
165
166 test_cycle<LLgraph_t>(UpdateVertexIndex(), 8);
167 test_cycle<LLgraph_t>(UpdateVertexIndex(), 19);
168
169 test_cycle<SSgraph_t>(UpdateVertexIndex(), 13);
170 test_cycle<SSgraph_t>(UpdateVertexIndex(), 20);
171
172 return 0;
173 }
174