如何用多线程在Boost Graph中高效创建无重复边？

我正在构建一个包含50K+节点的Boost Graph（用于映射机器人的配置空间），目前边创建已成为程序性能瓶颈，希望通过多线程实现边创建来优化。我将所有顶点索引存储在哈希表中，以便添加边时快速查找；每个顶点需要连接其5个最近邻节点。

我的图已禁用平行边，图定义如下：

using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties>;

最近邻查找采用局部敏感哈希（Local Sensitivity Hashing），核心代码如下：

model* myModel;
myModel = new lshEuclidean();

myModel->fit(datapoints, status);  /// 对所有无碰撞的叶节点进行训练

添加边前，我已将所有顶点插入图中，并构建哈希表以快速获取顶点索引（测试阶段将向量转为字符串存入哈希表，已知该方式低效，后续会自定义哈希函数），代码如下：

BoostGraph::VertexProperties vp1;

BoostGraph graph(5);

std::unordered_map<std::string, int> map;
    
for(int center = 0; center < finalLeafNodes.size(); center++){
    Vec origin = finalLeafNodes[center]->getOrigin();
    std::vector<double> joint_angle = {origin.at(0)*toRadians, origin.at(1)*toRadians, origin.at(2)*toRadians,
                                        origin.at(3)*toRadians, origin.at(4)*toRadians};

    Eigen::VectorXd joint_angle_center;
    joint_angle_center.resize(5);
    joint_angle_center << joint_angle[0], joint_angle[1], joint_angle[2], joint_angle[3], joint_angle[4];

    vp1.joint_angles = joint_angle;
    BoostGraph::Vertex v_center = graph.AddVertex(vp1);
    int vertex_index_center = graph.getVertexIndex(v_center);

    Vec joint_angle_in_vector_degrees = origin;
    
    std::stringstream output;
    std::copy(joint_angle_in_vector_degrees.begin(), joint_angle_in_vector_degrees.end(), std::ostream_iterator<double>(output, " "));

    map[output.str()] = vertex_index_center;
} 

之后，我为每个顶点查找指定半径内的邻居，按距离排序后选取前3/5个，通过哈希表获取邻居顶点索引并添加边；同时通过局部规划器检查两点间路径是否无碰撞，仅在无碰撞时添加边，相关代码如下：

neighbors.sort([&query](Item &a, Item &b) -> bool {compare(a, b, query);});

auto edge = graph.AddEdge(center_iterator->second, neighbour_iterator->second, BoostGraph::EdgeProperties{(double)recursion_index + 1.});

当前针对5自由度机器人，维度已提升。我尝试过用mutex_lock()实现多线程，但提速效果不明显。请问是否可通过共享内存对象先存储所有待添加边，再批量添加到图中以避免平行边？

1. 先收集有效边再批量添加完全可行 #

这是解决多线程下Boost Graph边创建瓶颈的高效方案：

• 你的图用boost::setS作为边容器，本身会自动去重，但单线程逐个添加时每次都要做集合查找，多线程加锁会导致大量等待，效率极低。
• 先在多线程中无锁完成耗时的邻居查找、碰撞检测，收集所有符合条件的边，最后单线程批量插入图中，既能利用多线程加速计算，又能避免操作图时的锁竞争。

2. 边收集阶段的关键优化 #

• 避免重复边：因为是无向图，顶点对(u, v)和(v, u)是同一条边。收集时约定只存储u < v（基于顶点整数索引）的边对，直接减少一半重复数据，也降低后续批量添加的去重开销。
• 线程安全的存储策略：用线程本地存储（thread_local）让每个线程维护自己的边集合，最后合并所有线程的结果并统一去重，完全避免锁竞争。比如每个线程用std::set<std::pair<int, int>>存储边对，合并时再合并到全局集合。
• 碰撞检测并行化：这部分是耗时核心，必须放在多线程阶段处理，每个线程负责一部分顶点的邻居筛选和碰撞校验，输出有效边对。

3. 批量添加边的细节 #

• 遍历收集到的边集合，直接调用add_edge()即可。因为boost::setS会自动处理平行边，再加上收集阶段的去重，这一步的开销极小。
• 如果边数量极大，可临时将图的边容器换成boost::vectorS，批量添加后再转换回boost::setS——但需权衡转换开销，仅适合超大规模边场景。

4. 其他辅助优化 #

• 替换哈希表的字符串键：尽快把向量转字符串的哈希表换成自定义哈希函数，比如针对Eigen::VectorXd或Vec类型实现哈希，大幅提升顶点查找速度。
• LSH参数调优：针对5自由度配置空间，调整LSH的哈希桶数量、哈希函数数量等参数，提升最近邻查找的准确率和速度，减少无效邻居的处理量。

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