1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
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 //=======================================================================
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.
17 This test needs to be linked against Boost.Filesystem.
21 #define BOOST_FILESYSTEM_VERSION 3
30 #include <boost/property_map/property_map.hpp>
31 #include <boost/lexical_cast.hpp>
32 #include <boost/tuple/tuple.hpp>
33 #include <boost/filesystem.hpp>
34 #include <boost/algorithm/string.hpp>
35 #include <boost/test/minimal.hpp>
38 #include <boost/graph/adjacency_list.hpp>
39 #include <boost/graph/depth_first_search.hpp>
40 #include <boost/graph/properties.hpp>
41 #include <boost/graph/graph_traits.hpp>
42 #include <boost/graph/planar_canonical_ordering.hpp>
43 #include <boost/graph/make_connected.hpp>
44 #include <boost/graph/make_biconnected_planar.hpp>
45 #include <boost/graph/make_maximal_planar.hpp>
46 #include <boost/graph/is_straight_line_drawing.hpp>
47 #include <boost/graph/is_kuratowski_subgraph.hpp>
48 #include <boost/graph/chrobak_payne_drawing.hpp>
49 #include <boost/graph/boyer_myrvold_planar_test.hpp>
50 #include <boost/graph/planar_detail/add_edge_visitors.hpp>
57 using namespace boost
;
67 template <typename Graph
>
68 void read_dimacs(Graph
& g
, const std::string
& filename
)
70 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_t
;
71 std::vector
<vertex_t
> vertices_by_index
;
73 std::ifstream
in(filename
.c_str());
78 in
.getline(buffer
, 256);
79 std::string
s(buffer
);
84 std::vector
<std::string
> v
;
85 split(v
, buffer
, is_any_of(" \t\n"));
90 g
= Graph(boost::lexical_cast
<std::size_t>(v
[2].c_str()));
91 std::copy(vertices(g
).first
,
93 std::back_inserter(vertices_by_index
)
98 add_edge(vertices_by_index
99 [boost::lexical_cast
<std::size_t>(v
[1].c_str())],
101 [boost::lexical_cast
<std::size_t>(v
[2].c_str())],
112 int test_graph(const std::string
& dimacs_filename
)
115 typedef adjacency_list
<listS
,
118 property
<vertex_index_t
, int>,
119 property
<edge_index_t
, int> > graph
;
121 typedef graph_traits
<graph
>::edge_descriptor edge_t
;
122 typedef graph_traits
<graph
>::edge_iterator edge_iterator_t
;
123 typedef graph_traits
<graph
>::vertex_iterator vertex_iterator_t
;
124 typedef graph_traits
<graph
>::edges_size_type e_size_t
;
125 typedef graph_traits
<graph
>::vertex_descriptor vertex_t
;
126 typedef edge_index_update_visitor
<property_map
<graph
, edge_index_t
>::type
>
129 vertex_iterator_t vi
, vi_end
;
130 edge_iterator_t ei
, ei_end
;
133 read_dimacs(g
, dimacs_filename
);
135 // Initialize the interior edge index
136 property_map
<graph
, edge_index_t
>::type e_index
= get(edge_index
, g
);
137 e_size_t edge_count
= 0;
138 for(boost::tie(ei
, ei_end
) = edges(g
); ei
!= ei_end
; ++ei
)
139 put(e_index
, *ei
, edge_count
++);
141 // Initialize the interior vertex index - not needed if the vertices
142 // are stored with a vecS
144 property_map<graph, vertex_index_t>::type v_index = get(vertex_index, g);
145 v_size_t vertex_count = 0;
146 for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
147 put(v_index, *vi, vertex_count++);
150 // This edge_updater will automatically update the interior edge
151 // index of the graph as edges are created.
152 edge_visitor_t
edge_updater(get(edge_index
, g
), num_edges(g
));
154 // The input graph may not be maximal planar, but the Chrobak-Payne straight
155 // line drawing needs a maximal planar graph as input. So, we make a copy of
156 // the original graph here, then add edges to the graph to make it maximal
157 // planar. When we're done creating a drawing of the maximal planar graph,
158 // we can use the same mapping of vertices to points on the grid to embed the
159 // original, non-maximal graph.
162 // Add edges to make g connected, if it isn't already
163 make_connected(g
, get(vertex_index
, g
), edge_updater
);
165 std::vector
<graph_traits
<graph
>::edge_descriptor
> kuratowski_edges
;
167 typedef std::vector
< std::vector
<edge_t
> > edge_permutation_storage_t
;
168 typedef boost::iterator_property_map
169 < edge_permutation_storage_t::iterator
,
170 property_map
<graph
, vertex_index_t
>::type
174 edge_permutation_storage_t
edge_permutation_storage(num_vertices(g
));
175 edge_permutation_t
perm(edge_permutation_storage
.begin(),
179 // Test for planarity, computing the planar embedding or the kuratowski
181 if (!boyer_myrvold_planarity_test(boyer_myrvold_params::graph
= g
,
182 boyer_myrvold_params::embedding
= perm
,
183 boyer_myrvold_params::kuratowski_subgraph
184 = std::back_inserter(kuratowski_edges
)
188 std::cout
<< "Not planar. ";
189 BOOST_REQUIRE(is_kuratowski_subgraph(g
,
190 kuratowski_edges
.begin(),
191 kuratowski_edges
.end()
198 // If we get this far, we have a connected planar graph.
199 make_biconnected_planar(g
, perm
, get(edge_index
, g
), edge_updater
);
201 // Compute the planar embedding of the (now) biconnected planar graph
202 BOOST_CHECK (boyer_myrvold_planarity_test(boyer_myrvold_params::graph
= g
,
203 boyer_myrvold_params::embedding
=
208 // If we get this far, we have a biconnected planar graph
209 make_maximal_planar(g
, perm
, get(vertex_index
,g
), get(edge_index
,g
),
213 // Now the graph is triangulated - we can compute the final planar embedding
214 BOOST_CHECK (boyer_myrvold_planarity_test(boyer_myrvold_params::graph
= g
,
215 boyer_myrvold_params::embedding
=
220 // Compute a planar canonical ordering of the vertices
221 std::vector
<vertex_t
> ordering
;
222 planar_canonical_ordering(g
, perm
, std::back_inserter(ordering
));
224 BOOST_CHECK(ordering
.size() == num_vertices(g
));
226 typedef std::vector
< coord_t
> drawing_storage_t
;
227 typedef boost::iterator_property_map
228 < drawing_storage_t::iterator
, property_map
<graph
, vertex_index_t
>::type
>
231 drawing_storage_t
drawing_vector(num_vertices(g
));
232 drawing_map_t
drawing(drawing_vector
.begin(), get(vertex_index
,g
));
234 // Compute a straight line drawing
235 chrobak_payne_straight_line_drawing(g
,
242 std::cout
<< "Planar. ";
243 BOOST_REQUIRE (is_straight_line_drawing(g
, drawing
));
254 int test_main(int argc
, char* argv
[])
257 std::string input_directory_str
= "planar_input_graphs";
260 input_directory_str
= std::string(argv
[1]);
263 std::cout
<< "Reading planar input files from " << input_directory_str
266 filesystem::path input_directory
=
267 filesystem::system_complete(filesystem::path(input_directory_str
));
268 const std::string dimacs_extension
= ".dimacs";
270 filesystem::directory_iterator dir_end
;
271 for( filesystem::directory_iterator
dir_itr(input_directory
);
272 dir_itr
!= dir_end
; ++dir_itr
)
275 if (dir_itr
->path().extension() != dimacs_extension
)
278 std::cout
<< "Testing " << dir_itr
->path().leaf() << "... ";
279 BOOST_REQUIRE (test_graph(dir_itr
->path().string()) == 0);
281 std::cout
<< std::endl
;