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 is almost identical to all_planar_input_files_test.cpp |
12 | except that parallel edges and loops are added to the graphs as |
13 | they are read in. |
14 | |
15 | This test needs to be linked against Boost.Filesystem. |
16 | |
17 | */ |
18 | |
19 | #define BOOST_FILESYSTEM_VERSION 3 |
20 | |
21 | #include <iostream> |
22 | #include <fstream> |
23 | #include <vector> |
24 | #include <string> |
25 | #include <utility> |
26 | |
27 | |
28 | #include <boost/property_map/property_map.hpp> |
29 | #include <boost/lexical_cast.hpp> |
30 | #include <boost/tuple/tuple.hpp> |
31 | #include <boost/filesystem.hpp> |
32 | #include <boost/algorithm/string.hpp> |
33 | #include <boost/test/minimal.hpp> |
34 | |
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 | |
51 | |
52 | |
53 | |
54 | |
55 | using namespace boost; |
56 | |
57 | struct coord_t |
58 | { |
59 | std::size_t x; |
60 | std::size_t y; |
61 | }; |
62 | |
63 | |
64 | |
65 | template <typename Graph> |
66 | void read_dimacs(Graph& g, const std::string& filename) |
67 | { |
68 | |
69 | // every <vertex_stride>th vertex has a self-loop |
70 | int vertex_stride = 5; |
71 | |
72 | // on vertices with self loops, there are between 1 and |
73 | // <max_loop_multiplicity> loops |
74 | int max_loop_multiplicity = 6; |
75 | |
76 | // every <edge_stride>th edge is a parallel edge |
77 | int edge_stride = 7; |
78 | |
79 | // parallel edges come in groups of 2 to <max_edge_multiplicity> + 1 |
80 | int max_edge_multiplicity = 5; |
81 | |
82 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; |
83 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
84 | std::vector<vertex_t> vertices_by_index; |
85 | |
86 | std::ifstream in(filename.c_str()); |
87 | |
88 | long num_edges_added = 0; |
89 | long num_parallel_edges = 0; |
90 | |
91 | while (!in.eof()) |
92 | { |
93 | |
94 | char buffer[256]; |
95 | in.getline(s: buffer, n: 256); |
96 | std::string s(buffer); |
97 | |
98 | if (s.size() == 0) |
99 | continue; |
100 | |
101 | std::vector<std::string> v; |
102 | split(Result&: v, Input&: buffer, Pred: is_any_of(Set: " \t\n" )); |
103 | |
104 | if (v[0] == "p" ) |
105 | { |
106 | //v[1] == "edge" |
107 | long num_vertices = boost::lexical_cast<long>(arg: v[2].c_str()); |
108 | g = Graph(num_vertices); |
109 | |
110 | |
111 | vertex_iterator_t vi, vi_end; |
112 | long count = 0; |
113 | long mult_count = 0; |
114 | for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
115 | { |
116 | if (count % vertex_stride == 0) |
117 | { |
118 | for(int i = 0; |
119 | i < (mult_count % max_loop_multiplicity) + 1; |
120 | ++i |
121 | ) |
122 | { |
123 | add_edge(*vi, *vi, g); |
124 | } |
125 | ++mult_count; |
126 | } |
127 | ++count; |
128 | } |
129 | |
130 | std::copy(vertices(g).first, |
131 | vertices(g).second, |
132 | std::back_inserter(vertices_by_index) |
133 | ); |
134 | } |
135 | else if (v[0] == "e" ) |
136 | { |
137 | add_edge(vertices_by_index[boost::lexical_cast<long>(arg: v[1].c_str())], |
138 | vertices_by_index[boost::lexical_cast<long>(arg: v[2].c_str())], |
139 | g); |
140 | |
141 | if (num_edges_added % edge_stride == 0) |
142 | { |
143 | for(int i = 0; |
144 | i < (num_parallel_edges % max_edge_multiplicity) + 1; |
145 | ++i |
146 | ) |
147 | { |
148 | add_edge(vertices_by_index |
149 | [boost::lexical_cast<long>(arg: v[1].c_str())], |
150 | vertices_by_index |
151 | [boost::lexical_cast<long>(arg: v[2].c_str())], |
152 | g); |
153 | } |
154 | ++num_parallel_edges; |
155 | } |
156 | ++num_edges_added; |
157 | |
158 | } |
159 | } |
160 | } |
161 | |
162 | |
163 | |
164 | |
165 | struct face_counter : planar_face_traversal_visitor |
166 | { |
167 | |
168 | face_counter() : m_num_faces(0) {} |
169 | |
170 | void begin_face() { ++m_num_faces; } |
171 | |
172 | long num_faces() { return m_num_faces; } |
173 | |
174 | private: |
175 | |
176 | long m_num_faces; |
177 | |
178 | }; |
179 | |
180 | |
181 | |
182 | |
183 | |
184 | |
185 | int test_graph(const std::string& dimacs_filename) |
186 | { |
187 | |
188 | typedef adjacency_list<listS, |
189 | vecS, |
190 | undirectedS, |
191 | property<vertex_index_t, int>, |
192 | property<edge_index_t, int> > graph; |
193 | |
194 | typedef graph_traits<graph>::edge_descriptor edge_t; |
195 | typedef graph_traits<graph>::edge_iterator edge_iterator_t; |
196 | typedef graph_traits<graph>::vertex_iterator vertex_iterator_t; |
197 | typedef graph_traits<graph>::edges_size_type e_size_t; |
198 | typedef graph_traits<graph>::vertex_descriptor vertex_t; |
199 | typedef edge_index_update_visitor<property_map<graph, edge_index_t>::type> |
200 | edge_visitor_t; |
201 | |
202 | vertex_iterator_t vi, vi_end; |
203 | edge_iterator_t ei, ei_end; |
204 | |
205 | graph g; |
206 | read_dimacs(g, filename: dimacs_filename); |
207 | |
208 | // Initialize the interior edge index |
209 | property_map<graph, edge_index_t>::type e_index = get(p: edge_index, g); |
210 | e_size_t edge_count = 0; |
211 | for(boost::tie(t0&: ei, t1&: ei_end) = edges(g_: g); ei != ei_end; ++ei) |
212 | put(pa: e_index, k: *ei, v: edge_count++); |
213 | |
214 | // Initialize the interior vertex index - not needed if the vertices |
215 | // are stored with a vecS |
216 | /* |
217 | property_map<graph, vertex_index_t>::type v_index = get(vertex_index, g); |
218 | v_size_t vertex_count = 0; |
219 | for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
220 | put(v_index, *vi, vertex_count++); |
221 | */ |
222 | |
223 | // This edge_updater will automatically update the interior edge |
224 | // index of the graph as edges are created. |
225 | edge_visitor_t edge_updater(get(p: edge_index, g), num_edges(g_: g)); |
226 | |
227 | // The input graph may not be maximal planar, but the Chrobak-Payne straight |
228 | // line drawing needs a maximal planar graph as input. So, we make a copy of |
229 | // the original graph here, then add edges to the graph to make it maximal |
230 | // planar. When we're done creating a drawing of the maximal planar graph, |
231 | // we can use the same mapping of vertices to points on the grid to embed the |
232 | // original, non-maximal graph. |
233 | graph g_copy(g); |
234 | |
235 | // Add edges to make g connected, if it isn't already |
236 | make_connected(g, vm: get(p: vertex_index, g), vis&: edge_updater); |
237 | |
238 | std::vector<graph_traits<graph>::edge_descriptor> kuratowski_edges; |
239 | |
240 | typedef std::vector< std::vector<edge_t> > edge_permutation_storage_t; |
241 | typedef boost::iterator_property_map |
242 | < edge_permutation_storage_t::iterator, |
243 | property_map<graph, vertex_index_t>::type |
244 | > |
245 | edge_permutation_t; |
246 | |
247 | edge_permutation_storage_t edge_permutation_storage(num_vertices(g_: g)); |
248 | edge_permutation_t perm(edge_permutation_storage.begin(), |
249 | get(p: vertex_index,g) |
250 | ); |
251 | |
252 | // Test for planarity, computing the planar embedding or the kuratowski |
253 | // subgraph. |
254 | if (!boyer_myrvold_planarity_test(arg0: boyer_myrvold_params::graph = g, |
255 | arg1: boyer_myrvold_params::embedding = perm, |
256 | arg2: boyer_myrvold_params::kuratowski_subgraph |
257 | = std::back_inserter(x&: kuratowski_edges) |
258 | ) |
259 | ) |
260 | { |
261 | std::cerr << "Not planar. " ; |
262 | BOOST_REQUIRE(is_kuratowski_subgraph |
263 | (g, kuratowski_edges.begin(), kuratowski_edges.end()) |
264 | ); |
265 | |
266 | return 0; |
267 | } |
268 | |
269 | // If we get this far, we have a connected planar graph. |
270 | make_biconnected_planar(g, embedding: perm, em: get(p: edge_index, g), vis&: edge_updater); |
271 | |
272 | // Compute the planar embedding of the (now) biconnected planar graph |
273 | BOOST_CHECK (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, |
274 | boyer_myrvold_params::embedding |
275 | = perm |
276 | ) |
277 | ); |
278 | |
279 | // If we get this far, we have a biconnected planar graph |
280 | make_maximal_planar(g, embedding: perm, vm: get(p: vertex_index,g), em: get(p: edge_index,g), |
281 | vis&: edge_updater); |
282 | |
283 | // Now the graph is triangulated - we can compute the final planar embedding |
284 | BOOST_CHECK (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, |
285 | boyer_myrvold_params::embedding |
286 | = perm |
287 | ) |
288 | ); |
289 | |
290 | // Make sure Euler's formula holds |
291 | face_counter vis; |
292 | planar_face_traversal(g, embedding: perm, visitor&: vis, em: get(p: edge_index, g)); |
293 | |
294 | BOOST_CHECK(num_vertices(g) - num_edges(g) + vis.num_faces() == 2); |
295 | |
296 | // Compute a planar canonical ordering of the vertices |
297 | std::vector<vertex_t> ordering; |
298 | planar_canonical_ordering(g, embedding: perm, ordering: std::back_inserter(x&: ordering)); |
299 | |
300 | BOOST_CHECK(ordering.size() == num_vertices(g)); |
301 | |
302 | typedef std::vector< coord_t > drawing_storage_t; |
303 | typedef boost::iterator_property_map |
304 | < drawing_storage_t::iterator, property_map<graph, vertex_index_t>::type > |
305 | drawing_map_t; |
306 | |
307 | drawing_storage_t drawing_vector(num_vertices(g_: g)); |
308 | drawing_map_t drawing(drawing_vector.begin(), get(p: vertex_index,g)); |
309 | |
310 | // Compute a straight line drawing |
311 | chrobak_payne_straight_line_drawing(g, |
312 | embedding: perm, |
313 | ord_begin: ordering.begin(), |
314 | ord_end: ordering.end(), |
315 | drawing |
316 | ); |
317 | |
318 | std::cerr << "Planar. " ; |
319 | BOOST_REQUIRE (is_straight_line_drawing(g, drawing)); |
320 | |
321 | return 0; |
322 | } |
323 | |
324 | |
325 | |
326 | |
327 | |
328 | |
329 | |
330 | int test_main(int argc, char* argv[]) |
331 | { |
332 | |
333 | std::string input_directory_str = "planar_input_graphs" ; |
334 | if (argc > 1) |
335 | { |
336 | input_directory_str = std::string(argv[1]); |
337 | } |
338 | |
339 | std::cout << "Reading planar input files from " << input_directory_str |
340 | << std::endl; |
341 | |
342 | filesystem::path input_directory = |
343 | filesystem::system_complete(p: filesystem::path(input_directory_str)); |
344 | const std::string dimacs_extension = ".dimacs" ; |
345 | |
346 | filesystem::directory_iterator dir_end; |
347 | for( filesystem::directory_iterator dir_itr(input_directory); |
348 | dir_itr != dir_end; ++dir_itr) |
349 | { |
350 | |
351 | if (dir_itr->path().extension() != dimacs_extension) |
352 | continue; |
353 | |
354 | std::cerr << "Testing " << dir_itr->path().leaf() << "... " ; |
355 | BOOST_REQUIRE (test_graph(dir_itr->path().string()) == 0); |
356 | |
357 | std::cerr << std::endl; |
358 | } |
359 | |
360 | return 0; |
361 | |
362 | } |
363 | |