如何读取包含 boost::read_graphviz 子图的 DOT 文件中给出的图形？
How to read a graph given in a DOT file containing subgraphs with boost::read_graphviz?
我想弄清楚如何使用 boost::read_graphviz 来访问给定点文件中的子图结构。我已经可以使用 boost::read_graphviz 来通过 属性 映射 (boost::dynamic_properties) 读取一些简单的属性。但是，我不知道如何使用 属性 映射来访问子图。如何访问下面给出的图的子图集群？
digraph G {
subgraph cluster_0 {
a0 -> a1;
a1 -> a2;
a2 -> a3;
}
subgraph cluster_1 {
b0 -> b1;
b1 -> b2;
b2 -> b3;
}
c1 -> a0;
c1 -> b0;
a1 -> b3;
b2 -> a3;
a3 -> a0;
a3 -> c2;
b3 -> c2;
}
好的。 确实 read_graphviz 支持已经 dropped somewhere in history:
#if 0
// This interface has not worked for a long time
...
// These four require linking the BGL-Graphviz library: libbgl-viz.a
// from the /src directory.
// Library has not existed for a while
extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
extern void read_graphviz(FILE* file, GraphvizDigraph& g);
extern void read_graphviz(const std::string& file, GraphvizGraph& g);
extern void read_graphviz(FILE* file, GraphvizGraph& g);
#endif
真可惜。
计划
正如我评论的那样，我曾经写过一个非常全面的 graphviz 解析器：。我做了/一些/工作来将生成的 AST 转换为图形模型（不是 BGL，但它可能是）。
但是，对于给定的示例，这似乎是一种过于复杂的方法。
简单的 Graphviz 解析器
让我们为给定的子集推出一个非常简单的 X3 语法：
namespace x3 = boost::spirit::x3;
using Id = std::string;
namespace Parser {
using namespace x3;
auto kw = [](auto... p) {
return lexeme[(x3::as_parser(p) | ...) >> !(alnum | '_')];
};
x3::rule<struct _> graph{"graph"};
auto subgraph = kw("subgraph") >> graph;
auto semi = &('}'|subgraph) | ';';
auto id = lexeme[ //
!kw("edge", "node", "graph", "subgraph") //
>> +char_("A-Za-z0-9_")];
auto edge = id >> *(kw("->") >> id) >> semi;
auto node = id >> semi;
auto element = subgraph | edge | node;
auto graph_def = -id >> '{' >> *element >> '}' >> eps;
auto simple_graphviz = skip(space)[kw("digraph") >> graph];
BOOST_SPIRIT_DEFINE(graph)
} // namespace Parser
这就足够了（甚至不是最小的）。注意
- 它 有智慧对某些关键字进行特殊处理并且
- 并在某些情况下将
';' 视为可选，但
- 它还引入了一个空的根图——我把它留作 reader
的练习
见Live On Wandbox，打印"Parse success"
接线事件
为了构建/anything/，我们应该能够注入解析器事件处理程序。例如：
struct Events{};
struct Handlers {
void node(Id id) { last = id; }
void edge(Id id) { std::cerr << stack.back() << ": " << last << " -> " << id << "\n"; }
void enter(auto optional_id) { stack.push_back(optional_id.value_or("(unnamed)")); }
void leave(unused_type) { stack.pop_back(); }
private:
std::deque<std::string> stack;
Id last{};
};
现在，Events 将用作上下文键：
#define ON(event) ([](auto& ctx) { get<Events>(ctx).event(_attr(ctx)); })
然后我们可以在语义动作中连接事件：
auto edge = id[ON(node)] >> *(kw("->") >> id[ON(edge)]) >> semi;
auto node = id[ON(node)] >> semi;
// ...
auto graph_def = (-id >> '{')[ON(enter)] >> *element >> '}' >> eps[ON(leave)];
在实际调用中我们应该绑定一个实例 Handler:
auto const bound_grammar = //
x3::with<Parser::Events>(Parser::Handlers{})[Parser::simple_graphviz];
try {
if (/*bool ok =*/parse(f, l, bound_grammar))
现在输出是 (Live On Wandbox):
cluster_0: a0 -> a1
cluster_0: a1 -> a2
cluster_0: a2 -> a3
cluster_1: b0 -> b1
cluster_1: b1 -> b2
cluster_1: b2 -> b3
G: c1 -> a0
G: c1 -> b0
G: a1 -> b3
G: b2 -> a3
G: a3 -> a0
G: a3 -> c2
G: b3 -> c2
Parse success
将它们放在一起：构建图表
我们的图形模型不需要太多，但正如我们在较早的答案中发现的那样，write_graphviz 的子图重载确实 强制所有属性映射：
using Attrs = std::map<std::string, std::string>;
using VProp = property<vertex_name_t, std::string,
property<vertex_attribute_t, Attrs>>;
using EProp = property<edge_attribute_t, Attrs, //
property<edge_index_t, int>>;
using GProp = property<graph_graph_attribute_t, Attrs,
property<graph_vertex_attribute_t, Attrs,
property<graph_edge_attribute_t, Attrs,
property<graph_name_t, std::string>>>>;
using Graph = subgraph< //
adjacency_list<vecS, vecS, undirectedS, VProp, EProp, GProp>>;
using Digraph = subgraph< //
adjacency_list<vecS, vecS, directedS, VProp, EProp, GProp>>;
现在我们可以实现 Handlers 接口来构建其中之一：
template <typename G> struct Builder {
using V = typename G::vertex_descriptor;
using E = typename G::edge_descriptor;
Builder(G& g) : g(g) {}
V node(Id id) // return global descriptor to optionally locally added
{
if (auto it = vertices.find(id); it != vertices.end()) {
return last = it->second;
} else {
auto& sub = current();
V vd = add_vertex(sub);
put(boost::vertex_name, sub, vd, id);
// translate to global descriptors for later use
vd = sub.local_to_global(vd);
[[maybe_unused]] auto [_, ok] = vertices.emplace(id, vd);
assert(ok);
return last = vd;
}
}
void edge(Id id) {
V s = last;
V t = node(id); // updates last, sequence point is important!
add_edge(s, t, g);
}
void enter(auto optional_id)
{
auto id = optional_id.value_or("");
if (!hasChild(current(), id))
get_property(current().create_subgraph(), boost::graph_name) = id;
stack.push_back(std::move(id));
}
void leave(x3::unused_type) { stack.pop_back(); }
private:
using Stack = std::deque<std::string>;
G& g;
Stack stack;
std::map<Id, V> vertices;
V last;
static G* hasChild(G& g, Id childId) {
for (auto& child : make_iterator_range(g.children()))
if (childId == get_property(child, boost::graph_name))
return &child;
return nullptr;
}
using F = Stack::const_iterator;
static G& descend(G& g, F f, F l) {
if (f == l)
return g;
if (G* c = hasChild(g, *f))
return descend(*c, ++f, l);
else
throw std::range_error("descend");
}
G& current() {
return descend(g, stack.cbegin(), stack.cend());
}
};
请注意，它可以进行优化，我对多个未命名子图的语义很草率。但是，解析器保持不变，只需将 Builder 绑定到 Events:
BGL::Digraph g;
auto const bound_grammar = //
x3::with<Parser::Events>(BGL::Builder{g})[Parser::simple_graphviz];
if (/*bool ok =*/parse(f, l, bound_grammar))
std::cerr << "Parse success\n";
else
std::cerr << "Parse failed\n";
auto name = get(boost::vertex_name, g);
print_graph(g, name);
write_graphviz(std::cout << "\n ---- GRAPHVIZ:\n", g);
这导致输出 (Live On Wandbox):
Parse success
a0 --> a1
a1 --> a2 b3
a2 --> a3
a3 --> a0 c2
b0 --> b1
b1 --> b2
b2 --> b3 a3
b3 --> c2
c1 --> a0 b0
c2 -->
---- GRAPHVIZ:
digraph "" {
subgraph G {
subgraph cluster_0 {
0;
1;
2;
3;
0 -> 1;
1 -> 2;
2 -> 3;
3 -> 0;
}
subgraph cluster_1 {
4;
5;
6;
7;
4 -> 5;
5 -> 6;
6 -> 7;
}
8;
9;
1 -> 7;
3 -> 9;
6 -> 3;
7 -> 9;
8 -> 0;
8 -> 4;
}
}
锦上添花
所以现在我们有 structure-preserving，而不是 id-preserving。我们至少可以确保 id 被用作节点标签然后：
auto name = get(boost::vertex_name, g);
auto attrs = get(boost::vertex_attribute, g);
for (auto v : make_iterator_range(vertices(g))) {
attrs[v]["label"] = name[v];
}
write_graphviz(std::cout, g);
现在打印：
digraph "" {
subgraph G {
subgraph cluster_0 {
0[label=a0];
1[label=a1];
2[label=a2];
3[label=a3];
0 -> 1;
1 -> 2;
2 -> 3;
3 -> 0;
}
subgraph cluster_1 {
4[label=b0];
5[label=b1];
6[label=b2];
7[label=b3];
4 -> 5;
5 -> 6;
6 -> 7;
}
8[label=c1];
9[label=c2];
1 -> 7;
3 -> 9;
6 -> 3;
7 -> 9;
8 -> 0;
8 -> 4;
}
}
完整列表
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/subgraph.hpp>
#include <boost/spirit/home/x3.hpp>
namespace x3 = boost::spirit::x3;
using boost::make_iterator_range;
using Id = std::string;
namespace BGL {
using namespace boost;
using Attrs = std::map<std::string, std::string>;
using VProp = property<vertex_name_t, std::string,
property<vertex_attribute_t, Attrs>>;
using EProp = property<edge_attribute_t, Attrs, //
property<edge_index_t, int>>;
using GProp = property<graph_graph_attribute_t, Attrs,
property<graph_vertex_attribute_t, Attrs,
property<graph_edge_attribute_t, Attrs,
property<graph_name_t, std::string>>>>;
using Graph = subgraph< //
adjacency_list<vecS, vecS, undirectedS, VProp, EProp, GProp>>;
using Digraph = subgraph< //
adjacency_list<vecS, vecS, directedS, VProp, EProp, GProp>>;
template <typename G> struct Builder {
using V = typename G::vertex_descriptor;
using E = typename G::edge_descriptor;
Builder(G& g) : g(g) {}
V node(Id id) // return global descriptor to optionally locally added
{
if (auto it = vertices.find(id); it != vertices.end()) {
return last = it->second;
} else {
auto& sub = current();
V vd = add_vertex(sub);
put(boost::vertex_name, sub, vd, id);
// translate to global descriptors for later use
vd = sub.local_to_global(vd);
[[maybe_unused]] auto [_, ok] = vertices.emplace(id, vd);
assert(ok);
return last = vd;
}
}
void edge(Id id) {
V s = last;
V t = node(id); // updates last, sequence point is important!
add_edge(s, t, g);
}
void enter(auto optional_id)
{
auto id = optional_id.value_or("");
if (!hasChild(current(), id))
get_property(current().create_subgraph(), boost::graph_name) = id;
stack.push_back(std::move(id));
}
void leave(x3::unused_type) { stack.pop_back(); }
private:
using Stack = std::deque<std::string>;
G& g;
Stack stack;
std::map<Id, V> vertices;
V last;
static G* hasChild(G& g, Id childId) {
for (auto& child : make_iterator_range(g.children()))
if (childId == get_property(child, boost::graph_name))
return &child;
return nullptr;
}
using F = Stack::const_iterator;
static G& descend(G& g, F f, F l) {
if (f == l)
return g;
if (G* c = hasChild(g, *f))
return descend(*c, ++f, l);
else
throw std::range_error("descend");
}
G& current() {
return descend(g, stack.cbegin(), stack.cend());
}
};
} // namespace BGL
namespace Parser {
using namespace x3;
auto kw = [](auto... p) {
return lexeme[(x3::as_parser(p) | ...) >> !(alnum | '_')];
};
struct Events{};
#define ON(event) ([](auto& ctx) { get<Events>(ctx).event(_attr(ctx)); })
x3::rule<struct _> graph{"graph"};
auto subgraph = kw("subgraph") >> graph;
auto semi = &('}'|subgraph) | ';';
auto id = lexeme[ //
!kw("edge", "node", "graph", "subgraph") //
>> +char_("A-Za-z0-9_")];
auto edge = id[ON(node)] >> *(kw("->") >> id[ON(edge)]) >> semi;
auto node = id[ON(node)] >> semi;
auto element = subgraph | edge | node;
auto graph_def = (-id >> '{')[ON(enter)] >> *element >> '}' >> eps[ON(leave)];
auto simple_graphviz = skip(space)[kw("digraph") >> graph];
BOOST_SPIRIT_DEFINE(graph)
#undef ON
} // namespace Parser
int main() {
std::ifstream ifs("input.txt");
std::string const s(std::istreambuf_iterator<char>(ifs >> std::noskipws), {});
auto f = s.begin(), l = s.end();
BGL::Digraph g;
auto const bound_grammar = //
x3::with<Parser::Events>(BGL::Builder{g})[Parser::simple_graphviz];
try {
if (/*bool ok =*/parse(f, l, bound_grammar))
std::cerr << "Parse success\n";
else
std::cerr << "Parse failed\n";
auto name = get(boost::vertex_name, g);
auto attrs = get(boost::vertex_attribute, g);
for (auto v : make_iterator_range(vertices(g))) {
attrs[v]["label"] = name[v];
}
write_graphviz(std::cout, g);
if (f != l)
std::cerr << "Remaining unparsed input: '" << std::string(f,l) << "'\n";
} catch (x3::expectation_failure<std::string::const_iterator> const& e) {
std::cerr << e.what() << ": " << e.which() << " at "
<< std::string(e.where(), l) << "\n";
}
}
结果图 renders:
我想弄清楚如何使用 boost::read_graphviz 来访问给定点文件中的子图结构。我已经可以使用 boost::read_graphviz 来通过 属性 映射 (boost::dynamic_properties) 读取一些简单的属性。但是，我不知道如何使用 属性 映射来访问子图。如何访问下面给出的图的子图集群？
digraph G {
subgraph cluster_0 {
a0 -> a1;
a1 -> a2;
a2 -> a3;
}
subgraph cluster_1 {
b0 -> b1;
b1 -> b2;
b2 -> b3;
}
c1 -> a0;
c1 -> b0;
a1 -> b3;
b2 -> a3;
a3 -> a0;
a3 -> c2;
b3 -> c2;
}
好的。 确实 read_graphviz 支持已经 dropped somewhere in history:
#if 0
// This interface has not worked for a long time
...
// These four require linking the BGL-Graphviz library: libbgl-viz.a
// from the /src directory.
// Library has not existed for a while
extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
extern void read_graphviz(FILE* file, GraphvizDigraph& g);
extern void read_graphviz(const std::string& file, GraphvizGraph& g);
extern void read_graphviz(FILE* file, GraphvizGraph& g);
#endif
真可惜。
计划
正如我评论的那样，我曾经写过一个非常全面的 graphviz 解析器：
但是，对于给定的示例，这似乎是一种过于复杂的方法。
简单的 Graphviz 解析器
让我们为给定的子集推出一个非常简单的 X3 语法：
namespace x3 = boost::spirit::x3;
using Id = std::string;
namespace Parser {
using namespace x3;
auto kw = [](auto... p) {
return lexeme[(x3::as_parser(p) | ...) >> !(alnum | '_')];
};
x3::rule<struct _> graph{"graph"};
auto subgraph = kw("subgraph") >> graph;
auto semi = &('}'|subgraph) | ';';
auto id = lexeme[ //
!kw("edge", "node", "graph", "subgraph") //
>> +char_("A-Za-z0-9_")];
auto edge = id >> *(kw("->") >> id) >> semi;
auto node = id >> semi;
auto element = subgraph | edge | node;
auto graph_def = -id >> '{' >> *element >> '}' >> eps;
auto simple_graphviz = skip(space)[kw("digraph") >> graph];
BOOST_SPIRIT_DEFINE(graph)
} // namespace Parser
这就足够了（甚至不是最小的）。注意
- 它 有智慧对某些关键字进行特殊处理并且
- 并在某些情况下将
';'视为可选，但 - 它还引入了一个空的根图——我把它留作 reader 的练习
见Live On Wandbox，打印"Parse success"
接线事件
为了构建/anything/，我们应该能够注入解析器事件处理程序。例如：
struct Events{};
struct Handlers {
void node(Id id) { last = id; }
void edge(Id id) { std::cerr << stack.back() << ": " << last << " -> " << id << "\n"; }
void enter(auto optional_id) { stack.push_back(optional_id.value_or("(unnamed)")); }
void leave(unused_type) { stack.pop_back(); }
private:
std::deque<std::string> stack;
Id last{};
};
现在，Events 将用作上下文键：
#define ON(event) ([](auto& ctx) { get<Events>(ctx).event(_attr(ctx)); })
然后我们可以在语义动作中连接事件：
auto edge = id[ON(node)] >> *(kw("->") >> id[ON(edge)]) >> semi;
auto node = id[ON(node)] >> semi;
// ...
auto graph_def = (-id >> '{')[ON(enter)] >> *element >> '}' >> eps[ON(leave)];
在实际调用中我们应该绑定一个实例 Handler:
auto const bound_grammar = //
x3::with<Parser::Events>(Parser::Handlers{})[Parser::simple_graphviz];
try {
if (/*bool ok =*/parse(f, l, bound_grammar))
现在输出是 (Live On Wandbox):
cluster_0: a0 -> a1
cluster_0: a1 -> a2
cluster_0: a2 -> a3
cluster_1: b0 -> b1
cluster_1: b1 -> b2
cluster_1: b2 -> b3
G: c1 -> a0
G: c1 -> b0
G: a1 -> b3
G: b2 -> a3
G: a3 -> a0
G: a3 -> c2
G: b3 -> c2
Parse success
将它们放在一起：构建图表
我们的图形模型不需要太多，但正如我们在较早的答案中发现的那样，write_graphviz 的子图重载确实 强制所有属性映射：
using Attrs = std::map<std::string, std::string>;
using VProp = property<vertex_name_t, std::string,
property<vertex_attribute_t, Attrs>>;
using EProp = property<edge_attribute_t, Attrs, //
property<edge_index_t, int>>;
using GProp = property<graph_graph_attribute_t, Attrs,
property<graph_vertex_attribute_t, Attrs,
property<graph_edge_attribute_t, Attrs,
property<graph_name_t, std::string>>>>;
using Graph = subgraph< //
adjacency_list<vecS, vecS, undirectedS, VProp, EProp, GProp>>;
using Digraph = subgraph< //
adjacency_list<vecS, vecS, directedS, VProp, EProp, GProp>>;
现在我们可以实现 Handlers 接口来构建其中之一：
template <typename G> struct Builder {
using V = typename G::vertex_descriptor;
using E = typename G::edge_descriptor;
Builder(G& g) : g(g) {}
V node(Id id) // return global descriptor to optionally locally added
{
if (auto it = vertices.find(id); it != vertices.end()) {
return last = it->second;
} else {
auto& sub = current();
V vd = add_vertex(sub);
put(boost::vertex_name, sub, vd, id);
// translate to global descriptors for later use
vd = sub.local_to_global(vd);
[[maybe_unused]] auto [_, ok] = vertices.emplace(id, vd);
assert(ok);
return last = vd;
}
}
void edge(Id id) {
V s = last;
V t = node(id); // updates last, sequence point is important!
add_edge(s, t, g);
}
void enter(auto optional_id)
{
auto id = optional_id.value_or("");
if (!hasChild(current(), id))
get_property(current().create_subgraph(), boost::graph_name) = id;
stack.push_back(std::move(id));
}
void leave(x3::unused_type) { stack.pop_back(); }
private:
using Stack = std::deque<std::string>;
G& g;
Stack stack;
std::map<Id, V> vertices;
V last;
static G* hasChild(G& g, Id childId) {
for (auto& child : make_iterator_range(g.children()))
if (childId == get_property(child, boost::graph_name))
return &child;
return nullptr;
}
using F = Stack::const_iterator;
static G& descend(G& g, F f, F l) {
if (f == l)
return g;
if (G* c = hasChild(g, *f))
return descend(*c, ++f, l);
else
throw std::range_error("descend");
}
G& current() {
return descend(g, stack.cbegin(), stack.cend());
}
};
请注意，它可以进行优化，我对多个未命名子图的语义很草率。但是，解析器保持不变，只需将 Builder 绑定到 Events:
BGL::Digraph g;
auto const bound_grammar = //
x3::with<Parser::Events>(BGL::Builder{g})[Parser::simple_graphviz];
if (/*bool ok =*/parse(f, l, bound_grammar))
std::cerr << "Parse success\n";
else
std::cerr << "Parse failed\n";
auto name = get(boost::vertex_name, g);
print_graph(g, name);
write_graphviz(std::cout << "\n ---- GRAPHVIZ:\n", g);
这导致输出 (Live On Wandbox):
Parse success
a0 --> a1
a1 --> a2 b3
a2 --> a3
a3 --> a0 c2
b0 --> b1
b1 --> b2
b2 --> b3 a3
b3 --> c2
c1 --> a0 b0
c2 -->
---- GRAPHVIZ:
digraph "" {
subgraph G {
subgraph cluster_0 {
0;
1;
2;
3;
0 -> 1;
1 -> 2;
2 -> 3;
3 -> 0;
}
subgraph cluster_1 {
4;
5;
6;
7;
4 -> 5;
5 -> 6;
6 -> 7;
}
8;
9;
1 -> 7;
3 -> 9;
6 -> 3;
7 -> 9;
8 -> 0;
8 -> 4;
}
}
锦上添花
所以现在我们有 structure-preserving，而不是 id-preserving。我们至少可以确保 id 被用作节点标签然后：
auto name = get(boost::vertex_name, g);
auto attrs = get(boost::vertex_attribute, g);
for (auto v : make_iterator_range(vertices(g))) {
attrs[v]["label"] = name[v];
}
write_graphviz(std::cout, g);
现在打印：
digraph "" {
subgraph G {
subgraph cluster_0 {
0[label=a0];
1[label=a1];
2[label=a2];
3[label=a3];
0 -> 1;
1 -> 2;
2 -> 3;
3 -> 0;
}
subgraph cluster_1 {
4[label=b0];
5[label=b1];
6[label=b2];
7[label=b3];
4 -> 5;
5 -> 6;
6 -> 7;
}
8[label=c1];
9[label=c2];
1 -> 7;
3 -> 9;
6 -> 3;
7 -> 9;
8 -> 0;
8 -> 4;
}
}
完整列表
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/subgraph.hpp>
#include <boost/spirit/home/x3.hpp>
namespace x3 = boost::spirit::x3;
using boost::make_iterator_range;
using Id = std::string;
namespace BGL {
using namespace boost;
using Attrs = std::map<std::string, std::string>;
using VProp = property<vertex_name_t, std::string,
property<vertex_attribute_t, Attrs>>;
using EProp = property<edge_attribute_t, Attrs, //
property<edge_index_t, int>>;
using GProp = property<graph_graph_attribute_t, Attrs,
property<graph_vertex_attribute_t, Attrs,
property<graph_edge_attribute_t, Attrs,
property<graph_name_t, std::string>>>>;
using Graph = subgraph< //
adjacency_list<vecS, vecS, undirectedS, VProp, EProp, GProp>>;
using Digraph = subgraph< //
adjacency_list<vecS, vecS, directedS, VProp, EProp, GProp>>;
template <typename G> struct Builder {
using V = typename G::vertex_descriptor;
using E = typename G::edge_descriptor;
Builder(G& g) : g(g) {}
V node(Id id) // return global descriptor to optionally locally added
{
if (auto it = vertices.find(id); it != vertices.end()) {
return last = it->second;
} else {
auto& sub = current();
V vd = add_vertex(sub);
put(boost::vertex_name, sub, vd, id);
// translate to global descriptors for later use
vd = sub.local_to_global(vd);
[[maybe_unused]] auto [_, ok] = vertices.emplace(id, vd);
assert(ok);
return last = vd;
}
}
void edge(Id id) {
V s = last;
V t = node(id); // updates last, sequence point is important!
add_edge(s, t, g);
}
void enter(auto optional_id)
{
auto id = optional_id.value_or("");
if (!hasChild(current(), id))
get_property(current().create_subgraph(), boost::graph_name) = id;
stack.push_back(std::move(id));
}
void leave(x3::unused_type) { stack.pop_back(); }
private:
using Stack = std::deque<std::string>;
G& g;
Stack stack;
std::map<Id, V> vertices;
V last;
static G* hasChild(G& g, Id childId) {
for (auto& child : make_iterator_range(g.children()))
if (childId == get_property(child, boost::graph_name))
return &child;
return nullptr;
}
using F = Stack::const_iterator;
static G& descend(G& g, F f, F l) {
if (f == l)
return g;
if (G* c = hasChild(g, *f))
return descend(*c, ++f, l);
else
throw std::range_error("descend");
}
G& current() {
return descend(g, stack.cbegin(), stack.cend());
}
};
} // namespace BGL
namespace Parser {
using namespace x3;
auto kw = [](auto... p) {
return lexeme[(x3::as_parser(p) | ...) >> !(alnum | '_')];
};
struct Events{};
#define ON(event) ([](auto& ctx) { get<Events>(ctx).event(_attr(ctx)); })
x3::rule<struct _> graph{"graph"};
auto subgraph = kw("subgraph") >> graph;
auto semi = &('}'|subgraph) | ';';
auto id = lexeme[ //
!kw("edge", "node", "graph", "subgraph") //
>> +char_("A-Za-z0-9_")];
auto edge = id[ON(node)] >> *(kw("->") >> id[ON(edge)]) >> semi;
auto node = id[ON(node)] >> semi;
auto element = subgraph | edge | node;
auto graph_def = (-id >> '{')[ON(enter)] >> *element >> '}' >> eps[ON(leave)];
auto simple_graphviz = skip(space)[kw("digraph") >> graph];
BOOST_SPIRIT_DEFINE(graph)
#undef ON
} // namespace Parser
int main() {
std::ifstream ifs("input.txt");
std::string const s(std::istreambuf_iterator<char>(ifs >> std::noskipws), {});
auto f = s.begin(), l = s.end();
BGL::Digraph g;
auto const bound_grammar = //
x3::with<Parser::Events>(BGL::Builder{g})[Parser::simple_graphviz];
try {
if (/*bool ok =*/parse(f, l, bound_grammar))
std::cerr << "Parse success\n";
else
std::cerr << "Parse failed\n";
auto name = get(boost::vertex_name, g);
auto attrs = get(boost::vertex_attribute, g);
for (auto v : make_iterator_range(vertices(g))) {
attrs[v]["label"] = name[v];
}
write_graphviz(std::cout, g);
if (f != l)
std::cerr << "Remaining unparsed input: '" << std::string(f,l) << "'\n";
} catch (x3::expectation_failure<std::string::const_iterator> const& e) {
std::cerr << e.what() << ": " << e.which() << " at "
<< std::string(e.where(), l) << "\n";
}
}
结果图 renders: