1 // Copyright 2004-5 Trustees of Indiana University
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)
8 // graphviz_test.cpp - Test cases for the Boost.Spirit implementation of a
9 // Graphviz DOT Language reader.
12 // Author: Ronald Garcia
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>
35 explicit close_to(T f
)
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());
48 using namespace boost
;
50 using namespace boost::assign
;
52 typedef std::string node_t
;
53 typedef std::pair
< node_t
, node_t
> edge_t
;
55 typedef std::map
< node_t
, float > mass_map_t
;
56 typedef std::map
< edge_t
, double > weight_map_t
;
58 template < typename graph_t
, typename NameMap
, typename MassMap
,
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
);
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())
72 return test_graph(dotfile
, g
, correct_num_vertices
, masses
, weights
,
73 node_id
, g_name
, get(vertex_name
, g
), get(vertex_color
, g
),
77 template < typename graph_t
, typename NameMap
, typename MassMap
,
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
)
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
);
91 boost::ref_property_map
< graph_t
*, std::string
> gname(
92 get_property(graph
, graph_name
));
93 dp
.property("name", gname
);
96 #ifdef BOOST_GRAPHVIZ_USE_ISTREAM
97 if (read_graphviz(dotfile
, graph
, dp
, node_id
))
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
))
107 // check correct vertex count
108 BOOST_TEST_EQ(num_vertices(graph
), correct_num_vertices
);
112 // assume that all the masses have been set
114 typename graph_traits
< graph_t
>::vertex_iterator i
, j
;
115 for (boost::tie(i
, j
) = vertices(graph
); i
!= j
; ++i
)
118 std::string node_name
= get(name
, *i
);
120 float node_mass
= get(mass
, *i
);
121 BOOST_TEST(masses
.find(node_name
) != masses
.end());
122 float ref_mass
= masses
.find(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
));
128 if (!weights
.empty())
130 // assume that all weights have been set
132 typename graph_traits
< graph_t
>::edge_iterator i
, j
;
133 for (boost::tie(i
, j
) = edges(graph
); i
!= j
; ++i
)
136 std::pair
< std::string
, std::string
> edge_name
= make_pair(
137 get(name
, source(*i
, graph
)), get(name
, target(*i
, graph
)));
139 double edge_weight
= get(weight
, *i
);
140 BOOST_TEST(weights
.find(edge_name
) != weights
.end());
141 double ref_weight
= weights
.find(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));
148 std::string parsed_name
= get_property(graph
, graph_name
);
149 BOOST_TEST(parsed_name
== g_name
);
154 std::cerr
<< "Parsing Failed!\n";
161 // int test_main(int, char*[]) {
163 typedef istringstream gs_t
;
165 typedef property
< vertex_name_t
, std::string
,
166 property
< vertex_color_t
, float > >
168 typedef property
< edge_weight_t
, double > edge_p
;
169 typedef property
< graph_name_t
, std::string
> graph_p
;
171 struct vertex_p_bundled
176 struct edge_p_bundled
181 // Basic directed graph tests
182 void test_basic_directed_graph_1()
185 insert(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
>
189 BOOST_TEST((test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t())));
192 void test_basic_directed_graph_2()
195 insert(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
>
199 BOOST_TEST((test_graph
< graph_t
>(gs
, 2, masses
, weight_map_t())));
202 void test_basic_directed_graph_3()
204 weight_map_t weights
;
205 insert(weights
)(make_pair("a", "b"), 0.0)(make_pair("c", "d"), 7.7)(
206 make_pair("e", "f"), 6.66)(make_pair("d", "e"), 0.5)(
207 make_pair("e", "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
>
213 BOOST_TEST((test_graph
< graph_t
>(gs
, 6, mass_map_t(), weights
)));
216 // undirected graph with alternate node_id property name
217 void test_undirected_graph_alternate_node_id()
220 insert(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
>
225 (test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t(), "nodenames")));
228 // Basic undirected graph tests
229 void test_basic_undirected_graph_1()
232 insert(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
>
236 BOOST_TEST((test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t())));
239 void test_basic_undirected_graph_2()
241 weight_map_t weights
;
242 insert(weights
)(make_pair("a", "b"), 0.0)(make_pair("c", "d"), 7.7)(
243 make_pair("e", "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
>
248 BOOST_TEST((test_graph
< graph_t
>(gs
, 6, mass_map_t(), weights
)));
251 // Mismatch directed graph test
252 void test_mismatch_directed_graph()
255 insert(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] }");
259 typedef adjacency_list
< vecS
, vecS
, directedS
, vertex_p
, edge_p
,
262 test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t());
263 BOOST_ERROR("Failed to throw boost::undirected_graph_error.");
265 catch (boost::undirected_graph_error
&)
268 catch (boost::directed_graph_error
&)
270 BOOST_ERROR("Threw boost::directed_graph_error, should have thrown "
271 "boost::undirected_graph_error.");
275 // Mismatch undirected graph test
276 void test_mismatch_undirected_graph()
279 insert(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] }");
283 typedef adjacency_list
< vecS
, vecS
, undirectedS
, vertex_p
, edge_p
,
286 test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t());
287 BOOST_ERROR("Failed to throw boost::directed_graph_error.");
289 catch (boost::directed_graph_error
&)
294 // Complain about parallel edges
295 void test_complain_about_parallel_edges()
297 weight_map_t weights
;
298 insert(weights
)(make_pair("a", "b"), 7.7);
299 gs_t
gs("diGraph { a -> b [weight = 7.7] a -> b [weight = 7.7] }");
302 typedef adjacency_list
< setS
, vecS
, directedS
, vertex_p
, edge_p
,
305 test_graph
< graph_t
>(gs
, 2, mass_map_t(), weights
);
306 BOOST_ERROR("Failed to throw boost::bad_parallel_edge.");
308 catch (boost::bad_parallel_edge
&)
313 // Handle parallel edges gracefully
314 void test_handle_parallel_edges_gracefully()
316 weight_map_t weights
;
317 insert(weights
)(make_pair("a", "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
>
321 BOOST_TEST((test_graph
< graph_t
>(gs
, 2, mass_map_t(), weights
)));
324 // Graph Property Test 1
325 void test_graph_property_test_1()
328 insert(masses
)("a", 0.0f
)("c", 0.0f
)("e", 6.66f
);
329 gs_t
gs("digraph { graph [name=\"foo \\\"escaped\\\"\"] a c e [mass = "
331 std::string
graph_name("foo \"escaped\"");
332 typedef adjacency_list
< vecS
, vecS
, directedS
, vertex_p
, edge_p
, graph_p
>
335 (test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t(), "", graph_name
)));
338 // Graph Property Test 2
339 void test_graph_property_test_2()
342 insert(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
>
348 (test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t(), "", graph_name
)));
351 // Graph Property Test 3 (HTML)
352 void test_graph_property_test_3()
355 insert(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
>
363 (test_graph
< graph_t
>(gs
, 3, masses
, weight_map_t(), "", graph_name
)));
366 // Comments embedded in strings
367 void test_comments_embedded_in_strings()
370 "a0 [ label = \"//depot/path/to/file_14#4\" ];"
371 "a1 [ label = \"//depot/path/to/file_29#9\" ];"
372 "a0 -> a1 [ color=gray ];"
374 typedef adjacency_list
< vecS
, vecS
, directedS
, vertex_p
, edge_p
, graph_p
>
376 BOOST_TEST((test_graph
< graph_t
>(gs
, 2, mass_map_t(), weight_map_t())));
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
)));
393 void test_basic_csr_directed_graph_ext_props()
395 weight_map_t weights
;
396 insert(weights
)(make_pair("a", "b"), 0.0)(make_pair("c", "d"), 7.7)(
397 make_pair("e", "f"), 6.66)(make_pair("d", "e"), 0.5)(
398 make_pair("e", "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
,
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
)));
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();