如何使用 Boost Graph 拆分顶点集？

Question

我正在使用 Boost Graph 和 [=44= 为并行 graph coloring 编写一些算法]。我正在处理非常大的图（最小的有 32K 个顶点）。

我想做的是获取整组顶点，将它们分成几部分并将每个部分分配给不同的线程并并行工作，但我在处理一些段落时遇到了困难。

基本思路是什么：

int step = g.m_vertices.size()/4;
int min = 0;

for(int i = 0; i < 4; i++){
    // call the function
}

我在里面调用的函数就是这样的

for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
    cout << *vp.first << endl;
}

所以我有两个问题：

g.m_vertices.size()/4;是正确的解法吗？如果最初我有 10 个顶点，然后我删除中间的一些顶点（例如 4），只剩下 6 个顶点（所以这是新的大小）但是顶点的索引从 从 0 到 5 或 从 0 到 9?
如何只传递顶点的一个子集给vp而不是传递vertices(g)？

Answer 1

g.m_vertices.size()/4; is the right solutions?

这仅取决于您的要求。

If initially I have 10 vertices, then I remove some vertex in the middle (e.g. 4), only 6 vertices left (so this is the new size) but the index of the vertices go from 0 to 5 or from 0 to 9?

这取决于您的图形模型。您没有指定图表的类型（我知道，您 do 说的是哪个模板，而不是模板参数）。假设顶点容器选择器为 vecS，那么是的，在删除 4 次之后，顶点描述符（和索引）将为 [0,6]。

How can pass only a subset of vertices to vp instead of passing vertices(g)

多种方式。

您可以std::for_each使用并行执行策略
您可以使用 openmp 从普通循环创建并行部分
您可以使用 filtered_graph 适配器创建底层图形的 4 个“视图”并在这些视图上操作
您可以使用 PBGL，它实际上是为处理巨大的图形而创建的。这有一个额外的好处，它可以与 threading/interprocess/inter-host 通信一起使用，可以跨段协调算法等。
你可以使用sub_graphs；如果您的图表构建方式具有自然分割，这主要（仅）有趣

None 的解决方案是微不足道的。但是，这是使用 filtered_graph:

的简单演示

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/random.hpp>
#include <iostream>
#include <random>

using G = boost::adjacency_list<>;
using V = G::vertex_descriptor;

G make_graph() {
    G g;
    std::mt19937 prng(std::random_device{}());
    generate_random_graph(g, 32 * 1024 - (prng() % 37), 64 * 1024, prng);
    return g;
}

template <int NSegments, int Segment> struct SegmentVertices {
    std::hash<V> _h;
    bool operator()(V vd) const { return (_h(vd) % NSegments) == Segment; }
};

template <int N>
using Quart = boost::filtered_graph<G, boost::keep_all, SegmentVertices<4, N>>;

template <typename Graph>
void the_function(Graph const& g, std::string_view name)
{
    std::cout << name << " " << size(boost::make_iterator_range(vertices(g)))
            << " vertices\n";
}

int main()
{
    G g = make_graph();
    the_function(g, "full graph");

    Quart<0> f0(g, {}, {});
    Quart<1> f1(g, {}, {});
    Quart<2> f2(g, {}, {});
    Quart<3> f3(g, {}, {});

    the_function(f0, "f0");
    the_function(f1, "f1");
    the_function(f2, "f2");
    the_function(f3, "f3");
}

打印例如

full graph 32766 vertices
f0 8192 vertices
f1 8192 vertices
f2 8191 vertices
f3 8191 vertices

如何使用 Boost Graph 拆分顶点集？

How to split set of vertices with Boost Graph?

c++

parallel-processing

boost

graph