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

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