提升：大圖和多線程

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