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
11This test looks in the directory "planar_input_graphs" for any files
12of the form *.dimacs. Each such file is used to create an input graph
13and test the input graph for planarity. If the graph is planar, a
14straight line drawing is generated and verified. If the graph isn't
15planar, a kuratowski subgraph is isolated and verified.
16
17This 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
50using namespace boost;
51
52struct coord_t
53{
54 std::size_t x;
55 std::size_t y;
56};
57
58template < typename Graph >
59void 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
96int 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
212int 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

source code of boost/libs/graph/test/all_planar_input_files_test.cpp