如何使用Boost Graph分割顶点集？C++并行图着色实现相关问题

以下回答默认基于你使用adjacency_list的默认VertexList参数vecS（即顶点存储在连续向量中），如果使用其他存储策略会单独说明。

问题1解答 #

• 首先不推荐直接访问g.m_vertices这个内部实现成员，标准用法是调用num_vertices(g)获取当前图的总顶点数，num_vertices(g)/4的拆分逻辑本身数值计算是没问题的，但要注意处理除不尽的边界场景，比如总顶点数不是4的整数倍时，最后一个线程需要覆盖剩余的所有顶点。
• 当你删除顶点后，顶点索引范围取决于adjacency_list的VertexList模板参数：
  • 如果是默认的vecS：删除顶点后，索引大于被删顶点的所有顶点会自动前移，顶点索引保持连续，总大小为删除后的实际顶点数，你举的10删1剩6的场景，索引范围是0到5，但此时原大于4的顶点描述符都会失效，数值会统一减1。
  • 如果是listS/setS等非连续存储策略：顶点描述符不是整数索引，不存在连续的序号范围，num_vertices(g)仍返回实际顶点数，但无法用0到N的整数直接索引顶点。

问题2解答 #

有两种常用的实现方案，可根据你的存储策略选择：

1. 针对vecS连续存储场景：
   顶点描述符本身就是连续整数，你可以直接按拆分后的索引范围遍历，不需要调用vertices(g)拿全量迭代器，示例代码如下：

// 拆分逻辑
int total = num_vertices(g);
int step = total / 4;
for(int i = 0; i < 4; i++){
    int start = i * step;
    int end = (i == 3) ? total : (i+1)*step;
    // 把start和end传给处理函数
    process_subset(g, start, end);
}

// 处理函数实现
void process_subset(const Graph& g, int start, int end) {
    for (int v = start; v < end; ++v) {
        cout << v << endl;
        // 你的着色逻辑
    }
}

2. 通用全场景兼容方案（适配所有VertexList存储策略）：
   先把全量顶点描述符预存到一个连续向量中，再拆分向量的区间给不同线程，示例代码如下：

// 预存全量顶点
using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;
std::vector<Vertex> all_vertices(vertices(g).first, vertices(g).second);

// 拆分逻辑
int total = all_vertices.size();
int step = total /4;
for(int i =0; i<4; i++){
    auto start_iter = all_vertices.begin() + i*step;
    auto end_iter = (i ==3) ? all_vertices.end() : all_vertices.begin() + (i+1)*step;
    // 把迭代器区间传给处理函数
    process_subset(g, start_iter, end_iter);
}

// 处理函数实现
template<typename Iter>
void process_subset(const Graph& g, Iter begin, Iter end) {
    for (Iter it = begin; it != end; ++it) {
        Vertex v = *it;
        cout << v << endl;
        // 你的着色逻辑
    }
}

注意：并行着色时需要对邻接顶点的颜色访问做线程安全保护，避免出现数据竞争导致着色结果错误。

内容的提问来源于stack exchange，提问作者Giacomo