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 >
read_dimacs(Graph & g,const std::string & filename)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(buffer, 256);
70 std::string s(buffer);
71
72 if (s.size() == 0)
73 continue;
74
75 std::vector< std::string > v;
76 split(v, buffer, is_any_of(" \t\n"));
77
78 if (v[0] == "p")
79 {
80 // v[1] == "edge"
81 g = Graph(boost::lexical_cast< std::size_t >(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 v[1].c_str())],
89 vertices_by_index[boost::lexical_cast< std::size_t >(
90 v[2].c_str())],
91 g);
92 }
93 }
94 }
95
test_graph(const std::string & dimacs_filename)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, dimacs_filename);
117
118 // Initialize the interior edge index
119 property_map< graph, edge_index_t >::type e_index = get(edge_index, g);
120 e_size_t edge_count = 0;
121 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
122 put(e_index, *ei, 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(edge_index, g), num_edges(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, get(vertex_index, g), 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));
156 edge_permutation_t perm(
157 edge_permutation_storage.begin(), get(vertex_index, g));
158
159 // Test for planarity, computing the planar embedding or the kuratowski
160 // subgraph.
161 if (!boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
162 boyer_myrvold_params::embedding = perm,
163 boyer_myrvold_params::kuratowski_subgraph
164 = std::back_inserter(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, perm, get(edge_index, g), 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, perm, get(vertex_index, g), get(edge_index, g), 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, perm, std::back_inserter(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));
200 drawing_map_t drawing(drawing_vector.begin(), get(vertex_index, g));
201
202 // Compute a straight line drawing
203 chrobak_payne_straight_line_drawing(
204 g, perm, ordering.begin(), ordering.end(), drawing);
205
206 std::cout << "Planar. ";
207 BOOST_TEST(is_straight_line_drawing(g, drawing));
208
209 return 0;
210 }
211
main(int argc,char * argv[])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(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