Boost图形库和访问者模式

Question

我正在编写一个用于操作键合图的库，并使用Boost Graph Library来存储数据。不幸的是，我似乎无法想出如何使用它来实现正确的访问者模式，因为您不能对顶点进行子类化 - 您必须依赖于“属性”。该库提供的访问者框架似乎主要针对某些算法工作，其中顶点都是相同类型，但存储不同信息。在我的问题中，顶点具有不同的类型和不同类型的信息 - 一些顶点是电阻器，而另一些则是电容器等。如何编写基于顶点属性而不是顶点本身的访问者模式呢？

到目前为止，我唯一的想法是编写一个小类来表示指向需要获取图形信息的原始顶点的对象类型。然而，这似乎非常笨拙，难以处理。

- user137792

Answer 1

你是说无法子类化顶点吗？你可以使用自己的顶点类，只需要在Graph typedef中指定即可。甚至在使用BGL算法时，您可以将成员用作属性。

至于另一种方式（我认为更难），您需要创建一个顶点属性列表，并使用顶点描述符访问它...我想是这样的。

编辑：在定义图类型时指定顶点/边缘类：

struct Vertex {
    double some_property;
};

struct Edge {
    double weight;
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::undirectedS, Vertex, Edge
> Graph; //sorry about the formatting

Graph g;

从哪里开始g[vertex_descriptor]应该返回一个顶点的引用，例如：

//add 100 vertices
for (int i=0; i<100; ++i) {
    Graph::vertex_descriptor v = add_vertex(g);
    g[v].some_property = -1.0;
}

//zero some_property for all vertices
for (Graph::vertex_iterator i = vertices(g).first;
                            i != vertices(g).second;
                            ++i)
{
    g[*i].some_property = 0.0;
}

我无法利用这些属性找到我的访问者代码，但我找到了BGL文档的相关部分：

1）内部属性的部分建议您改用：
2）捆绑属性

第二个链接似乎有一个使用成员指针的Boost函数来利用捆绑属性。

这有帮助吗？

- aib

---

真的吗？我正在寻找关于这个的文档，但是找不到太多信息 - 你能给一个简短的例子吗？在这个例子中，你可以提供一个自定义的顶点类，而不是将属性附加到顶点上。 - user137792

我也有文档方面的问题。回家后我会发布一段代码示例。 - aib

它确实做到了 - 我在尝试解决这个问题时采用了类似的方法。唯一的问题是，我还需要从元素的属性中访问顶点信息，这涉及跟踪元素自己的vertex_descriptor并通过描述符路由所有连接信息请求。最终变得相当复杂，现在我相当确定最好自己编写一个小型图形实现。不过还是谢谢，当我将来在其他事情上使用这个库时，捆绑属性肯定是正确的选择！ - user137792

Answer 2

如果有人关心的话，在2个月后，这里有一个访客正在查看该属性。

class demo_visitor : public default_bfs_visitor {
public:
    template <typename Vertex, typename Graph>
    void discover_vertex( Vertex u, Graph& g)
    {
        printf("Visited vertex %d with property %f\n",
            u, g[u].some_property);
    }
};

如果访问者需要修改属性，那么事情就会变得稍微复杂一些。关于这个问题 - 点击这里

- ravenspoint

---

你怎么使用它？'breadth_first_search(G, vertex(0, G), demo_visitor())' 报错了。 - Arlen

@user1344784 你遇到了什么错误？也许你可以发布一个新的问题，附上你的代码和收到的错误。如果你这样做了，请在这里发布你的问题链接，这样我就能找到它。 - ravenspoint

Answer 3

也许你可以使用 boost::variant 来构建顶点类型的不相交和，然后在每个顶点处将 BGL 访问者与 boost::variant 访问者结合起来？

- dtw