1 | // Copyright 2004-5 Trustees of Indiana University |
2 | |
3 | // Use, modification and distribution is subject to the Boost Software |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
5 | // http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | // |
8 | // graphviz_test.cpp - Test cases for the Boost.Spirit implementation of a |
9 | // Graphviz DOT Language reader. |
10 | // |
11 | |
12 | // Author: Ronald Garcia |
13 | |
14 | #define BOOST_GRAPHVIZ_USE_ISTREAM |
15 | #include <boost/regex.hpp> |
16 | #include <boost/graph/graphviz.hpp> |
17 | #include <boost/assign/std/map.hpp> |
18 | #include <boost/graph/adjacency_list.hpp> |
19 | #include <boost/graph/compressed_sparse_row_graph.hpp> |
20 | #include <boost/graph/graph_traits.hpp> |
21 | #include <boost/tuple/tuple.hpp> |
22 | #include <boost/property_map/dynamic_property_map.hpp> |
23 | #include <boost/core/lightweight_test.hpp> |
24 | #include <algorithm> |
25 | #include <string> |
26 | #include <iostream> |
27 | #include <iterator> |
28 | #include <map> |
29 | #include <utility> |
30 | #include <cmath> |
31 | |
32 | template<class T> |
33 | class close_to { |
34 | public: |
35 | explicit close_to(T f) |
36 | : f_(f) { } |
37 | |
38 | bool operator()(T l, T r) const { |
39 | return std::abs(l - r) <= |
40 | (std::max)(f_ * (std::max)(std::abs(l), std::abs(r)), T()); |
41 | } |
42 | |
43 | private: |
44 | T f_; |
45 | }; |
46 | |
47 | using namespace std; |
48 | using namespace boost; |
49 | |
50 | using namespace boost::assign; |
51 | |
52 | typedef std::string node_t; |
53 | typedef std::pair< node_t, node_t > edge_t; |
54 | |
55 | typedef std::map< node_t, float > mass_map_t; |
56 | typedef std::map< edge_t, double > weight_map_t; |
57 | |
58 | template < typename graph_t, typename NameMap, typename MassMap, |
59 | typename WeightMap > |
60 | bool test_graph(std::istream& dotfile, graph_t& graph, |
61 | std::size_t correct_num_vertices, mass_map_t const& masses, |
62 | weight_map_t const& weights, std::string const& node_id, |
63 | std::string const& g_name, NameMap name, MassMap mass, WeightMap weight); |
64 | |
65 | template < typename graph_t > |
66 | bool test_graph(std::istream& dotfile, std::size_t correct_num_vertices, |
67 | mass_map_t const& masses, weight_map_t const& weights, |
68 | std::string const& node_id = "node_id" , |
69 | std::string const& g_name = std::string()) |
70 | { |
71 | graph_t g; |
72 | return test_graph(dotfile, g, correct_num_vertices, masses, weights, |
73 | node_id, g_name, get(vertex_name, g), get(vertex_color, g), |
74 | get(edge_weight, g)); |
75 | } |
76 | |
77 | template < typename graph_t, typename NameMap, typename MassMap, |
78 | typename WeightMap > |
79 | bool test_graph(std::istream& dotfile, graph_t& graph, |
80 | std::size_t correct_num_vertices, mass_map_t const& masses, |
81 | weight_map_t const& weights, std::string const& node_id, |
82 | std::string const& g_name, NameMap name, MassMap mass, WeightMap weight) |
83 | { |
84 | |
85 | // Construct a graph and set up the dynamic_property_maps. |
86 | dynamic_properties dp(ignore_other_properties); |
87 | dp.property(node_id, name); |
88 | dp.property("mass" , mass); |
89 | dp.property("weight" , weight); |
90 | |
91 | boost::ref_property_map< graph_t*, std::string > gname( |
92 | get_property(graph, graph_name)); |
93 | dp.property("name" , gname); |
94 | |
95 | bool result = true; |
96 | #ifdef BOOST_GRAPHVIZ_USE_ISTREAM |
97 | if (read_graphviz(dotfile, graph, dp, node_id)) |
98 | { |
99 | #else |
100 | std::string data; |
101 | dotfile >> std::noskipws; |
102 | std::copy(std::istream_iterator< char >(dotfile), |
103 | std::istream_iterator< char >(), std::back_inserter(data)); |
104 | if (read_graphviz(data.begin(), data.end(), graph, dp, node_id)) |
105 | { |
106 | #endif |
107 | // check correct vertex count |
108 | BOOST_TEST_EQ(num_vertices(graph), correct_num_vertices); |
109 | // check masses |
110 | if (!masses.empty()) |
111 | { |
112 | // assume that all the masses have been set |
113 | // for each vertex: |
114 | typename graph_traits< graph_t >::vertex_iterator i, j; |
115 | for (boost::tie(i, j) = vertices(graph); i != j; ++i) |
116 | { |
117 | // - get its name |
118 | std::string node_name = get(name, *i); |
119 | // - get its mass |
120 | float node_mass = get(mass, *i); |
121 | BOOST_TEST(masses.find(node_name) != masses.end()); |
122 | float ref_mass = masses.find(x: node_name)->second; |
123 | // - compare the mass to the result in the table |
124 | BOOST_TEST_WITH(node_mass, ref_mass, close_to<float>(0.01f)); |
125 | } |
126 | } |
127 | // check weights |
128 | if (!weights.empty()) |
129 | { |
130 | // assume that all weights have been set |
131 | /// for each edge: |
132 | typename graph_traits< graph_t >::edge_iterator i, j; |
133 | for (boost::tie(i, j) = edges(graph); i != j; ++i) |
134 | { |
135 | // - get its name |
136 | std::pair< std::string, std::string > edge_name = make_pair( |
137 | get(name, source(*i, graph)), get(name, target(*i, graph))); |
138 | // - get its weight |
139 | double edge_weight = get(weight, *i); |
140 | BOOST_TEST(weights.find(edge_name) != weights.end()); |
141 | double ref_weight = weights.find(x: edge_name)->second; |
142 | // - compare the weight to teh result in the table |
143 | BOOST_TEST_WITH(edge_weight, ref_weight, close_to<double>(0.01)); |
144 | } |
145 | } |
146 | if (!g_name.empty()) |
147 | { |
148 | std::string parsed_name = get_property(graph, graph_name); |
149 | BOOST_TEST(parsed_name == g_name); |
150 | } |
151 | } |
152 | else |
153 | { |
154 | std::cerr << "Parsing Failed!\n" ; |
155 | result = false; |
156 | } |
157 | |
158 | return result; |
159 | } |
160 | |
161 | // int test_main(int, char*[]) { |
162 | |
163 | typedef istringstream gs_t; |
164 | |
165 | typedef property< vertex_name_t, std::string, |
166 | property< vertex_color_t, float > > |
167 | vertex_p; |
168 | typedef property< edge_weight_t, double > edge_p; |
169 | typedef property< graph_name_t, std::string > graph_p; |
170 | |
171 | struct vertex_p_bundled |
172 | { |
173 | std::string name; |
174 | float color; |
175 | }; |
176 | struct edge_p_bundled |
177 | { |
178 | double weight; |
179 | }; |
180 | |
181 | // Basic directed graph tests |
182 | void test_basic_directed_graph_1() |
183 | { |
184 | mass_map_t masses; |
185 | insert(c&: masses)("a" , 0.0f)("c" , 7.7f)("e" , 6.66f); |
186 | gs_t gs("digraph { a node [mass = 7.7] c e [mass = 6.66] }" ); |
187 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
188 | graph_t; |
189 | BOOST_TEST((test_graph< graph_t >(gs, 3, masses, weight_map_t()))); |
190 | } |
191 | |
192 | void test_basic_directed_graph_2() |
193 | { |
194 | mass_map_t masses; |
195 | insert(c&: masses)("a" , 0.0f)("e" , 6.66f); |
196 | gs_t gs("digraph { a node [mass = 7.7] \"a\" e [mass = 6.66] }" ); |
197 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
198 | graph_t; |
199 | BOOST_TEST((test_graph< graph_t >(gs, 2, masses, weight_map_t()))); |
200 | } |
201 | |
202 | void test_basic_directed_graph_3() |
203 | { |
204 | weight_map_t weights; |
205 | insert(c&: weights)(make_pair(x: "a" , y: "b" ), 0.0)(make_pair(x: "c" , y: "d" ), 7.7)( |
206 | make_pair(x: "e" , y: "f" ), 6.66)(make_pair(x: "d" , y: "e" ), 0.5)( |
207 | make_pair(x: "e" , y: "a" ), 0.5); |
208 | gs_t gs("digraph { a -> b eDge [weight = 7.7] " |
209 | "c -> d e-> f [weight = 6.66] " |
210 | "d ->e->a [weight=.5]}" ); |
211 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
212 | graph_t; |
213 | BOOST_TEST((test_graph< graph_t >(gs, 6, mass_map_t(), weights))); |
214 | } |
215 | |
216 | // undirected graph with alternate node_id property name |
217 | void test_undirected_graph_alternate_node_id() |
218 | { |
219 | mass_map_t masses; |
220 | insert(c&: masses)("a" , 0.0f)("c" , 7.7f)("e" , 6.66f); |
221 | gs_t gs("graph { a node [mass = 7.7] c e [mass = 6.66] }" ); |
222 | typedef adjacency_list< vecS, vecS, undirectedS, vertex_p, edge_p, graph_p > |
223 | graph_t; |
224 | BOOST_TEST( |
225 | (test_graph< graph_t >(gs, 3, masses, weight_map_t(), "nodenames" ))); |
226 | } |
227 | |
228 | // Basic undirected graph tests |
229 | void test_basic_undirected_graph_1() |
230 | { |
231 | mass_map_t masses; |
232 | insert(c&: masses)("a" , 0.0f)("c" , 7.7f)("e" , 6.66f); |
233 | gs_t gs("graph { a node [mass = 7.7] c e [mass =\\\n6.66] }" ); |
234 | typedef adjacency_list< vecS, vecS, undirectedS, vertex_p, edge_p, graph_p > |
235 | graph_t; |
236 | BOOST_TEST((test_graph< graph_t >(gs, 3, masses, weight_map_t()))); |
237 | } |
238 | |
239 | void test_basic_undirected_graph_2() |
240 | { |
241 | weight_map_t weights; |
242 | insert(c&: weights)(make_pair(x: "a" , y: "b" ), 0.0)(make_pair(x: "c" , y: "d" ), 7.7)( |
243 | make_pair(x: "e" , y: "f" ), 6.66); |
244 | gs_t gs("graph { a -- b eDge [weight = 7.7] " |
245 | "c -- d e -- f [weight = 6.66] }" ); |
246 | typedef adjacency_list< vecS, vecS, undirectedS, vertex_p, edge_p, graph_p > |
247 | graph_t; |
248 | BOOST_TEST((test_graph< graph_t >(gs, 6, mass_map_t(), weights))); |
249 | } |
250 | |
251 | // Mismatch directed graph test |
252 | void test_mismatch_directed_graph() |
253 | { |
254 | mass_map_t masses; |
255 | insert(c&: masses)("a" , 0.0f)("c" , 7.7f)("e" , 6.66f); |
256 | gs_t gs("graph { a nodE [mass = 7.7] c e [mass = 6.66] }" ); |
257 | try |
258 | { |
259 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, |
260 | graph_p > |
261 | graph_t; |
262 | test_graph< graph_t >(dotfile&: gs, correct_num_vertices: 3, masses, weights: weight_map_t()); |
263 | BOOST_ERROR("Failed to throw boost::undirected_graph_error." ); |
264 | } |
265 | catch (boost::undirected_graph_error&) |
266 | { |
267 | } |
268 | catch (boost::directed_graph_error&) |
269 | { |
270 | BOOST_ERROR("Threw boost::directed_graph_error, should have thrown " |
271 | "boost::undirected_graph_error." ); |
272 | } |
273 | } |
274 | |
275 | // Mismatch undirected graph test |
276 | void test_mismatch_undirected_graph() |
277 | { |
278 | mass_map_t masses; |
279 | insert(c&: masses)("a" , 0.0f)("c" , 7.7f)("e" , 6.66f); |
280 | gs_t gs("digraph { a node [mass = 7.7] c e [mass = 6.66] }" ); |
281 | try |
282 | { |
283 | typedef adjacency_list< vecS, vecS, undirectedS, vertex_p, edge_p, |
284 | graph_p > |
285 | graph_t; |
286 | test_graph< graph_t >(dotfile&: gs, correct_num_vertices: 3, masses, weights: weight_map_t()); |
287 | BOOST_ERROR("Failed to throw boost::directed_graph_error." ); |
288 | } |
289 | catch (boost::directed_graph_error&) |
290 | { |
291 | } |
292 | } |
293 | |
294 | // Complain about parallel edges |
295 | void test_complain_about_parallel_edges() |
296 | { |
297 | weight_map_t weights; |
298 | insert(c&: weights)(make_pair(x: "a" , y: "b" ), 7.7); |
299 | gs_t gs("diGraph { a -> b [weight = 7.7] a -> b [weight = 7.7] }" ); |
300 | try |
301 | { |
302 | typedef adjacency_list< setS, vecS, directedS, vertex_p, edge_p, |
303 | graph_p > |
304 | graph_t; |
305 | test_graph< graph_t >(dotfile&: gs, correct_num_vertices: 2, masses: mass_map_t(), weights); |
306 | BOOST_ERROR("Failed to throw boost::bad_parallel_edge." ); |
307 | } |
308 | catch (boost::bad_parallel_edge&) |
309 | { |
310 | } |
311 | } |
312 | |
313 | // Handle parallel edges gracefully |
314 | void test_handle_parallel_edges_gracefully() |
315 | { |
316 | weight_map_t weights; |
317 | insert(c&: weights)(make_pair(x: "a" , y: "b" ), 7.7); |
318 | gs_t gs("digraph { a -> b [weight = 7.7] a -> b [weight = 7.7] }" ); |
319 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
320 | graph_t; |
321 | BOOST_TEST((test_graph< graph_t >(gs, 2, mass_map_t(), weights))); |
322 | } |
323 | |
324 | // Graph Property Test 1 |
325 | void test_graph_property_test_1() |
326 | { |
327 | mass_map_t masses; |
328 | insert(c&: masses)("a" , 0.0f)("c" , 0.0f)("e" , 6.66f); |
329 | gs_t gs("digraph { graph [name=\"foo \\\"escaped\\\"\"] a c e [mass = " |
330 | "6.66] }" ); |
331 | std::string graph_name("foo \"escaped\"" ); |
332 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
333 | graph_t; |
334 | BOOST_TEST( |
335 | (test_graph< graph_t >(gs, 3, masses, weight_map_t(), "" , graph_name))); |
336 | } |
337 | |
338 | // Graph Property Test 2 |
339 | void test_graph_property_test_2() |
340 | { |
341 | mass_map_t masses; |
342 | insert(c&: masses)("a" , 0.0f)("c" , 0.0f)("e" , 6.66f); |
343 | gs_t gs("digraph { name=\"fo\"+ \"\\\no\" a c e [mass = 6.66] }" ); |
344 | std::string graph_name("foo" ); |
345 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
346 | graph_t; |
347 | BOOST_TEST( |
348 | (test_graph< graph_t >(gs, 3, masses, weight_map_t(), "" , graph_name))); |
349 | } |
350 | |
351 | // Graph Property Test 3 (HTML) |
352 | void test_graph_property_test_3() |
353 | { |
354 | mass_map_t masses; |
355 | insert(c&: masses)("a" , 0.0f)("c" , 0.0f)("e" , 6.66f); |
356 | std::string graph_name |
357 | = "<html title=\"x'\" title2='y\"'>foo<b><![CDATA[><bad " |
358 | "tag&>]]>bar</b>\n<br/>\nbaz</html>" ; |
359 | gs_t gs("digraph { name=" + graph_name + " a c e [mass = 6.66] }" ); |
360 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
361 | graph_t; |
362 | BOOST_TEST( |
363 | (test_graph< graph_t >(gs, 3, masses, weight_map_t(), "" , graph_name))); |
364 | } |
365 | |
366 | // Comments embedded in strings |
367 | void () |
368 | { |
369 | gs_t gs("digraph { " |
370 | "a0 [ label = \"//depot/path/to/file_14#4\" ];" |
371 | "a1 [ label = \"//depot/path/to/file_29#9\" ];" |
372 | "a0 -> a1 [ color=gray ];" |
373 | "}" ); |
374 | typedef adjacency_list< vecS, vecS, directedS, vertex_p, edge_p, graph_p > |
375 | graph_t; |
376 | BOOST_TEST((test_graph< graph_t >(gs, 2, mass_map_t(), weight_map_t()))); |
377 | } |
378 | |
379 | #if 0 // Currently broken |
380 | void test_basic_csr_directed_graph() { |
381 | weight_map_t weights; |
382 | insert( weights )(make_pair("a" ,"b" ),0.0) |
383 | (make_pair("c" ,"d" ),7.7)(make_pair("e" ,"f" ),6.66) |
384 | (make_pair("d" ,"e" ),0.5)(make_pair("e" ,"a" ),0.5); |
385 | gs_t gs("digraph { a -> b eDge [weight = 7.7] " |
386 | "c -> d e-> f [weight = 6.66] " |
387 | "d ->e->a [weight=.5]}" ); |
388 | typedef compressed_sparse_row_graph<directedS, vertex_p_bundled, edge_p_bundled, graph_p > graph_t; |
389 | BOOST_TEST((test_graph<graph_t>(gs,6,mass_map_t(),weights,"node_id" ,"" ,&vertex_p_bundled::name,&vertex_p_bundled::color,&edge_p_bundled::weight))); |
390 | } |
391 | #endif |
392 | |
393 | void test_basic_csr_directed_graph_ext_props() |
394 | { |
395 | weight_map_t weights; |
396 | insert(c&: weights)(make_pair(x: "a" , y: "b" ), 0.0)(make_pair(x: "c" , y: "d" ), 7.7)( |
397 | make_pair(x: "e" , y: "f" ), 6.66)(make_pair(x: "d" , y: "e" ), 0.5)( |
398 | make_pair(x: "e" , y: "a" ), 0.5); |
399 | gs_t gs("digraph { a -> b eDge [weight = 7.7] " |
400 | "c -> d e-> f [weight = 6.66] " |
401 | "d ->e->a [weight=.5]}" ); |
402 | typedef compressed_sparse_row_graph< directedS, no_property, no_property, |
403 | graph_p > |
404 | graph_t; |
405 | graph_t g; |
406 | vector_property_map< std::string, |
407 | property_map< graph_t, vertex_index_t >::const_type > |
408 | vertex_name(get(vertex_index, g)); |
409 | vector_property_map< float, |
410 | property_map< graph_t, vertex_index_t >::const_type > |
411 | vertex_color(get(vertex_index, g)); |
412 | vector_property_map< double, |
413 | property_map< graph_t, edge_index_t >::const_type > |
414 | edge_weight(get(edge_index, g)); |
415 | BOOST_TEST((test_graph(gs, g, 6, mass_map_t(), weights, "node_id" , "" , |
416 | vertex_name, vertex_color, edge_weight))); |
417 | } |
418 | |
419 | int main() |
420 | { |
421 | test_basic_directed_graph_1(); |
422 | test_basic_directed_graph_2(); |
423 | test_basic_directed_graph_3(); |
424 | test_undirected_graph_alternate_node_id(); |
425 | test_basic_undirected_graph_1(); |
426 | test_basic_undirected_graph_2(); |
427 | test_mismatch_directed_graph(); |
428 | test_mismatch_undirected_graph(); |
429 | test_complain_about_parallel_edges(); |
430 | test_handle_parallel_edges_gracefully(); |
431 | test_graph_property_test_1(); |
432 | test_graph_property_test_2(); |
433 | test_graph_property_test_3(); |
434 | test_comments_embedded_in_strings(); |
435 | test_basic_csr_directed_graph_ext_props(); |
436 | return boost::report_errors(); |
437 | } |
438 | |