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