c++ - Boost:大图和多线程

Question

我需要创建一个有向图，该图可能来自大型数据集。我肯定知道这些事情:

• 每个节点最多有K条出边
• 我有一个包含 N >> K 个节点的列表 (unordered_map)
• 该图是通过将所有节点相互比较来构建的(是的，不幸的是 O(N^2))

考虑到这一点，我会使用 std::thread 并行化图形创建，我想知道这是否可以通过 Boost Graph Library 完成。

如果我使用邻接矩阵，应该可以预分配矩阵(K*N 个元素)，因此插入所有相邻节点将是线程安全的。

我读过 BGL 可能是线程不安全的，但我发现的帖子是三年前的。

你知道是否可以按照我的想法去做吗？您是否建议采用其他方式？

干杯!

Answer 1

几乎所有 BGL 中的图算法都需要一个映射:vertex -> int 为每个顶点分配一个范围 [0, num_vertices(g) ) 内的唯一整数。此映射称为“vertex_index”，通常可作为 property_map 访问。

话虽如此，我可以假设您的顶点已经是整数或与某些整数相关联(例如，您的 unordered_map 在“mapped_type”中有一些额外的字段)。如果您的输入顶点存储在连续的紧凑数组中，则更好(对于性能和内存)，例如std::vector，那么索引是自然的。

如果顶点是 [关联] 整数，内存紧凑图的最佳选择是“Compressed Sparse Row Graph”。该图是不可变的，因此您需要在生成图之前填充边缘容器。

正如 ravenspoint 所解释的那样，您最好的选择是为每个线程配备自己的本地结果容器，并仅在将本地结果合并到最终结果时才锁定中央容器。这种策略由 TBB 模板实现无锁 tbb::parallel_reduce .因此，您构建图形的完整代码大致如下所示:

#include "tbb/blocked_range2d.h"
#include "tbb/parallel_reduce.h"
#include "boost/graph/compressed_sparse_row_graph.hpp"

typedef something vertex; //e.g.something is integer giving index of a real data

class EdgeBuilder
{
public:
    typedef std::pair<int,int> edge;
    typedef std::vector<edge> Edges;
    typedef ActualStorage Input;

    EdgeBuilder(const Input & input):_input(input){} //OPTIONAL: reserve some space in _edges
    EdgeBuilder( EdgeBuilder& parent, tbb::split ): _input(parent.input){} // reserve something

    void operator()( const const tbb::blocked_range2d<size_t>& r ) 
    { 
        for( size_t i=r.rows().begin(); i!=r.rows().end(); ++i ){
            for( size_t j=r.cols().begin(); j!=r.cols().end(); ++j ) {
                //I assume you provide some function to compute existence
                if (my_func_edge_exist(_input,i, j))
                    m_edges.push_back(edge(i,j));
            }
        }        
    } 

    //merges local results from two TBB threads
    void join( EdgeBuilder& rhs ) 
    {
        m_edges.insert( m_edges.end(), rhs.m_edges.begin(), rhs.m_edges.end() ); 
    }

    Edges _edges; //for a given interval of vertices
    const Input & _input;
};

//full flow:  
boost::compressed_sparse_row_graph<>* build_graph( const Storage & vertices)
{
    EdgeBuilder builder(vertices);
    tbb::blocked_range2d<size_t,size_t> range(0,vertices.size(), 100, //row grain size 
                                              0,vertices.size(), 100); //col grain size
    tbb::parallel_reduce(range, builder);

    boost::compressed_sparse_row_graph<> 
      theGraph = new boost::compressed_sparse_row_graph<> 
                        (boost::edges_are_unsorted_multi_pass_t, 
                         builder._edges.begin(), builder._edges.end(), 
                         vertices.size() );
    return theGraph;
}