在C++中使用1億個節點的大圖的表示

Question

我正在處理一個擁有5億個節點數量的非常大的圖，節點的平均度數爲100，因此它是一種稀疏圖。我還必須存儲每個邊緣的權重。我目前使用兩個向量，像以下

// V could be 100 million 
vector<int> *AdjList = new vector<int>[V]; 
vector<int> *Weight = new vector<int>[V]; 

使用的vectorvector似乎並沒有被有效利用空間。它需要超過400GB的存儲空間。有沒有更好的空間有效的方式來存儲這個大型圖形？任何使用任何C++庫的建議？

Answer 1

開場白

你能想到用載體的載體，而不是使用動態內存分配的：

vector<vector<int>> AdjList(V); 

在任何情況下，你必須伏在你的鄰接表不同vector<int>。每個矢量需要一些空間開銷來管理其項目的大小和位置。不幸的是，通過將權重保持在不同的向量/數組中，您可以將此開銷加倍（並在添加新鏈接時關聯隱藏內存管理）。

那麼爲什麼不重新組合鄰接表和重量呢？

struct Link { 
    int target; // node number that was in adj list. Hope none is negative!! 
    int weight; 
}; 
vector<vector<Link>> AdjList(V); 

結構是否稀疏？

如果絕大多數節點有某種鏈接，這就很好了。

如果相反，很多節點不具有輸出鏈接（或者，如果您有大量未使用的節點ID範圍），那麼你可以考慮：

map<int, vector<Link>> AdjList; 

的map是一個關聯數組。只有具有傳出鏈接的節點的矢量。順便說一句，你可以使用任何你想要的節點編號方案，甚至是負值節點。

你甚至可以更進一步，並使用雙映射。第一張地圖爲您提供了傳出節點。第二張地圖將目標節點映射到重量：

map<int, map<int, int>> Oulala; 

但是，這樣做的風險要大得多。

大容量？

map and vector使用默認分配器動態管理內存。但是你有很多預定尺寸的小物體。所以你可以考慮使用你自己的allocator。這可以顯着優化內存管理開銷。另外，如果使用向量，當您加載新節點的鄰接列表時，立即爲向量保留大小（如果您知道的話）可能很有效。這可以避免向量的增長進行幾次連續的重新分配。數百萬個節點可能會非常昂貴。

圖書館？

搜索第三方庫超出了搜索範圍。但是，如果上面的提示是不夠的，你可以例如考慮使用現有的圖形庫：

• Boost Graph library：升壓優勢
• SNAP: Standford Network Analysis Platform：對於巨大的圖表爲構建（和使用）的庫擁有數百萬個節點。 （網絡在這裏是指在節點和邊緣上有數據的圖形）

還有其他一些圖庫，但很多看起來不再維護或不適合大卷。