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
32template<class T>
33class close_to {
34public:
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
43private:
44 T f_;
45};
46
47using namespace std;
48using namespace boost;
49
50using namespace boost::assign;
51
52typedef std::string node_t;
53typedef std::pair< node_t, node_t > edge_t;
54
55typedef std::map< node_t, float > mass_map_t;
56typedef std::map< edge_t, double > weight_map_t;
57
58template < typename graph_t, typename NameMap, typename MassMap,
59 typename WeightMap >
60bool 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
65template < typename graph_t >
66bool 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
77template < typename graph_t, typename NameMap, typename MassMap,
78 typename WeightMap >
79bool 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
163typedef istringstream gs_t;
164
165typedef property< vertex_name_t, std::string,
166 property< vertex_color_t, float > >
167 vertex_p;
168typedef property< edge_weight_t, double > edge_p;
169typedef property< graph_name_t, std::string > graph_p;
170
171struct vertex_p_bundled
172{
173 std::string name;
174 float color;
175};
176struct edge_p_bundled
177{
178 double weight;
179};
180
181// Basic directed graph tests
182void 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
192void 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
202void 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
217void 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
229void 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
239void 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
252void 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
276void 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
295void 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
314void 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
325void 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
339void 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)
352void 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
367void test_comments_embedded_in_strings()
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
393void 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
419int 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

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