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 #include <boost/property_map/property_map.hpp>
28 #include <boost/lexical_cast.hpp>
29 #include <boost/tuple/tuple.hpp>
30 #include <boost/filesystem.hpp>
31 #include <boost/algorithm/string.hpp>
32 #include <boost/core/lightweight_test.hpp>
33
34 #include <boost/graph/adjacency_list.hpp>
35 #include <boost/graph/depth_first_search.hpp>
36 #include <boost/graph/properties.hpp>
37 #include <boost/graph/graph_traits.hpp>
38 #include <boost/graph/planar_canonical_ordering.hpp>
39 #include <boost/graph/make_connected.hpp>
40 #include <boost/graph/make_biconnected_planar.hpp>
41 #include <boost/graph/make_maximal_planar.hpp>
42 #include <boost/graph/is_straight_line_drawing.hpp>
43 #include <boost/graph/is_kuratowski_subgraph.hpp>
44 #include <boost/graph/chrobak_payne_drawing.hpp>
45 #include <boost/graph/boyer_myrvold_planar_test.hpp>
46 #include <boost/graph/planar_detail/add_edge_visitors.hpp>
47
48 using namespace boost;
49
50 struct coord_t
51 {
52 std::size_t x;
53 std::size_t y;
54 };
55
56 template < typename Graph >
read_dimacs(Graph & g,const std::string & filename)57 void read_dimacs(Graph& g, const std::string& filename)
58 {
59
60 // every <vertex_stride>th vertex has a self-loop
61 int vertex_stride = 5;
62
63 // on vertices with self loops, there are between 1 and
64 // <max_loop_multiplicity> loops
65 int max_loop_multiplicity = 6;
66
67 // every <edge_stride>th edge is a parallel edge
68 int edge_stride = 7;
69
70 // parallel edges come in groups of 2 to <max_edge_multiplicity> + 1
71 int max_edge_multiplicity = 5;
72
73 typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
74 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
75 std::vector< vertex_t > vertices_by_index;
76
77 std::ifstream in(filename.c_str());
78
79 long num_edges_added = 0;
80 long num_parallel_edges = 0;
81
82 while (!in.eof())
83 {
84
85 char buffer[256];
86 in.getline(buffer, 256);
87 std::string s(buffer);
88
89 if (s.size() == 0)
90 continue;
91
92 std::vector< std::string > v;
93 split(v, buffer, is_any_of(" \t\n"));
94
95 if (v[0] == "p")
96 {
97 // v[1] == "edge"
98 long num_vertices = boost::lexical_cast< long >(v[2].c_str());
99 g = Graph(num_vertices);
100
101 vertex_iterator_t vi, vi_end;
102 long count = 0;
103 long mult_count = 0;
104 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
105 {
106 if (count % vertex_stride == 0)
107 {
108 for (int i = 0;
109 i < (mult_count % max_loop_multiplicity) + 1; ++i)
110 {
111 add_edge(*vi, *vi, g);
112 }
113 ++mult_count;
114 }
115 ++count;
116 }
117
118 std::copy(vertices(g).first, vertices(g).second,
119 std::back_inserter(vertices_by_index));
120 }
121 else if (v[0] == "e")
122 {
123 add_edge(
124 vertices_by_index[boost::lexical_cast< long >(v[1].c_str())],
125 vertices_by_index[boost::lexical_cast< long >(v[2].c_str())],
126 g);
127
128 if (num_edges_added % edge_stride == 0)
129 {
130 for (int i = 0;
131 i < (num_parallel_edges % max_edge_multiplicity) + 1; ++i)
132 {
133 add_edge(vertices_by_index[boost::lexical_cast< long >(
134 v[1].c_str())],
135 vertices_by_index[boost::lexical_cast< long >(
136 v[2].c_str())],
137 g);
138 }
139 ++num_parallel_edges;
140 }
141 ++num_edges_added;
142 }
143 }
144 }
145
146 struct face_counter : planar_face_traversal_visitor
147 {
148
face_counterface_counter149 face_counter() : m_num_faces(0) {}
150
begin_faceface_counter151 void begin_face() { ++m_num_faces; }
152
num_facesface_counter153 long num_faces() { return m_num_faces; }
154
155 private:
156 long m_num_faces;
157 };
158
test_graph(const std::string & dimacs_filename)159 int test_graph(const std::string& dimacs_filename)
160 {
161
162 typedef adjacency_list< listS, vecS, undirectedS,
163 property< vertex_index_t, int >, property< edge_index_t, int > >
164 graph;
165
166 typedef graph_traits< graph >::edge_descriptor edge_t;
167 typedef graph_traits< graph >::edge_iterator edge_iterator_t;
168 typedef graph_traits< graph >::vertex_iterator vertex_iterator_t;
169 typedef graph_traits< graph >::edges_size_type e_size_t;
170 typedef graph_traits< graph >::vertex_descriptor vertex_t;
171 typedef edge_index_update_visitor<
172 property_map< graph, edge_index_t >::type >
173 edge_visitor_t;
174
175 vertex_iterator_t vi, vi_end;
176 edge_iterator_t ei, ei_end;
177
178 graph g;
179 read_dimacs(g, dimacs_filename);
180
181 // Initialize the interior edge index
182 property_map< graph, edge_index_t >::type e_index = get(edge_index, g);
183 e_size_t edge_count = 0;
184 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
185 put(e_index, *ei, edge_count++);
186
187 // Initialize the interior vertex index - not needed if the vertices
188 // are stored with a vecS
189 /*
190 property_map<graph, vertex_index_t>::type v_index = get(vertex_index, g);
191 v_size_t vertex_count = 0;
192 for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
193 put(v_index, *vi, vertex_count++);
194 */
195
196 // This edge_updater will automatically update the interior edge
197 // index of the graph as edges are created.
198 edge_visitor_t edge_updater(get(edge_index, g), num_edges(g));
199
200 // The input graph may not be maximal planar, but the Chrobak-Payne straight
201 // line drawing needs a maximal planar graph as input. So, we make a copy of
202 // the original graph here, then add edges to the graph to make it maximal
203 // planar. When we're done creating a drawing of the maximal planar graph,
204 // we can use the same mapping of vertices to points on the grid to embed
205 // the original, non-maximal graph.
206 graph g_copy(g);
207
208 // Add edges to make g connected, if it isn't already
209 make_connected(g, get(vertex_index, g), edge_updater);
210
211 std::vector< graph_traits< graph >::edge_descriptor > kuratowski_edges;
212
213 typedef std::vector< std::vector< edge_t > > edge_permutation_storage_t;
214 typedef boost::iterator_property_map< edge_permutation_storage_t::iterator,
215 property_map< graph, vertex_index_t >::type >
216 edge_permutation_t;
217
218 edge_permutation_storage_t edge_permutation_storage(num_vertices(g));
219 edge_permutation_t perm(
220 edge_permutation_storage.begin(), get(vertex_index, g));
221
222 // Test for planarity, computing the planar embedding or the kuratowski
223 // subgraph.
224 if (!boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
225 boyer_myrvold_params::embedding = perm,
226 boyer_myrvold_params::kuratowski_subgraph
227 = std::back_inserter(kuratowski_edges)))
228 {
229 std::cerr << "Not planar. ";
230 BOOST_TEST(is_kuratowski_subgraph(
231 g, kuratowski_edges.begin(), kuratowski_edges.end()));
232
233 return 0;
234 }
235
236 // If we get this far, we have a connected planar graph.
237 make_biconnected_planar(g, perm, get(edge_index, g), edge_updater);
238
239 // Compute the planar embedding of the (now) biconnected planar graph
240 BOOST_TEST(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
241 boyer_myrvold_params::embedding = perm));
242
243 // If we get this far, we have a biconnected planar graph
244 make_maximal_planar(
245 g, perm, get(vertex_index, g), get(edge_index, g), edge_updater);
246
247 // Now the graph is triangulated - we can compute the final planar embedding
248 BOOST_TEST(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
249 boyer_myrvold_params::embedding = perm));
250
251 // Make sure Euler's formula holds
252 face_counter vis;
253 planar_face_traversal(g, perm, vis, get(edge_index, g));
254
255 BOOST_TEST(num_vertices(g) - num_edges(g) + vis.num_faces() == 2);
256
257 // Compute a planar canonical ordering of the vertices
258 std::vector< vertex_t > ordering;
259 planar_canonical_ordering(g, perm, std::back_inserter(ordering));
260
261 BOOST_TEST(ordering.size() == num_vertices(g));
262
263 typedef std::vector< coord_t > drawing_storage_t;
264 typedef boost::iterator_property_map< drawing_storage_t::iterator,
265 property_map< graph, vertex_index_t >::type >
266 drawing_map_t;
267
268 drawing_storage_t drawing_vector(num_vertices(g));
269 drawing_map_t drawing(drawing_vector.begin(), get(vertex_index, g));
270
271 // Compute a straight line drawing
272 chrobak_payne_straight_line_drawing(
273 g, perm, ordering.begin(), ordering.end(), drawing);
274
275 std::cerr << "Planar. ";
276 BOOST_TEST(is_straight_line_drawing(g, drawing));
277
278 return 0;
279 }
280
main(int argc,char * argv[])281 int main(int argc, char* argv[])
282 {
283
284 std::string input_directory_str = "planar_input_graphs";
285 if (argc > 1)
286 {
287 input_directory_str = std::string(argv[1]);
288 }
289
290 std::cout << "Reading planar input files from " << input_directory_str
291 << std::endl;
292
293 filesystem::path input_directory
294 = filesystem::system_complete(filesystem::path(input_directory_str));
295 const std::string dimacs_extension = ".dimacs";
296
297 filesystem::directory_iterator dir_end;
298 for (filesystem::directory_iterator dir_itr(input_directory);
299 dir_itr != dir_end; ++dir_itr)
300 {
301
302 if (dir_itr->path().extension() != dimacs_extension)
303 continue;
304
305 std::cerr << "Testing " << dir_itr->path().leaf() << "... ";
306 BOOST_TEST(test_graph(dir_itr->path().string()) == 0);
307
308 std::cerr << std::endl;
309 }
310
311 return boost::report_errors();
312 }
313