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