logo标签列表

如何使用boost::write_graphviz编写GraphViz子图

c++boostgraphvizdotboost-graph
7

可以使用::boost::write_graphviz生成DOT子图吗？

例如，如果我在图形G中创建了一个子图G0，是否可以在DOT输出中获得以下内容：

graph G {
  subgraph G0 {
    ...
  }
  ...
}
在BGL中，您如何“将子图添加到图形”？ - sehe
@sehe 用 create_subgraph 创建子图？ - Mitchell Slep
我的意思是，也许您可以用一个简单的自包含示例来荣幸我们？我已经花了45分钟以上来尝试解决这个问题。令人沮丧的是，我不断地必须考虑到我可能在错误/不同的方式中使用子图的可能性。没有具体上下文和“这就是我卡住的地方”的问题通常太宽泛了。（问这个问题并不愚蠢，记录一下。即使我有一些经验（甚至可能相当丰富），我碰巧没有使用过子图。） - sehe
我之前确实不理解子图。但现在我懂了 :/ 请看我的回答。 - sehe
1个回答
20

我终于弄清了子图是如何工作的，以及如何使用boost::write_graphviz来打印这些子图。

第一个要求在boost库源代码的注释中“半文档化”地说明：requires graph_name property。

然而，最令人惊讶的要求似乎是detail::write_graphviz_subgraph假定存在以下属性:

  • vertex_attribute
  • edge_attribute
  • graph_vertex_attribute、graph_edge_attribute、graph_graph_attribute图形属性

我认为这些要求可能相当严格，因为您的图类型至少看起来像这样：

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>
      > > >
    >;

无论如何，演示如何向Graphviz提供边/节点/(子)图属性当然很好:

在Coliru上实时演示

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;
}

这里输入图片描述

那就是这个样子：

int main() {
#ifdef GENERATE_RANDOM_GRAPHS
    auto g = generate_random<subgraph<Graph> >();
#else
    auto g = create_data<subgraph<Graph> >();
#endif

    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);
}

我还为了自己的测试和理解，实现了generate_random函数。它生成类似下面的图表：

enter image description here

完整程序

在 Coliru 上实时运行

#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>
#include <iostream>

using namespace boost;

//#define GENERATE_RANDOM_GRAPHS
#ifdef GENERATE_RANDOM_GRAPHS
#include <boost/graph/random.hpp> // in case you comment out the random graph creation code
#include <random>

template <typename SubGraph> SubGraph generate_random()
{
    std::mt19937 prng(std::random_device{}());
    SubGraph randomized(uniform_int<int>(10,20)(prng));

    auto subs = uniform_int<int>(1,5)(prng);
    while (subs--) randomized.create_subgraph();
    subs = boost::size(randomized.children());

    int offset = 0;
    for (auto& sub : make_iterator_range(randomized.children()))
    {
        for (size_t i = offset; i < num_vertices(randomized); i += subs) 
            add_vertex(i, sub);
        ++offset;
    }

    auto random_edges = [&](SubGraph& g) {
        uniform_int<typename SubGraph::vertex_descriptor> v(0, num_vertices(g) -1);
        for (size_t i = 1; i < 4; ++i)
            add_edge(v(prng), v(prng), g);
    };

    for (auto& sub : make_iterator_range(randomized.children()))
        random_edges(sub);
    random_edges(randomized);

    // setting some graph viz attributes
    get_property(randomized, graph_name) = "G0";

    offset = 0;
    for (auto& sub : make_iterator_range(randomized.children())) {
        ++offset;
        get_property(sub, graph_name) = "cluster" + std::to_string(offset);
        get_property(sub, graph_graph_attribute)["label"]    = "G" + std::to_string(offset);
    }

    return randomized;
}
#else

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;
}
#endif

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;

    do {
        name += 'A' + (index%26);
        index /= 26;
    } while (index);

    return name;
}

int main() {
#ifdef GENERATE_RANDOM_GRAPHS
    auto g = generate_random<subgraph<Graph> >();
#else
    auto g = create_data<subgraph<Graph> >();
#endif

    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);
}
我认为我们不能像你定义的那样使用make_iterator_vertex_map(names)和subgraph<Graph>，至少在1.68.0版本中不行。请参见https://stackoverflow.com/q/54599136。 - LogicStuff
1
@LogicStuff 很好的发现。UBSan/ASan 也认同。在相关问题中，我解释了我的错误假设来源（不幸的是，它“看起来”是正确的）。我已经修正了这个答案。祝好！ - sehe
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接