c++ - Boost Graph 查找一组顶点的邻居

Question

我有一个 undirected_unweighted_graph graph;定义如下:

typedef typename boost::adjacency_list<boost::vecS,boost::vecS,boost::undirectedS,boost::no_property,boost::no_property> undirected_unweighted_graph;

它有几个由无向边互连的顶点。 在我的算法中，我正在搜索 graph 的连通子图。它只包含一些具有某些属性的顶点。

我正在使用一个线性优化软件包，它为我的问题提供了可能的最佳解决方案。一个解决方案由一组具有固定大小 n 的顶点组成，并且可能是不可行的(即顶点在 graph 的相应子图中未连接)。我目前正在生成一个包含解决方案顶点的新图并添加边，这些边也存在于 graph 中。 .我正在使用 boost::connected_components()计算它的连通分量。

现在我来回答我的问题:
我的下一步是通过施加约束来 boost 生成解决方案的性能。具体来说，我将“增长”一个解决方案，从单个节点开始，以 n 的子图结束。节点。在每个阶段，部分解决方案将通过添加其邻居之一来增长。 (想法是，如果部分解决方案可以发展为完整解决方案，那么它的至少一个邻居将在完整解决方案中。)我如何识别这些邻居？

我的方法如下:

我正在遍历每个组件，然后遍历 boost::out_edges(v, g) .然后我必须检查邻居是否是我的组件的一部分。如果它不是组件的一部分，我将它添加到组件邻居组中。我想知道是否有任何方法可以迭代 boost::out_edges(V, g)对于顶点列表 V .

编辑

更具体地说:给定一个图，我可以像这样迭代给定顶点的邻居:

for (auto edge: boost::make_iterator_range(boost::out_edges(v, graph))) {
    //do stuff
}

如果我有一个连通分量怎么办，比如一个顶点 vector std::vector<size_t> component .我想要的是组件的出边，这意味着顶点的所有出边，不包括 component 的两个顶点之间的边。 .有没有一种优雅的方法可以有效地获得这些优势？

Answer 1

我不会遍历多个顶点。相反，我会维护两组顶点——一组包含当前部分解中的顶点，另一组包含与部分解相邻(但不在其中)的顶点。当线性优化包向部分解添加一个顶点时，该顶点也应该从邻接集移动到解中的顶点集。接下来需要迭代来自新顶点的边，但只需要迭代来自新顶点的边。对于与新顶点相邻的每个顶点，如果它不在部分解中，则将其添加到相邻顶点集。

我还会尝试使用仅包含部分解中的顶点和与部分解相邻的顶点的集合来进行类似的尝试。更少的开销。根据周围代码的预期，此集合可能与仅包含相邻顶点的集合一样有效。

这种方法的优点是您可以消除重复性工作。如果您已经查看了顶点 A 的所有邻居，为什么仅仅因为顶点 B 已添加到您的集合中就需要再次查看它们？

这种方法的一个缺点是，如果您有时需要回溯(想想深度优先搜索并维护这些集合的堆栈)，您可能需要大量的内存开销。这有多糟糕取决于 n 有多大，以及平均有多少条边连接到每个顶点。即使在糟糕的情况下，一些巧妙的冗余消除也可能挽救这种方法，但我会把它留到以后再说。