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 | |
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 | |
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 | { |
48 | 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 | { |
61 | template < typename Graph > void update(Graph&) {} |
62 | }; |
63 | |
64 | template < typename Graph, typename VertexIndexUpdater > |
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 | |
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 >(vertex_index_updater: NoVertexIndexUpdater(), size: 10); |
121 | test_cycle< VVgraph_t >(vertex_index_updater: NoVertexIndexUpdater(), size: 50); |
122 | |
123 | test_cycle< VLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 3); |
124 | test_cycle< VLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 30); |
125 | |
126 | test_cycle< LVgraph_t >(vertex_index_updater: NoVertexIndexUpdater(), size: 15); |
127 | test_cycle< LVgraph_t >(vertex_index_updater: NoVertexIndexUpdater(), size: 45); |
128 | |
129 | test_cycle< LLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 8); |
130 | test_cycle< LLgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 19); |
131 | |
132 | test_cycle< SSgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 13); |
133 | test_cycle< SSgraph_t >(vertex_index_updater: UpdateVertexIndex(), size: 20); |
134 | |
135 | return boost::report_errors(); |
136 | } |
137 | |