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

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