mirror of
https://github.com/boostorg/graph.git
synced 2025-05-09 23:14:00 +00:00
507 lines
16 KiB
C++
507 lines
16 KiB
C++
// Copyright 2004-5 Trustees of Indiana University
|
|
//
|
|
|
|
// Use, modification and distribution is subject to the Boost Software
|
|
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
|
// http://www.boost.org/LICENSE_1_0.txt)
|
|
|
|
//
|
|
// graphviz_test.cpp - Test cases for the Graphviz DOT Language reader
|
|
//
|
|
|
|
// Author: Ronald Garcia
|
|
|
|
#define BOOST_GRAPHVIZ_USE_ISTREAM
|
|
#include <boost/graph/graphviz.hpp>
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
#include <boost/graph/compressed_sparse_row_graph.hpp>
|
|
#include <boost/core/lightweight_test.hpp>
|
|
#include <boost/property_map/function_property_map.hpp>
|
|
#include <iostream>
|
|
#include <cmath>
|
|
|
|
typedef std::string node_t;
|
|
typedef std::pair< node_t, node_t > edge_t;
|
|
|
|
typedef float Mass;
|
|
typedef double Weight;
|
|
typedef std::map< node_t, Mass > expected_masses_t;
|
|
typedef std::map< edge_t, Weight > expected_weights_t;
|
|
|
|
struct Fixture
|
|
{
|
|
std::string graphviz_text;
|
|
size_t correct_num_vertices;
|
|
expected_masses_t masses;
|
|
expected_weights_t weights;
|
|
};
|
|
|
|
namespace Samples
|
|
{
|
|
namespace Directed
|
|
{
|
|
static Fixture const basic {
|
|
"digraph { a node [mass = 7.7] c e [mass = 6.66] }",
|
|
3,
|
|
{ { "a", 0.0f }, { "c", 7.7f }, { "e", 6.66f } },
|
|
expected_weights_t(),
|
|
};
|
|
|
|
static Fixture const basic_aliased {
|
|
"digraph { a node [mass = 7.7] \"a\" e [mass = 6.66] }",
|
|
2,
|
|
{ { "a", 0.0f }, { "e", 6.66f } },
|
|
expected_weights_t(),
|
|
};
|
|
|
|
static Fixture const full {
|
|
"digraph { a -> b eDge [weight = 7.7] "
|
|
"c -> d e-> f [weight = 6.66] "
|
|
"d ->e->a [weight=.5]}",
|
|
6,
|
|
expected_masses_t(),
|
|
{
|
|
{ edge_t("a", "b"), 0.0 }, { edge_t("c", "d"), 7.7 },
|
|
{ edge_t("e", "f"), 6.66 }, { edge_t("d", "e"), 0.5 },
|
|
{ edge_t("e", "a"), 0.5 } //
|
|
},
|
|
};
|
|
}
|
|
|
|
namespace Undirected
|
|
{
|
|
static Fixture const basic {
|
|
"graph { a nodE [mass = 7.7] c e [mass =\\\n6.66] }",
|
|
3,
|
|
{ { "a", 0.0f }, { "c", 7.7f }, { "e", 6.66f } },
|
|
expected_weights_t(),
|
|
};
|
|
|
|
static Fixture const full {
|
|
"graph { a -- b eDge [weight = 7.7] "
|
|
"c -- d e -- f [weight = 6.66] }",
|
|
6,
|
|
expected_masses_t(),
|
|
{
|
|
{ edge_t("a", "b"), 0.0 }, { edge_t("c", "d"), 7.7 },
|
|
{ edge_t("e", "f"), 6.66 } //
|
|
},
|
|
};
|
|
}
|
|
|
|
Fixture const all_directed[] {
|
|
Directed::basic,
|
|
Directed::basic_aliased,
|
|
Directed::full,
|
|
};
|
|
Fixture const all_undirected[] {
|
|
Undirected::basic,
|
|
Undirected::full,
|
|
};
|
|
} // Samples
|
|
|
|
namespace ComparisonDriver
|
|
{
|
|
template < class T > class close_to
|
|
{
|
|
public:
|
|
explicit close_to(T f) : f_(f) { assert(f >= 0); }
|
|
|
|
bool operator()(T l, T r) const
|
|
{
|
|
using std::abs;
|
|
return abs(l - r) <= f_ * (std::max)(abs(l), abs(r));
|
|
}
|
|
|
|
private:
|
|
T f_;
|
|
};
|
|
|
|
template < typename graph_t, typename NameMap, typename MassMap,
|
|
typename WeightMap >
|
|
bool test_graph(std::string const& text, graph_t& graph,
|
|
std::size_t correct_num_vertices, expected_masses_t const& expected_masses,
|
|
expected_weights_t const& expected_weights, std::string const& node_id,
|
|
std::string const& g_name, NameMap name_map, MassMap mass_map,
|
|
WeightMap weight_map)
|
|
{
|
|
// Construct a graph and set up the dynamic_property_maps.
|
|
boost::dynamic_properties dp(boost::ignore_other_properties);
|
|
dp.property(node_id, name_map);
|
|
dp.property("mass", mass_map);
|
|
dp.property("weight", weight_map);
|
|
|
|
boost::ref_property_map< graph_t*, std::string > gname(
|
|
get_property(graph, boost::graph_name));
|
|
dp.property("name", gname);
|
|
|
|
bool result = true;
|
|
#ifdef BOOST_GRAPHVIZ_USE_ISTREAM
|
|
std::istringstream is(text);
|
|
if (read_graphviz(is, graph, dp, node_id))
|
|
#else
|
|
if (read_graphviz(text.begin(), text.end(), graph, dp, node_id))
|
|
#endif
|
|
{
|
|
// check correct vertex count
|
|
BOOST_TEST_EQ(num_vertices(graph), correct_num_vertices);
|
|
// check masses
|
|
if (!expected_masses.empty())
|
|
{
|
|
// assume that all the masses have been set
|
|
// for each vertex:
|
|
typename boost::graph_traits< graph_t >::vertex_iterator i, j;
|
|
for (boost::tie(i, j) = vertices(graph); i != j; ++i)
|
|
{
|
|
std::string node_name = get(name_map, *i);
|
|
Mass node_mass = get(mass_map, *i);
|
|
BOOST_TEST(
|
|
expected_masses.find(node_name) != expected_masses.end());
|
|
Mass ref_mass = expected_masses.find(node_name)->second;
|
|
// - compare the mass to the result in the table
|
|
BOOST_TEST_WITH(node_mass, ref_mass, close_to< Mass >(0.0001f));
|
|
}
|
|
}
|
|
// check weights
|
|
if (!expected_weights.empty())
|
|
{
|
|
// assume that all weights have been set
|
|
/// for each edge:
|
|
typename boost::graph_traits< graph_t >::edge_iterator i, j;
|
|
for (boost::tie(i, j) = edges(graph); i != j; ++i)
|
|
{
|
|
// - get its name
|
|
std::pair< std::string, std::string > edge_name
|
|
= make_pair(get(name_map, source(*i, graph)),
|
|
get(name_map, target(*i, graph)));
|
|
// - get its weight
|
|
Weight edge_weight = get(weight_map, *i);
|
|
BOOST_TEST(
|
|
expected_weights.find(edge_name) != expected_weights.end());
|
|
Weight ref_weight = expected_weights.find(edge_name)->second;
|
|
// - compare the weight to the result in the table
|
|
BOOST_TEST_WITH(
|
|
edge_weight, ref_weight, close_to< Weight >(0.000001));
|
|
}
|
|
}
|
|
if (!g_name.empty())
|
|
{
|
|
std::string parsed_name = get_property(graph, boost::graph_name);
|
|
BOOST_TEST(parsed_name == g_name);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
std::cerr << "Parsing Failed!\n";
|
|
result = false;
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
template < typename graph_t, typename NameMap, typename MassMap,
|
|
typename WeightMap >
|
|
bool test_graph(Fixture const& sample, graph_t& g, std::string const& node_id,
|
|
std::string const& g_name, NameMap name_map, MassMap mass_map,
|
|
WeightMap weight_map)
|
|
{
|
|
return test_graph(sample.graphviz_text, g, sample.correct_num_vertices,
|
|
sample.masses, sample.weights, node_id, g_name, name_map, mass_map,
|
|
weight_map);
|
|
}
|
|
|
|
template < typename graph_t >
|
|
bool test_graph(std::string const& dottext, std::size_t correct_num_vertices,
|
|
expected_masses_t const& masses, expected_weights_t const& weights,
|
|
std::string const& node_id = "node_id", std::string const& g_name = "")
|
|
{
|
|
graph_t g;
|
|
return test_graph(dottext, g, correct_num_vertices, masses, weights,
|
|
node_id, g_name, get(boost::vertex_name, g),
|
|
get(boost::vertex_color, g), get(boost::edge_weight, g));
|
|
}
|
|
|
|
template < typename graph_t >
|
|
bool test_graph(Fixture const& sample, std::string const& node_id = "node_id",
|
|
std::string const& g_name = "")
|
|
{
|
|
graph_t g;
|
|
return test_graph(sample.graphviz_text, g, sample.correct_num_vertices,
|
|
sample.masses, sample.weights, node_id, g_name, //
|
|
get(boost::vertex_name, g), //
|
|
get(boost::vertex_color, g), //
|
|
get(boost::edge_weight, g) //
|
|
);
|
|
}
|
|
}
|
|
|
|
namespace Models
|
|
{
|
|
typedef boost::property< boost::vertex_name_t, std::string,
|
|
boost::property< boost::vertex_color_t, Mass > >
|
|
vertex_p;
|
|
typedef boost::property< boost::edge_weight_t, Weight > edge_p;
|
|
typedef boost::property< boost::graph_name_t, std::string > graph_p;
|
|
|
|
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
|
|
vertex_p, edge_p, graph_p >
|
|
Graph;
|
|
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS,
|
|
vertex_p, edge_p, graph_p >
|
|
DiGraph;
|
|
|
|
typedef boost::adjacency_list< boost::setS, boost::vecS, boost::directedS,
|
|
vertex_p, edge_p, graph_p >
|
|
DiGraphNoParallel;
|
|
|
|
struct VertexBundle
|
|
{
|
|
std::string name;
|
|
Mass mass;
|
|
};
|
|
struct EdgeBundle
|
|
{
|
|
Weight weight;
|
|
};
|
|
|
|
typedef boost::compressed_sparse_row_graph< boost::directedS, VertexBundle,
|
|
EdgeBundle, graph_p >
|
|
CSRBundledGraph;
|
|
typedef boost::compressed_sparse_row_graph< boost::directedS,
|
|
boost::no_property, boost::no_property, graph_p >
|
|
CSRGraph;
|
|
} // Models
|
|
|
|
// SEHE I intended for this to be able to pass __FUNCTION__ for reporting
|
|
// failures, but there seems to be no way to achieve this with lightweight_test
|
|
#define TEST_GRAPH(Model, ...) \
|
|
BOOST_TEST((ComparisonDriver::test_graph< Model >(__VA_ARGS__)));
|
|
|
|
// Basic directed graph tests
|
|
void test_basic_directed_graph_1()
|
|
{
|
|
TEST_GRAPH(Models::DiGraph, Samples::Directed::basic);
|
|
}
|
|
|
|
void test_basic_directed_graph_2()
|
|
{
|
|
TEST_GRAPH(Models::DiGraph, Samples::Directed::basic_aliased);
|
|
}
|
|
|
|
void test_basic_directed_graph_3()
|
|
{
|
|
TEST_GRAPH(Models::DiGraph, Samples::Directed::full);
|
|
}
|
|
|
|
// undirected graph with alternate node_id property name
|
|
void test_undirected_graph_alternate_node_id()
|
|
{
|
|
TEST_GRAPH(Models::Graph, Samples::Undirected::basic, "nodenames");
|
|
}
|
|
|
|
// Basic undirected graph tests
|
|
void test_basic_undirected_graph_1()
|
|
{
|
|
TEST_GRAPH(Models::Graph, Samples::Undirected::basic);
|
|
}
|
|
|
|
void test_basic_undirected_graph_2()
|
|
{
|
|
TEST_GRAPH(Models::Graph, Samples::Undirected::full);
|
|
}
|
|
|
|
// Mismatch directed graph test
|
|
void test_mismatch_directed_graph()
|
|
{
|
|
BOOST_TEST_THROWS(TEST_GRAPH(Models::DiGraph, Samples::Undirected::basic),
|
|
boost::undirected_graph_error);
|
|
}
|
|
|
|
// Mismatch undirected graph test
|
|
void test_mismatch_undirected_graph()
|
|
{
|
|
BOOST_TEST_THROWS(TEST_GRAPH(Models::Graph, Samples::Directed::basic),
|
|
boost::directed_graph_error);
|
|
}
|
|
|
|
// Complain about parallel edges
|
|
void test_parallel_edges()
|
|
{
|
|
Fixture parallel {
|
|
"diGraph { a -> b [weight = 7.7] a -> b [weight = 7.7] }",
|
|
2,
|
|
expected_masses_t(),
|
|
{ { edge_t("a", "b"), 7.7 } },
|
|
};
|
|
TEST_GRAPH(Models::DiGraph, parallel);
|
|
BOOST_TEST_THROWS(TEST_GRAPH(Models::DiGraphNoParallel, parallel),
|
|
boost::bad_parallel_edge);
|
|
}
|
|
|
|
// Graph Property Test 1
|
|
void test_graph_property_test_1()
|
|
{
|
|
Fixture named {
|
|
"digraph { graph [name=\"foo \\\"escaped\\\"\"] a c e [mass = 6.66] "
|
|
"}",
|
|
3,
|
|
{ { "a", 0.0f }, { "c", 0.0f }, { "e", 6.66f } },
|
|
expected_weights_t(),
|
|
};
|
|
TEST_GRAPH(Models::DiGraph, named, "", "foo \"escaped\"");
|
|
}
|
|
|
|
// Graph Property Test 2
|
|
void test_graph_property_test_2()
|
|
{
|
|
Fixture named {
|
|
"digraph { name=\"fo\"+ \"\\\no\" a c e [mass = 6.66] }",
|
|
3,
|
|
{ { "a", 0.0f }, { "c", 0.0f }, { "e", 6.66f } },
|
|
expected_weights_t(),
|
|
};
|
|
TEST_GRAPH(Models::DiGraph, named, "", "foo"); // SEHE why not "foo\no"?
|
|
}
|
|
|
|
// Graph Property Test 3 (HTML)
|
|
void test_graph_property_test_3()
|
|
{
|
|
std::string graph_name
|
|
= "<html title=\"x'\" title2='y\"'>foo<b><![CDATA[><bad "
|
|
"tag&>]]>bar</b>\n<br/>\nbaz</html>";
|
|
Fixture html_named {
|
|
"digraph { name=" + graph_name + " a c e [mass = 6.66] }",
|
|
3,
|
|
{ { "a", 0.0f }, { "c", 0.0f }, { "e", 6.66f } },
|
|
expected_weights_t(),
|
|
};
|
|
TEST_GRAPH(Models::DiGraph, html_named, "", graph_name);
|
|
}
|
|
|
|
// Comments embedded in strings
|
|
void test_comments_embedded_in_strings()
|
|
{
|
|
std::string gv("digraph { "
|
|
"a0 [ label = \"//depot/path/to/file_14#4\" ];"
|
|
"a1 [ label = \"//depot/path/to/file_29#9\" ];"
|
|
"a0 -> a1 [ color=gray ];"
|
|
"}");
|
|
TEST_GRAPH(
|
|
Models::DiGraph, gv, 2, expected_masses_t(), expected_weights_t());
|
|
}
|
|
|
|
void test_basic_csr_directed_graph()
|
|
{
|
|
auto sample = Samples::Directed::full;
|
|
|
|
typedef Models::CSRBundledGraph graph_t;
|
|
graph_t g;
|
|
#ifdef UNSTABLE_PROPERTY_MAPS_FIXED // https://github.com/boostorg/graph/issues/373
|
|
BOOST_TEST((test_graph(gs, g, 6, mass_map_t(), weights, "node_id", "",
|
|
get(&vertex_p_bundled::name, g), // Warning, currently broken
|
|
get(&vertex_p_bundled::color, g), // Warning, currently broken
|
|
get(&edge_p_bundled::weight, g)) // Warning, currently broken
|
|
));
|
|
#else
|
|
typedef graph_t::vertex_descriptor V;
|
|
typedef graph_t::edge_descriptor E;
|
|
TEST_GRAPH(graph_t, sample, g, "node_id", "", //
|
|
boost::make_function_property_map< V >(
|
|
[&g](V v) -> std::string& { return g[v].name; }),
|
|
boost::make_function_property_map< V >(
|
|
[&g](V v) -> Mass& { return g[v].mass; }),
|
|
boost::make_function_property_map< E >(
|
|
[&g](E e) -> Weight& { return g[e].weight; }) //
|
|
);
|
|
#endif
|
|
}
|
|
|
|
void test_basic_csr_directed_graph_ext_props()
|
|
{
|
|
auto sample = Samples::Directed::full;
|
|
using Models::CSRGraph;
|
|
CSRGraph g;
|
|
boost::property_map< CSRGraph, boost::vertex_index_t >::const_type vidx
|
|
= get(boost::vertex_index, g);
|
|
boost::property_map< CSRGraph, boost::edge_index_t >::const_type eidx
|
|
= get(boost::edge_index, g);
|
|
|
|
boost::vector_property_map< std::string,
|
|
boost::property_map< CSRGraph, boost::vertex_index_t >::const_type >
|
|
vertex_name(vidx);
|
|
boost::vector_property_map< Mass,
|
|
boost::property_map< CSRGraph, boost::vertex_index_t >::const_type >
|
|
vertex_mass(vidx);
|
|
boost::vector_property_map< Weight,
|
|
boost::property_map< CSRGraph, boost::edge_index_t >::const_type >
|
|
edge_weight(eidx);
|
|
|
|
TEST_GRAPH(CSRGraph, sample, g, "node_id", "", vertex_name, vertex_mass,
|
|
edge_weight);
|
|
}
|
|
|
|
void test_subgraphs()
|
|
{
|
|
// on the BGL side, the new parser doesn't support subgraphs
|
|
// however, the docs promise to support reading them on the input side as
|
|
// "syntactic sugar".
|
|
for (auto gv : {
|
|
Fixture { "digraph {}" },
|
|
Fixture { "digraph { 1 -> {} }", 1 },
|
|
Fixture { "digraph { 1 -> {2} }", 2 },
|
|
Fixture { "digraph { 1; { 2; 3; } }", 3 },
|
|
Fixture { "digraph { { 2; 3; } 1; }", 3 },
|
|
Fixture { "digraph { 1; subgraph { 2; 3; } }", 3 },
|
|
Fixture { "digraph { 1 -> subgraph { 2; 3; } }", 3 },
|
|
Fixture { "digraph { 1 -> subgraph hello { 2; 3; } }", 3 },
|
|
Fixture { "digraph { 1 -> subgraph clust_Hello { 2; 3; } }", 3 },
|
|
Fixture { "digraph { 1 -> subgraph \"hello\" { 2; 3; } }", 3 },
|
|
Fixture {
|
|
"digraph { {2} -> subgraph \"hello\" {{{{ 2; 3; }}}} }", 2 },
|
|
})
|
|
{
|
|
TEST_GRAPH(Models::DiGraph, gv);
|
|
}
|
|
}
|
|
|
|
void test_subgraph_nesting_limit() // issue #364
|
|
{
|
|
auto independent_nests = [=](unsigned level)
|
|
{
|
|
auto sg = std::string(level, '{') + " 2; 3; " + std::string(level, '}');
|
|
ComparisonDriver::test_graph< Models::DiGraph >(
|
|
{ "digraph{1->" + sg + "}", 3 });
|
|
ComparisonDriver::test_graph< Models::DiGraph >(
|
|
{ "digraph{1->" + sg + ";4->" + sg + "}", 4 });
|
|
};
|
|
|
|
constexpr unsigned limit = 255;
|
|
independent_nests(1);
|
|
independent_nests(limit / 2);
|
|
independent_nests(limit - 1);
|
|
independent_nests(limit); // edge-case
|
|
BOOST_TEST_THROWS(independent_nests(limit + 1), boost::bad_graphviz_syntax);
|
|
}
|
|
|
|
int main()
|
|
{
|
|
test_basic_directed_graph_1();
|
|
test_basic_directed_graph_2();
|
|
test_basic_directed_graph_3();
|
|
test_undirected_graph_alternate_node_id();
|
|
test_basic_undirected_graph_1();
|
|
test_basic_undirected_graph_2();
|
|
test_mismatch_directed_graph();
|
|
test_mismatch_undirected_graph();
|
|
test_parallel_edges();
|
|
test_graph_property_test_1();
|
|
test_graph_property_test_2();
|
|
test_graph_property_test_3();
|
|
test_comments_embedded_in_strings();
|
|
test_basic_csr_directed_graph_ext_props();
|
|
test_basic_csr_directed_graph();
|
|
test_subgraphs();
|
|
test_subgraph_nesting_limit();
|
|
return boost::report_errors();
|
|
}
|