提升：大图和多线程

Question

我需要创建一个指导的图，该图可以从大数据集中非常大。我知道这些事情是肯定的：

• 每个节点都有为N >> K节点
• 该图是通过比较每个所有节点建立的最多有K出边
• 我有一个列表（unordered_map）其他（是的，不幸的是，O（N^2））

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

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

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

你知道是否有可能做我在想什么吗？你建议不要这样做吗？

干杯！

Answer 1

我认为你应该把你的目标分解成两个单独的子目标。

1. 通过对节点对进行N *（N-1）次测试来创建节点之间的链接。您似乎对如何将其分解为独立的线程有了一个概念。将结果存储在您知道线程安全的数据结构中，而不用担心boost：graph的奥秘。

2. 从节点和（刚创建的）链接创建boost ::图形。

关于存储在每个线程中创建的链接的说明：找到合适的线程安全数据结构并不那么容易。如果你使用STL动态分配的结构，那么你不得不担心做一个线程安全的分配器，这是一个挑战。如果预分配，那么有很多meessy代码来处理分配。所以，我建议将每个线程创建的链接存储在一个单独的数据结构中，因此它们不必是线程安全的。当链接全部创建时，您可以逐个遍历由每个线程创建的链接。

可以设想一个稍微高效的设计，但是需要很多关于线程安全的神秘知识。我提出的设计可以在没有神秘知识或棘手的代码的情况下实现，因此可以更快，更强大地实现，并且更容易维护。

Answer 2

几乎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; 
}