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 | |

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> |

36 | |

37 | |

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> |

51 | |

52 | |

53 | |

54 | |

55 | |

56 | |

57 | using namespace boost; |

58 | |

59 | struct coord_t |

60 | { |

61 | std::size_t x; |

62 | std::size_t y; |

63 | }; |

64 | |

65 | |

66 | |

67 | template <typename Graph> |

68 | void read_dimacs(Graph& g, const std::string& filename) |

69 | { |

70 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |

71 | std::vector<vertex_t> vertices_by_index; |

72 | |

73 | std::ifstream in(filename.c_str()); |

74 | |

75 | while (!in.eof()) |

76 | { |

77 | char buffer[256]; |

78 | in.getline(buffer, 256); |

79 | std::string s(buffer); |

80 | |

81 | if (s.size() == 0) |

82 | continue; |

83 | |

84 | std::vector<std::string> v; |

85 | split(v, buffer, is_any_of(" \t\n")); |

86 | |

87 | if (v[0] == "p") |

88 | { |

89 | //v[1] == "edge" |

90 | g = Graph(boost::lexical_cast<std::size_t>(v[2].c_str())); |

91 | std::copy(vertices(g).first, |

92 | vertices(g).second, |

93 | std::back_inserter(vertices_by_index) |

94 | ); |

95 | } |

96 | else if (v[0] == "e") |

97 | { |

98 | add_edge(vertices_by_index |

99 | [boost::lexical_cast<std::size_t>(v[1].c_str())], |

100 | vertices_by_index |

101 | [boost::lexical_cast<std::size_t>(v[2].c_str())], |

102 | g); |

103 | } |

104 | } |

105 | } |

106 | |

107 | |

108 | |

109 | |

110 | |

111 | |

112 | int test_graph(const std::string& dimacs_filename) |

113 | { |

114 | |

115 | typedef adjacency_list<listS, |

116 | vecS, |

117 | undirectedS, |

118 | property<vertex_index_t, int>, |

119 | property<edge_index_t, int> > graph; |

120 | |

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> |

127 | edge_visitor_t; |

128 | |

129 | vertex_iterator_t vi, vi_end; |

130 | edge_iterator_t ei, ei_end; |

131 | |

132 | graph g; |

133 | read_dimacs(g, dimacs_filename); |

134 | |

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++); |

140 | |

141 | // Initialize the interior vertex index - not needed if the vertices |

142 | // are stored with a vecS |

143 | /* |

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++); |

148 | */ |

149 | |

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)); |

153 | |

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. |

160 | graph g_copy(g); |

161 | |

162 | // Add edges to make g connected, if it isn't already |

163 | make_connected(g, get(vertex_index, g), edge_updater); |

164 | |

165 | std::vector<graph_traits<graph>::edge_descriptor> kuratowski_edges; |

166 | |

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 |

171 | > |

172 | edge_permutation_t; |

173 | |

174 | edge_permutation_storage_t edge_permutation_storage(num_vertices(g)); |

175 | edge_permutation_t perm(edge_permutation_storage.begin(), |

176 | get(vertex_index,g) |

177 | ); |

178 | |

179 | // Test for planarity, computing the planar embedding or the kuratowski |

180 | // subgraph. |

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) |

185 | ) |

186 | ) |

187 | { |

188 | std::cout << "Not planar. "; |

189 | BOOST_REQUIRE(is_kuratowski_subgraph(g, |

190 | kuratowski_edges.begin(), |

191 | kuratowski_edges.end() |

192 | ) |

193 | ); |

194 | |

195 | return 0; |

196 | } |

197 | |

198 | // If we get this far, we have a connected planar graph. |

199 | make_biconnected_planar(g, perm, get(edge_index, g), edge_updater); |

200 | |

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 = |

204 | perm |

205 | ) |

206 | ); |

207 | |

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), |

210 | edge_updater |

211 | ); |

212 | |

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 = |

216 | perm |

217 | ) |

218 | ); |

219 | |

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)); |

223 | |

224 | BOOST_CHECK(ordering.size() == num_vertices(g)); |

225 | |

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 > |

229 | drawing_map_t; |

230 | |

231 | drawing_storage_t drawing_vector(num_vertices(g)); |

232 | drawing_map_t drawing(drawing_vector.begin(), get(vertex_index,g)); |

233 | |

234 | // Compute a straight line drawing |

235 | chrobak_payne_straight_line_drawing(g, |

236 | perm, |

237 | ordering.begin(), |

238 | ordering.end(), |

239 | drawing |

240 | ); |

241 | |

242 | std::cout << "Planar. "; |

243 | BOOST_REQUIRE (is_straight_line_drawing(g, drawing)); |

244 | |

245 | return 0; |

246 | } |

247 | |

248 | |

249 | |

250 | |

251 | |

252 | |

253 | |

254 | int test_main(int argc, char* argv[]) |

255 | { |

256 | |

257 | std::string input_directory_str = "planar_input_graphs"; |

258 | if (argc > 1) |

259 | { |

260 | input_directory_str = std::string(argv[1]); |

261 | } |

262 | |

263 | std::cout << "Reading planar input files from "<< input_directory_str |

264 | << std::endl; |

265 | |

266 | filesystem::path input_directory = |

267 | filesystem::system_complete(filesystem::path(input_directory_str)); |

268 | const std::string dimacs_extension = ".dimacs"; |

269 | |

270 | filesystem::directory_iterator dir_end; |

271 | for( filesystem::directory_iterator dir_itr(input_directory); |

272 | dir_itr != dir_end; ++dir_itr) |

273 | { |

274 | |

275 | if (dir_itr->path().extension() != dimacs_extension) |

276 | continue; |

277 | |

278 | std::cout << "Testing "<< dir_itr->path().leaf() << "... "; |

279 | BOOST_REQUIRE (test_graph(dir_itr->path().string()) == 0); |

280 | |

281 | std::cout << std::endl; |

282 | } |

283 | |

284 | return 0; |

285 | |

286 | } |

287 |