Boost.Graph和Graphviz嵌套子图 [英] Boost.Graph and Graphviz nested subgraphs
问题描述
我希望输入代码
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>
#include <iostream>
using namespace boost;
using attrs_t = std::map<std::string, std::string>;
using graph_t = adjacency_list<
vecS, vecS, directedS,
property<vertex_attribute_t, attrs_t>,
property<edge_index_t, int, property<edge_attribute_t, attrs_t>>,
property<graph_name_t, std::string,
property<graph_graph_attribute_t, attrs_t,
property<graph_vertex_attribute_t, attrs_t,
property<graph_edge_attribute_t, attrs_t>>>>>;
int main()
{
char names[] = {"AB"};
enum {A, B, N};
subgraph<graph_t> main(N);
subgraph<graph_t>& sub1 = main.create_subgraph();
subgraph<graph_t>& sub2 = sub1.create_subgraph();
add_vertex(A, sub1);
add_vertex(B, sub2);
add_edge(A, B, main);
get_property(main, graph_name) = "G0";
get_property(sub1, graph_name) = "clusterG1";
get_property(sub2, graph_name) = "clusterG2";
write_graphviz(std::cout, main, make_iterator_vertex_map(names));
}
生成左侧的图形，而我得到右侧的图形:
to generate the graph on the left, whereas I have got the right one:
输出为:
digraph G0 {
subgraph clusterG1 {
subgraph clusterG2 {
//B;
}
//A;
}
A -> B;
}
注释的节点语句是丢失层次结构信息的地方(这些行在我的输出中没有).我该如何避免呢?
The commented node statements are where the hierarchy information is lost (these lines I do not have in my output). How can I avoid that?
如果我将两个顶点都添加到同一子图中:
If I add both vertices into the same subgraph:
add_vertex(A, sub1);
add_vertex(B, sub1);
add_edge(A, B, main);
根据我的理解，连接A -> B出现在clusterG1的范围内，在该处也将隐式声明所提到的顶点.
the connection A -> B appears in the scope of clusterG1 and from how I understand it, that is where the mentioned vertices will also be implicitly declared.
我正在使用Boost 1.68.0
I am using Boost 1.68.0
推荐答案
好地方.正如您自己的答案所解释的，链接的答案实际上具有UB.传递给write_graphviz函数的映射实际上不应该具有graphviz输出的node_id.相反，该映射被假定为vertex_index_t属性映射.
Good spot. The linked answer actually has UB, as your own answer explains. The map passed in to the write_graphviz function isn't actually supposed to have the node_id for the graphviz output. Instead, that map was assumed to be a vertex_index_t propertymap.
这是我可能从boost::print_graph(graph_utility.hpp)得出的一个假设，即确实具有这样的属性映射.
That was an assumption I probably held from boost::print_graph (graph_utility.hpp) that does that such property-map.
为了使其安全运行，我将修改示例以使用write_graphviz_dp-使用动态属性:
To make it work safely I'd modify the example to employ write_graphviz_dp - using dynamic properties:
int main() {
boost::dynamic_properties dp;
dp.property("node_id", boost::make_transform_value_property_map<std::string>(&name_for_index, boost::identity_property_map{}));
write_graphviz_dp(std::cout, create_data<subgraph<Graph> >(), dp);
}
我选择使用转换函数来获取任何顶点描述符的名称，也不想再假设任何关于顶点数目的东西，我编写了更通用的函数来生成诸如"A"的名称，...， "Z"，"AA"，...，"ZZ"等:
I opted to use a transform function to get a name for any vertex descriptor, not wanting to assume anything about the number of vertices anymore either, I wrote the more general function to generate names like "A",...,"Z","AA",...,"ZZ" etc.:
static std::string name_for_index(intmax_t index) {
std::string name;
do {
name += 'A' + (index%26);
index /= 26;
} while (index);
return name;
}
上述重载不支持子图.因此，让我们修复vertex_attribute贴图以具有预期的顶点标签:
The above overload doesn't have the subgraph support. So, instead let's fix the vertex_attribute map to have the expected vertex labels:
int main() {
auto g = create_data<subgraph<Graph> >();
for (auto vd : make_iterator_range(vertices(g))) {
put(get(vertex_attribute, g), vd,
GraphvizAttributes{
{"label", name_for_index(vd)}
});
}
write_graphviz(std::cout, g);
}
现在它可以打印:
digraph G0 {
subgraph clusterG1 {
graph [
label=G1];
node [
color=red, shape=Mrecord];
0[label="Vertex A"];
1[label="Vertex B"];
0 -> 1;
}
subgraph clusterG2 {
graph [
fillcolor=lightgray, label=G2, style=filled];
node [
shape=circle];
4[label="Vertex E"];
2[label="Vertex C"];
5[label="Vertex F"];
4 -> 5;
2 -> 5;
}
3[label="Vertex D"];
1 -> 2;
1 -> 3;
4 -> 1;
5 -> 3;
}
哪个呈现为
保留后代
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>
#include <iostream>
using namespace boost;
template <typename SubGraph> SubGraph create_data()
{
enum { A,B,C,D,E,F,N }; // main edges
SubGraph main(N);
SubGraph& sub1 = main.create_subgraph();
SubGraph& sub2 = main.create_subgraph();
auto A1 = add_vertex(A, sub1);
auto B1 = add_vertex(B, sub1);
auto E2 = add_vertex(E, sub2);
auto C2 = add_vertex(C, sub2);
auto F2 = add_vertex(F, sub2);
add_edge(A1, B1, sub1);
add_edge(E2, F2, sub2);
add_edge(C2, F2, sub2);
add_edge(E, B, main);
add_edge(B, C, main);
add_edge(B, D, main);
add_edge(F, D, main);
// setting some graph viz attributes
get_property(main, graph_name) = "G0";
get_property(sub1, graph_name) = "clusterG1";
get_property(sub2, graph_name) = "clusterG2";
get_property(sub1, graph_graph_attribute)["label"] = "G1";
/*extra*/get_property(sub1, graph_vertex_attribute)["shape"] = "Mrecord";
get_property(sub2, graph_graph_attribute)["label"] = "G2";
/*extra*/get_property(sub1, graph_vertex_attribute)["color"] = "red";
/*extra*/get_property(sub2, graph_graph_attribute)["fillcolor"] = "lightgray";
/*extra*/get_property(sub2, graph_graph_attribute)["style"] = "filled";
/*extra*/get_property(sub2, graph_vertex_attribute)["shape"] = "circle";
return main;
}
using GraphvizAttributes =
std::map<std::string, std::string>;
using Graph =
adjacency_list<vecS, vecS, directedS,
property<vertex_attribute_t, GraphvizAttributes>,
property<edge_index_t, int, property<edge_attribute_t, GraphvizAttributes> >,
property<graph_name_t, std::string,
property<graph_graph_attribute_t, GraphvizAttributes,
property<graph_vertex_attribute_t, GraphvizAttributes,
property<graph_edge_attribute_t, GraphvizAttributes>
> > >
>;
static std::string name_for_index(intmax_t index) {
std::string name = "Vertex ";
do {
name += 'A' + (index%26);
index /= 26;
} while (index);
return name;
}
int main() {
auto g = create_data<subgraph<Graph> >();
for (auto vd : make_iterator_range(vertices(g))) {
put(get(vertex_attribute, g), vd,
GraphvizAttributes{
{"label", name_for_index(vd)}
});
}
write_graphviz(std::cout, g);
}
这篇关于Boost.Graph和Graphviz嵌套子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
