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));
}
生成左边的图表,而我得到的是右边的图表:
输出为:
digraph G0 {
subgraph clusterG1 {
subgraph clusterG2 {
//B;
}
//A;
}
A -> B;
}
注释的节点语句是层次结构信息丢失的地方(我的输出中没有这些行)。我怎样才能避免这种情况?
如果我将两个顶点添加到同一个子图中:
add_vertex(A, sub1);
add_vertex(B, sub1);
add_edge(A, B, main);
连接 A -> B
出现在 clusterG1
的范围内,根据我的理解,这也是隐式声明提到的顶点的地方。
我正在使用 Boost 1.68.0
问题是由 make_iterator_vertex_map(names)
提供的 names
char
引起的 names
('A'
, 'B'
)。这与预期的(和默认的)vertex_index
属性(0
、1
)不兼容。修复后,我得到:
digraph G0 {
subgraph clusterG1 {
subgraph clusterG2 {
1;
}
0;
}
0 -> 1;
}
vertex_marker
,在我的例子中是 2
个元素中的 std::vector<bool>
个,而不是 67
并且更多的元素被顶点索引索引。我遇到了未定义的行为,
并且 if ( vertex_marker[pos] )
从未实现。
boost::detail::write_graphviz_subgraph
的负责部分:
// Print out vertices and edges not in the subgraphs.
typename graph_traits<Graph>::vertex_iterator i, end;
typename graph_traits<Graph>::edge_iterator ei, edge_end;
for(boost::tie(i,end) = vertices(g); i != end; ++i) {
Vertex v = g.local_to_global(*i);
int pos = get(vertex_id, v); // 66, 65, should be 1, 0
if ( vertex_marker[pos] ) { // out-of-bounds access
vertex_marker[pos] = false;
out << escape_dot_string(pos);
make_vertex_attributes_writer(g.root())(out, v);
out << ";" << std::endl;
}
}
vertex_id
参数类型的 static_assert
/SFINAE 针对 Graph
的 vertex_id
类型(可以在 boost::write_graphviz
中立即完成)不胜欢迎。附带一提,硬编码的 int pos = ...
看起来不太专业......
如果我们想保留自定义名称,我们必须通过 label
属性来提供它们。
好地方。 实际上有 UB,正如您自己的回答所解释的那样。传递给 write_graphviz
函数的地图实际上不应该具有用于 graphviz 输出的 node_id。相反,该地图被假定为 vertex_index_t
属性map.
这是我可能从 boost::print_graph
(graph_utility.hpp) 得出的一个假设,即 确实 这样的 属性-map.
为了使其安全工作,我将修改示例以使用 write_graphviz_dp
- 使用动态属性:
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" 等:
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
地图以使其具有预期的顶点标签:
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);
}
我期待代码
#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));
}
生成左边的图表,而我得到的是右边的图表:
输出为:
digraph G0 {
subgraph clusterG1 {
subgraph clusterG2 {
//B;
}
//A;
}
A -> B;
}
注释的节点语句是层次结构信息丢失的地方(我的输出中没有这些行)。我怎样才能避免这种情况?
如果我将两个顶点添加到同一个子图中:
add_vertex(A, sub1);
add_vertex(B, sub1);
add_edge(A, B, main);
连接 A -> B
出现在 clusterG1
的范围内,根据我的理解,这也是隐式声明提到的顶点的地方。
我正在使用 Boost 1.68.0
问题是由 make_iterator_vertex_map(names)
提供的 names
char
引起的 names
('A'
, 'B'
)。这与预期的(和默认的)vertex_index
属性(0
、1
)不兼容。修复后,我得到:
digraph G0 {
subgraph clusterG1 {
subgraph clusterG2 {
1;
}
0;
}
0 -> 1;
}
vertex_marker
,在我的例子中是 2
个元素中的 std::vector<bool>
个,而不是 67
并且更多的元素被顶点索引索引。我遇到了未定义的行为,
并且 if ( vertex_marker[pos] )
从未实现。
boost::detail::write_graphviz_subgraph
的负责部分:
// Print out vertices and edges not in the subgraphs.
typename graph_traits<Graph>::vertex_iterator i, end;
typename graph_traits<Graph>::edge_iterator ei, edge_end;
for(boost::tie(i,end) = vertices(g); i != end; ++i) {
Vertex v = g.local_to_global(*i);
int pos = get(vertex_id, v); // 66, 65, should be 1, 0
if ( vertex_marker[pos] ) { // out-of-bounds access
vertex_marker[pos] = false;
out << escape_dot_string(pos);
make_vertex_attributes_writer(g.root())(out, v);
out << ";" << std::endl;
}
}
vertex_id
参数类型的 static_assert
/SFINAE 针对 Graph
的 vertex_id
类型(可以在 boost::write_graphviz
中立即完成)不胜欢迎。附带一提,硬编码的 int pos = ...
看起来不太专业......
如果我们想保留自定义名称,我们必须通过 label
属性来提供它们。
好地方。 write_graphviz
函数的地图实际上不应该具有用于 graphviz 输出的 node_id。相反,该地图被假定为 vertex_index_t
属性map.
这是我可能从 boost::print_graph
(graph_utility.hpp) 得出的一个假设,即 确实 这样的 属性-map.
为了使其安全工作,我将修改示例以使用 write_graphviz_dp
- 使用动态属性:
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" 等:
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
地图以使其具有预期的顶点标签:
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);
}