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 | /* |
10 | |
11 | This test looks in the directory "planar_input_graphs" for any files |
12 | of the form *.dimacs. Each such file is used to create an input graph |
13 | and test the input graph for planarity. If the graph is planar, a |
14 | straight line drawing is generated and verified. If the graph isn't |
15 | planar, a kuratowski subgraph is isolated and verified. |
16 | |
17 | This test needs to be linked against Boost.Filesystem. |
18 | |
19 | */ |
20 | |
21 | #define BOOST_FILESYSTEM_VERSION 3 |
22 | |
23 | #include <iostream> |
24 | #include <fstream> |
25 | #include <vector> |
26 | #include <string> |
27 | #include <utility> |
28 | |
29 | #include <boost/property_map/property_map.hpp> |
30 | #include <boost/lexical_cast.hpp> |
31 | #include <boost/tuple/tuple.hpp> |
32 | #include <boost/filesystem.hpp> |
33 | #include <boost/algorithm/string.hpp> |
34 | #include <boost/core/lightweight_test.hpp> |
35 | |
36 | #include <boost/graph/adjacency_list.hpp> |
37 | #include <boost/graph/depth_first_search.hpp> |
38 | #include <boost/graph/properties.hpp> |
39 | #include <boost/graph/graph_traits.hpp> |
40 | #include <boost/graph/planar_canonical_ordering.hpp> |
41 | #include <boost/graph/make_connected.hpp> |
42 | #include <boost/graph/make_biconnected_planar.hpp> |
43 | #include <boost/graph/make_maximal_planar.hpp> |
44 | #include <boost/graph/is_straight_line_drawing.hpp> |
45 | #include <boost/graph/is_kuratowski_subgraph.hpp> |
46 | #include <boost/graph/chrobak_payne_drawing.hpp> |
47 | #include <boost/graph/boyer_myrvold_planar_test.hpp> |
48 | #include <boost/graph/planar_detail/add_edge_visitors.hpp> |
49 | |
50 | using namespace boost; |
51 | |
52 | struct coord_t |
53 | { |
54 | std::size_t x; |
55 | std::size_t y; |
56 | }; |
57 | |
58 | template < typename Graph > |
59 | void read_dimacs(Graph& g, const std::string& filename) |
60 | { |
61 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; |
62 | std::vector< vertex_t > vertices_by_index; |
63 | |
64 | std::ifstream in(filename.c_str()); |
65 | |
66 | while (!in.eof()) |
67 | { |
68 | char buffer[256]; |
69 | in.getline(s: buffer, n: 256); |
70 | std::string s(buffer); |
71 | |
72 | if (s.size() == 0) |
73 | continue; |
74 | |
75 | std::vector< std::string > v; |
76 | split(Result&: v, Input&: buffer, Pred: is_any_of(Set: " \t\n" )); |
77 | |
78 | if (v[0] == "p" ) |
79 | { |
80 | // v[1] == "edge" |
81 | g = Graph(boost::lexical_cast< std::size_t >(arg: v[2].c_str())); |
82 | std::copy(vertices(g).first, vertices(g).second, |
83 | std::back_inserter(vertices_by_index)); |
84 | } |
85 | else if (v[0] == "e" ) |
86 | { |
87 | add_edge(vertices_by_index[boost::lexical_cast< std::size_t >( |
88 | arg: v[1].c_str())], |
89 | vertices_by_index[boost::lexical_cast< std::size_t >( |
90 | arg: v[2].c_str())], |
91 | g); |
92 | } |
93 | } |
94 | } |
95 | |
96 | int test_graph(const std::string& dimacs_filename) |
97 | { |
98 | |
99 | typedef adjacency_list< listS, vecS, undirectedS, |
100 | property< vertex_index_t, int >, property< edge_index_t, int > > |
101 | graph; |
102 | |
103 | typedef graph_traits< graph >::edge_descriptor edge_t; |
104 | typedef graph_traits< graph >::edge_iterator edge_iterator_t; |
105 | typedef graph_traits< graph >::vertex_iterator vertex_iterator_t; |
106 | typedef graph_traits< graph >::edges_size_type e_size_t; |
107 | typedef graph_traits< graph >::vertex_descriptor vertex_t; |
108 | typedef edge_index_update_visitor< |
109 | property_map< graph, edge_index_t >::type > |
110 | edge_visitor_t; |
111 | |
112 | vertex_iterator_t vi, vi_end; |
113 | edge_iterator_t ei, ei_end; |
114 | |
115 | graph g; |
116 | read_dimacs(g, filename: dimacs_filename); |
117 | |
118 | // Initialize the interior edge index |
119 | property_map< graph, edge_index_t >::type e_index = get(p: edge_index, g); |
120 | e_size_t edge_count = 0; |
121 | for (boost::tie(t0&: ei, t1&: ei_end) = edges(g_: g); ei != ei_end; ++ei) |
122 | put(pa: e_index, k: *ei, v: edge_count++); |
123 | |
124 | // Initialize the interior vertex index - not needed if the vertices |
125 | // are stored with a vecS |
126 | /* |
127 | property_map<graph, vertex_index_t>::type v_index = get(vertex_index, g); |
128 | v_size_t vertex_count = 0; |
129 | for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
130 | put(v_index, *vi, vertex_count++); |
131 | */ |
132 | |
133 | // This edge_updater will automatically update the interior edge |
134 | // index of the graph as edges are created. |
135 | edge_visitor_t edge_updater(get(p: edge_index, g), num_edges(g_: g)); |
136 | |
137 | // The input graph may not be maximal planar, but the Chrobak-Payne straight |
138 | // line drawing needs a maximal planar graph as input. So, we make a copy of |
139 | // the original graph here, then add edges to the graph to make it maximal |
140 | // planar. When we're done creating a drawing of the maximal planar graph, |
141 | // we can use the same mapping of vertices to points on the grid to embed |
142 | // the original, non-maximal graph. |
143 | graph g_copy(g); |
144 | |
145 | // Add edges to make g connected, if it isn't already |
146 | make_connected(g, vm: get(p: vertex_index, g), vis&: edge_updater); |
147 | |
148 | std::vector< graph_traits< graph >::edge_descriptor > kuratowski_edges; |
149 | |
150 | typedef std::vector< std::vector< edge_t > > edge_permutation_storage_t; |
151 | typedef boost::iterator_property_map< edge_permutation_storage_t::iterator, |
152 | property_map< graph, vertex_index_t >::type > |
153 | edge_permutation_t; |
154 | |
155 | edge_permutation_storage_t edge_permutation_storage(num_vertices(g_: g)); |
156 | edge_permutation_t perm( |
157 | edge_permutation_storage.begin(), get(p: vertex_index, g)); |
158 | |
159 | // Test for planarity, computing the planar embedding or the kuratowski |
160 | // subgraph. |
161 | if (!boyer_myrvold_planarity_test(arg0: boyer_myrvold_params::graph = g, |
162 | arg1: boyer_myrvold_params::embedding = perm, |
163 | arg2: boyer_myrvold_params::kuratowski_subgraph |
164 | = std::back_inserter(x&: kuratowski_edges))) |
165 | { |
166 | std::cout << "Not planar. " ; |
167 | BOOST_TEST(is_kuratowski_subgraph( |
168 | g, kuratowski_edges.begin(), kuratowski_edges.end())); |
169 | |
170 | return 0; |
171 | } |
172 | |
173 | // If we get this far, we have a connected planar graph. |
174 | make_biconnected_planar(g, embedding: perm, em: get(p: edge_index, g), vis&: edge_updater); |
175 | |
176 | // Compute the planar embedding of the (now) biconnected planar graph |
177 | BOOST_TEST(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, |
178 | boyer_myrvold_params::embedding = perm)); |
179 | |
180 | // If we get this far, we have a biconnected planar graph |
181 | make_maximal_planar( |
182 | g, embedding: perm, vm: get(p: vertex_index, g), em: get(p: edge_index, g), vis&: edge_updater); |
183 | |
184 | // Now the graph is triangulated - we can compute the final planar embedding |
185 | BOOST_TEST(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, |
186 | boyer_myrvold_params::embedding = perm)); |
187 | |
188 | // Compute a planar canonical ordering of the vertices |
189 | std::vector< vertex_t > ordering; |
190 | planar_canonical_ordering(g, embedding: perm, ordering: std::back_inserter(x&: ordering)); |
191 | |
192 | BOOST_TEST(ordering.size() == num_vertices(g)); |
193 | |
194 | typedef std::vector< coord_t > drawing_storage_t; |
195 | typedef boost::iterator_property_map< drawing_storage_t::iterator, |
196 | property_map< graph, vertex_index_t >::type > |
197 | drawing_map_t; |
198 | |
199 | drawing_storage_t drawing_vector(num_vertices(g_: g)); |
200 | drawing_map_t drawing(drawing_vector.begin(), get(p: vertex_index, g)); |
201 | |
202 | // Compute a straight line drawing |
203 | chrobak_payne_straight_line_drawing( |
204 | g, embedding: perm, ord_begin: ordering.begin(), ord_end: ordering.end(), drawing); |
205 | |
206 | std::cout << "Planar. " ; |
207 | BOOST_TEST(is_straight_line_drawing(g, drawing)); |
208 | |
209 | return 0; |
210 | } |
211 | |
212 | int main(int argc, char* argv[]) |
213 | { |
214 | |
215 | std::string input_directory_str = "planar_input_graphs" ; |
216 | if (argc > 1) |
217 | { |
218 | input_directory_str = std::string(argv[1]); |
219 | } |
220 | |
221 | std::cout << "Reading planar input files from " << input_directory_str |
222 | << std::endl; |
223 | |
224 | filesystem::path input_directory |
225 | = filesystem::system_complete(p: filesystem::path(input_directory_str)); |
226 | const std::string dimacs_extension = ".dimacs" ; |
227 | |
228 | filesystem::directory_iterator dir_end; |
229 | for (filesystem::directory_iterator dir_itr(input_directory); |
230 | dir_itr != dir_end; ++dir_itr) |
231 | { |
232 | |
233 | if (dir_itr->path().extension() != dimacs_extension) |
234 | continue; |
235 | |
236 | std::cout << "Testing " << dir_itr->path().leaf() << "... " ; |
237 | BOOST_TEST(test_graph(dir_itr->path().string()) == 0); |
238 | |
239 | std::cout << std::endl; |
240 | } |
241 | |
242 | return boost::report_errors(); |
243 | } |
244 | |