Boost::Graph 中的 read_graphviz()，传递给构造函数

2021-12-24 00:00:00 graph c++ boost

我使用了一个 python 库来生成以下 GraphViz .dot 文件.

http://pastebin.com/mL7ck9Zp

我现在想将其读入 C++ 的 Boost::Graph，以便我可以在其上使用 Boost::Graph 的库算法.

但是，我需要做一些预处理.特别是，我想创建一个带有字符串构造函数的捆绑属性，并让 read_graphviz() 将点文件中标签字段中的字符串传递给字符串构造函数.

我该怎么做?

解决方案

首先要意识到 Boost 文档样本几乎总是参考/从实际样本生成:libs/graph/example/read_graphviz.cpp

要意识到的第二件事是 BGL 是高度通用的.高度.它在 Boost Property 的概念上实现了大部分这种通用性地图.

最后，观察从自由格式"(至少是动态/无类型文本格式)解析为某种通用MutableGraph 模型正在突破极限.

这解释了您必须如何阅读property_map 的文档.

无论如何，因为确实样本似乎有点过时了，请允许我演示一下:

将解析器的实现包含在一个翻译单元中:
```
#include 
```
这样 BGL 仍然是一个只有头文件的库.

现在更喜欢捆绑属性:

struct Vertex {std::string 名称、标签、形状；};结构边{std::string 标签；双倍重量；//也许你以后也需要这个，只是一个例子};typedef 属性图_p;typedef adjacency_list图_t;

我们将为顶点和边填充label、shape、name.

动态属性映射是神奇发生的地方:

dynamic_properties dp/*(ignore_other_properties)*/;

该类提供对各种底层属性映射由(name, typeid(key_type))标识.

这意味着您可以注册捆绑的属性，并将它们映射到 graphviz 属性名称:

int main() {//构造一个空图并准备dynamic_property_maps.graph_t 图(0)；动态属性 dp(ignore_other_properties);dp.property("node_id", get(&Vertex::name, graph));dp.property("label", get(&Vertex::label, graph));dp.property("shape", get(&Vertex::shape, graph));dp.property("label", get(&Edge::label, graph));

<块引用>

这就是它的全部内容.(阅读捆绑属性的魔力，通过页面找到 adjacency_list 模板).

虽然我们不需要它，但让我们也将图形属性放入混合中(如文档示例中所示):

//使用 ref_property_map 将图属性转为属性图boost::ref_property_mapgname(get_property(graph, graph_name));dp.property("name", gname);

现在剩下的就是阅读图表了.

嗯.好吧.让我们也把它写回去，但是用一个新的图形名称，然后:

std::ifstream dot("input.dot");if (read_graphviz(dot, graph, dp/*, "node_id"*/)) {std::cout <<图形名称:'"<<get_property(graph, graph_name) <<"'
";get_property(graph, graph_name) = "让我们给它起个名字吧";write_graphviz_dp(std::cout, graph, dp/*, "node_id"*/);}

不要忘记链接到 Boost Regex

完整演示

生活在 Coliru

#include #include #include #include #include 使用命名空间提升；结构顶点{std::string 名称、标签、形状；};结构边{std::string 标签；双倍重量；//也许你以后也需要这个，只是一个例子};typedef 属性图_p;typedef adjacency_list图_t;int main() {//构造一个空图并准备dynamic_property_maps.graph_t 图(0)；动态属性 dp/*(ignore_other_properties)*/;dp.property("node_id", get(&Vertex::name, graph));dp.property("label", get(&Vertex::label, graph));dp.property("shape", get(&Vertex::shape, graph));dp.property("label", get(&Edge::label, graph));//使用 ref_property_map 将图属性转换为属性图boost::ref_property_mapgname(get_property(graph, graph_name));dp.property("name", gname);std::ifstream dot("input.dot");if (read_graphviz(dot, graph, dp/*, "node_id"*/)) {std::cout <<图形名称:'"<<get_property(graph, graph_name) <<"'
";get_property(graph, graph_name) = "让我们给它起个名字吧";write_graphviz_dp(std::cout, graph, dp/*, "node_id"*/);}}

打印(注意之前的空名称，以及更新后的图形名称属性):

图形名称:''有向图 G {name="让我们给它起个名字吧";n0 [label="A9
", shape=box];n1 [label="- [0.48%,19.42%]", shape=ellipse];n11 [label="+ [0%,0%]", shape=ellipse];n12 [label="- [0%,0.75%]", shape=ellipse];n13 [label="+ [0.03%,1.33%]", shape=ellipse];n14 [label="- [0%,0.75%]", shape=ellipse];n15 [label="+ [0%,0%]", shape=ellipse];n16 [label="+ [0%,0%]", shape=ellipse];n17 [label="A14
", shape=box];n18 [label="+ [0.03%,2.51%]", shape=ellipse];n19 [label="A15
", shape=box];n2 [label="A15
", shape=box];n20 [label="A6
", shape=box];n21 [label="A2
", shape=box];n22 [label="- [0%,1.11%]", shape=ellipse];n23 [label="+ [0%,1%]", shape=ellipse];n25 [label="- [0%,2.18%]", shape=ellipse];n26 [label="+ [0%,1.79%]", shape=ellipse];n27 [label="- [0%,1%]", shape=ellipse];n28 [label="- [0%,0%]", shape=ellipse];n29 [label="- [0%,0%]", shape=ellipse];n3 [label="A11
", shape=box];n30 [label="- [0%,0%]", shape=ellipse];n31 [label="- [0%,0%]", shape=ellipse];n32 [label="- [0%,1%]", shape=ellipse];n33 [label="A13
", shape=box];n34 [label="+ [0%,1%]", shape=ellipse];n35 [label="- [0%,0%]", shape=ellipse];n36 [label="- [0.01%,1.21%]", shape=ellipse];n38 [label="A12
", shape=box];n39 [label="- [0%,1%]", shape=ellipse];n4 [label="A4
", shape=box];n40 [label="+ [0%,1.17%]", shape=ellipse];n42 [label="- [0%,0%]", shape=ellipse];n43 [label="A12
", shape=box];n44 [label="+ [0%,1.11%]", shape=ellipse];n45 [label="- [0%,1%]", shape=ellipse];n47 [label="- [0%,0%]", shape=ellipse];n49 [label="+ [0%,1.17%]", shape=ellipse];n5 [label="+ [0%,0%]", shape=ellipse];n52 [label="+ [0%,0.75%]", shape=ellipse];n54 [label="A13
", shape=box];n55 [label="A14
", shape=box];n56 [label="- [0.03%,2.5%]", shape=ellipse];n57 [label="+ [0.01%,2.27%]", shape=ellipse];n59 [label="- [0%,0%]", shape=ellipse];n6 [label="A7
", shape=box];n60 [label="+ [0%,1%]", shape=ellipse];n63 [label="A15
", shape=box];n64 [label="+ [0.05%,1.34%]", shape=ellipse];n65 [label="A15
", shape=box];n66 [label="- [0%,1%]", shape=ellipse];n67 [label="+ [0.02%,2.44%]", shape=ellipse];n7 [label="A14
", shape=box];n71 [label="+ [0.21%,3.83%]", shape=ellipse];n8 [label="+ [0%,1.57%]", shape=ellipse];n9 [label="- [0.01%,1.22%]", shape=ellipse];n0->n1 [标签=f]；n0->n2 [标签=t]；n17->n18 [label="<=110"];n17->n19 [label=">110"];n19->n20 [label="<=8"];n19->n49 [label=">8"];n2->n3 [label="<=228"];n2->n71 [label=">228"];n20->n21 [标签=aa]；n20->n25 [标签=c]；n20->n26 [标签=cc]；n20->n27 [标签=d]；n20->n28 [标签=e]；n20->n29 [标签=ff]；n20->n30 [标签=i]；n20->n31 [标签=j]；n20->n32 [标签=k]；n20->n33 [标签=m]；n20->n38 [标签=q]；n20->n42 [标签=r]；n20->n43 [标签=w]；n20->n47 [标签=x]；n21->n22 [label="<=41"];n21->n23 [label=">41"];n3->n4 [label="<=3"];n3->n63 [label=">3"];n33->n34 [标签=g]；n33->n35 [标签=p]；n33->n36 [标签=s]；n38->n39 [标签=f]；n38->n40 [标签=t]；n4-＞n5[标签=1]；n4->n6 [标签=u]；n4->n54 [标签=y]；n43->n44 [标签=f]；n43->n45 [标签=t]；n54->n55 [标签=g]；n54->n59 [标签=p]；n54->n60 [标签=s]；n55->n56 [label="<=204"];n55->n57 [label=">204"];n6->n7 [标签=bb]；n6->n11 [标签=dd]；n6->n12 [标签=ff]；n6->n13 [标签=h]；n6->n14 [标签=j]；n6->n15 [标签=n]；n6->n16 [标签=o]；n6->n17 [标签=v]；n6->n52 [标签=z]；n63->n64 [label="<=4"];n63->n65 [label=">4"];n65->n66 [label="<=5"];n65->n67 [label=">5"];n7->n8 [label="<=164"];n7->n9 [label=">164"];}

I have used a python library to generate the following GraphViz .dot file.

http://pastebin.com/mL7ck9Zp

I want to now read it into C++'s Boost::Graph so I can use Boost::Graph's library algorithms on it.

However, I need to do some preprocessing. In particular, I want to create a bundled property with a string constructor and have read_graphviz() pass the string in the label field in the dot file into the string constructor.

How do I go about doing this?

解决方案

First thing to realize is that Boost documentation samples almost always refer to/are generated from the actual samples: libs/graph/example/read_graphviz.cpp

Second thing to realize is that BGL is highly generic. Highly. And it achieves much of this genericity on the concepts of Boost Property Maps.

Finally, observe that parsing from "free-form" (at least dynamically/untyped text form) into some kind of generic MutableGraph model is pushing the limits.

This explains how you would have to read important parts of the documentation under the docs for property_map.

Anyhow, since indeed the sample seems a bit dated, allow me to demonstrate:

Include the implementation of the parser into one translation unit:
```
#include <libs/graph/src/read_graphviz_new.cpp>
```
This way BGL remains a header-only library.

Prefer bundled properties these days:

struct Vertex {
    std::string name, label, shape;
};

struct Edge {
    std::string label;
    double weight; // perhaps you need this later as well, just an example
};

typedef property<graph_name_t, std::string> graph_p;
typedef adjacency_list<vecS, vecS, directedS, Vertex, Edge, graph_p> graph_t;

We will be filling label, shape, name for vertices and edges.

The dynamic property maps are where the magic happens:

dynamic_properties dp/*(ignore_other_properties)*/;

This class provides type-erased access to a variety of underlying property maps identified by (name, typeid(key_type)).

This means you can register the bundled properties, and map them to the graphviz attribute names:

int main() {
    // Construct an empty graph and prepare the dynamic_property_maps.
    graph_t graph(0);

    dynamic_properties dp(ignore_other_properties);
    dp.property("node_id", get(&Vertex::name,  graph));
    dp.property("label",   get(&Vertex::label, graph));
    dp.property("shape",   get(&Vertex::shape, graph));
    dp.property("label",   get(&Edge::label,   graph));

That's really all there is to it. (Read up on the magic of Bundled Properties, found via the page for the adjacency_list template).

Though we don't need it, let's throw the graph property in the mix too (as in the documentation sample):

    // Use ref_property_map to turn a graph property into a property map
    boost::ref_property_map<graph_t *, std::string> gname(get_property(graph, graph_name));
    dp.property("name",    gname);

Now all that's left is reading the graph.

Well. Okay then. And let's write it back out too, but with a new graph name, then:

std::ifstream dot("input.dot");

if (read_graphviz(dot, graph, dp/*, "node_id"*/)) {
    std::cout << "Graph name: '" << get_property(graph, graph_name) << "'
";
    get_property(graph, graph_name) = "Let's give it a name";
    write_graphviz_dp(std::cout, graph, dp/*, "node_id"*/);
}

Don't forget to link to Boost Regex

Full Demo

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/dynamic_property_map.hpp>
#include <libs/graph/src/read_graphviz_new.cpp>
#include <boost/graph/graph_utility.hpp>

using namespace boost;

struct Vertex {
    std::string name, label, shape;
};

struct Edge {
    std::string label;
    double weight; // perhaps you need this later as well, just an example
};

typedef property<graph_name_t, std::string> graph_p;
typedef adjacency_list<vecS, vecS, directedS, Vertex, Edge, graph_p> graph_t;

int main() {
    // Construct an empty graph and prepare the dynamic_property_maps.
    graph_t graph(0);

    dynamic_properties dp/*(ignore_other_properties)*/;
    dp.property("node_id", get(&Vertex::name,  graph));
    dp.property("label",   get(&Vertex::label, graph));
    dp.property("shape",   get(&Vertex::shape, graph));
    dp.property("label",   get(&Edge::label,   graph));

    // Use ref_property_map to turn a graph property into a property map
    boost::ref_property_map<graph_t *, std::string> gname(get_property(graph, graph_name));
    dp.property("name",    gname);

    std::ifstream dot("input.dot");

    if (read_graphviz(dot, graph, dp/*, "node_id"*/)) {
        std::cout << "Graph name: '" << get_property(graph, graph_name) << "'
";
        get_property(graph, graph_name) = "Let's give it a name";
        write_graphviz_dp(std::cout, graph, dp/*, "node_id"*/);
    }
}

Prints (note the empty name before, and the updated graph name attribute, after):

Graph name: ''
digraph G {
name="Let's give it a name";
n0 [label="A9
", shape=box];
n1 [label="- [0.48%,19.42%]", shape=ellipse];
n11 [label="+ [0%,0%]", shape=ellipse];
n12 [label="- [0%,0.75%]", shape=ellipse];
n13 [label="+ [0.03%,1.33%]", shape=ellipse];
n14 [label="- [0%,0.75%]", shape=ellipse];
n15 [label="+ [0%,0%]", shape=ellipse];
n16 [label="+ [0%,0%]", shape=ellipse];
n17 [label="A14
", shape=box];
n18 [label="+ [0.03%,2.51%]", shape=ellipse];
n19 [label="A15
", shape=box];
n2 [label="A15
", shape=box];
n20 [label="A6
", shape=box];
n21 [label="A2
", shape=box];
n22 [label="- [0%,1.11%]", shape=ellipse];
n23 [label="+ [0%,1%]", shape=ellipse];
n25 [label="- [0%,2.18%]", shape=ellipse];
n26 [label="+ [0%,1.79%]", shape=ellipse];
n27 [label="- [0%,1%]", shape=ellipse];
n28 [label="- [0%,0%]", shape=ellipse];
n29 [label="- [0%,0%]", shape=ellipse];
n3 [label="A11
", shape=box];
n30 [label="- [0%,0%]", shape=ellipse];
n31 [label="- [0%,0%]", shape=ellipse];
n32 [label="- [0%,1%]", shape=ellipse];
n33 [label="A13
", shape=box];
n34 [label="+ [0%,1%]", shape=ellipse];
n35 [label="- [0%,0%]", shape=ellipse];
n36 [label="- [0.01%,1.21%]", shape=ellipse];
n38 [label="A12
", shape=box];
n39 [label="- [0%,1%]", shape=ellipse];
n4 [label="A4
", shape=box];
n40 [label="+ [0%,1.17%]", shape=ellipse];
n42 [label="- [0%,0%]", shape=ellipse];
n43 [label="A12
", shape=box];
n44 [label="+ [0%,1.11%]", shape=ellipse];
n45 [label="- [0%,1%]", shape=ellipse];
n47 [label="- [0%,0%]", shape=ellipse];
n49 [label="+ [0%,1.17%]", shape=ellipse];
n5 [label="+ [0%,0%]", shape=ellipse];
n52 [label="+ [0%,0.75%]", shape=ellipse];
n54 [label="A13
", shape=box];
n55 [label="A14
", shape=box];
n56 [label="- [0.03%,2.5%]", shape=ellipse];
n57 [label="+ [0.01%,2.27%]", shape=ellipse];
n59 [label="- [0%,0%]", shape=ellipse];
n6 [label="A7
", shape=box];
n60 [label="+ [0%,1%]", shape=ellipse];
n63 [label="A15
", shape=box];
n64 [label="+ [0.05%,1.34%]", shape=ellipse];
n65 [label="A15
", shape=box];
n66 [label="- [0%,1%]", shape=ellipse];
n67 [label="+ [0.02%,2.44%]", shape=ellipse];
n7 [label="A14
", shape=box];
n71 [label="+ [0.21%,3.83%]", shape=ellipse];
n8 [label="+ [0%,1.57%]", shape=ellipse];
n9 [label="- [0.01%,1.22%]", shape=ellipse];
n0->n1  [label=f];
n0->n2  [label=t];
n17->n18  [label="<=110"];
n17->n19  [label=">110"];
n19->n20  [label="<=8"];
n19->n49  [label=">8"];
n2->n3  [label="<=228"];
n2->n71  [label=">228"];
n20->n21  [label=aa];
n20->n25  [label=c];
n20->n26  [label=cc];
n20->n27  [label=d];
n20->n28  [label=e];
n20->n29  [label=ff];
n20->n30  [label=i];
n20->n31  [label=j];
n20->n32  [label=k];
n20->n33  [label=m];
n20->n38  [label=q];
n20->n42  [label=r];
n20->n43  [label=w];
n20->n47  [label=x];
n21->n22  [label="<=41"];
n21->n23  [label=">41"];
n3->n4  [label="<=3"];
n3->n63  [label=">3"];
n33->n34  [label=g];
n33->n35  [label=p];
n33->n36  [label=s];
n38->n39  [label=f];
n38->n40  [label=t];
n4->n5  [label=l];
n4->n6  [label=u];
n4->n54  [label=y];
n43->n44  [label=f];
n43->n45  [label=t];
n54->n55  [label=g];
n54->n59  [label=p];
n54->n60  [label=s];
n55->n56  [label="<=204"];
n55->n57  [label=">204"];
n6->n7  [label=bb];
n6->n11  [label=dd];
n6->n12  [label=ff];
n6->n13  [label=h];
n6->n14  [label=j];
n6->n15  [label=n];
n6->n16  [label=o];
n6->n17  [label=v];
n6->n52  [label=z];
n63->n64  [label="<=4"];
n63->n65  [label=">4"];
n65->n66  [label="<=5"];
n65->n67  [label=">5"];
n7->n8  [label="<=164"];
n7->n9  [label=">164"];
}

相关文章