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