如何存儲非常大的圖空間高效，但有快速索引？

我正在與875713 nodes和5105039 edges一起工作。使用vector<bitset<875713>> vec(875713)或array<bitset<875713>, 875713>會引發段錯誤。我需要計算路徑恢復的全對最短路徑。我有什麼替代數據結構？如何存儲非常大的圖空間高效，但有快速索引？

我發現這個SO Thread但它不回答我的查詢。

編輯

我讀，似乎工作的建議後，嘗試這樣做。感謝大家幫助我。

vector<vector<uint>> neighboursOf; // An edge between i and j exists if 
            // neighboursOf[i] contains j 
neighboursOf.resize(nodeCount); 

while (input.good()) 
{ 
    uint fromNodeId = 0; 
    uint toNodeId = 0; 

    getline(input, line); 

    // Skip comments in the input file 
    if (line.size() > 0 && line[0] == '#') 
     continue; 
    else 
    { 
     // Each line is of the format "<fromNodeId> [TAB] <toNodeId>" 
     sscanf(line.c_str(), "%d\t%d", &fromNodeId, &toNodeId); 

     // Store the edge 
     neighboursOf[fromNodeId].push_back(toNodeId); 
    } 
}

來源

2012-07-15 Hindol

嘗試'矢量 vec（875713）'，或者甚至'矢量'。 – 2012-07-15 12:15:14

如果圖形密集，那麼鄰接矩陣就是一個非常緊湊的表示。 Wikipedias上的圖形文章有充足的理由選擇演示文稿 – fork0 2012-07-15 12:20:38

您似乎使用鄰接矩陣......並且它會很多：875713^2/8 ...〜90Gib。 – fork0 2012-07-15 12:25:36

你可以存儲每個節點邊緣的名單在單個陣列中。如果每個節點的邊數是可變的，則可以用空邊來終止列表。這將避免許多小列表（或類似的數據結構）的空間開銷。結果可能如下所示：

enum { 
    MAX_NODES = 875713, 
    MAX_EDGES = 5105039, 
}; 

int nodes[MAX_NODES+1];   // contains index into array edges[]. 
           // index zero is reserved as null node 
           // to terminate lists. 

int edges[MAX_EDGES+MAX_NODES]; // contains null terminated lists of edges. 
           // each edge occupies a single entry in the 
           // array. each list ends with a null node. 
           // there are MAX_EDGES entries and MAX_NODES 
           // lists. 

[...] 

/* find edges for node */ 
int node, edge, edge_index; 
for (edge_index=nodes[node]; edges[edge_index]; edge_index++) { 
    edge = edges[edge_index]; 
    /* do something with edge... */ 
}

由於您擁有大量的小數據結構，因此儘量減少空間開銷非常重要。每個節點列表的開銷只是一個整數，這比開銷少得多。一個stl向量。此外，這些列表還會不斷放在內存中，這意味着任何兩個列表之間都沒有浪費空間。對於可變大小的載體，情況並非如此。

讀取任何給定節點的所有邊將非常快，因爲任何節點的邊都連續存儲在內存中。

這個數據安排的缺點是，當你初始化數組和構造邊界列表時，你需要手邊有一個節點的所有邊。如果您獲得按節點排序的邊，這不是問題，但如果邊的順序是隨機的，則效果不佳。

來源

2012-07-15 13:51:36

'「最小化空間開銷非常重要」'<=絕對！我嘗試過vector vector方法，它會使系統變慢。爲此我必須重啓兩次。 – Hindol 2012-07-15 16:58:24

我如何實際測量空間開銷？我在Ubuntu上。我想比較這種方法與user1071136的方法。 – Hindol 2012-07-16 05:15:49

@Hindol查看更新的答案。總空間應該在26Mbytes左右，看陣列的大小。要測量其他解決方案的開銷，你可以構建一個更小的邊，並測量內存消耗的圖... – 2012-07-16 12:48:07

你的圖是稀疏的，那就是，|E| << |V|^2，所以你應該要麼使用稀疏矩陣來表示你的鄰接矩陣，或者等價地，存儲每個節點的鄰居列表（這是一個結果交錯數組），這樣的 -

vector<vector<int> > V (number_of_nodes); 
// For each cell of V, which is a vector itself, push only the indices of adjacent nodes. 
V[0].push_back(2); // Node number 2 is a neighbor of node number 0 
... 
V[number_of_nodes-1].push_back(...);

這樣，你預計內存的要求O(|E| + |V|)代替O(|V|^2)，而你的情況應該是大約50 MB，而不是gazzillion MB。

這也將導致更快的Dijkstra（或任何其他最短路徑算法），因爲您只需要在每個步驟考慮節點的鄰居。

來源

2012-07-15 12:29:24 user1071136

這可能是最好的方法。我會等一些其他有趣的答案。這樣，隨機邊訪問需要O（）時間。但我希望這個數字是'<= 5000'（想象一下社交網絡圖）。 – Hindol 2012-07-15 16:54:10

你是什麼意思「隨機邊緣訪問」？你在什麼情況下需要它？ – user1071136 2012-07-15 17:16:00

隨機我的意思是索引訪問像'edge [src] [dst]'其中src和dst不遵循特定模式。像邊[200] [0]在邊[15] [29]之後被訪問。我需要從_parent_矩陣隨機訪問_recover_所有對最短路徑。在_parent_矩陣中，parent [i] [j]的值表示在i和j之間的最短路徑中j之前的節點。 – Hindol 2012-07-15 18:17:57

如果我們聲明如下節點：

struct{ 
int node_id; 
vector<int> edges; //all the edges starts from this Node. 
} Node;

然後所有節點可表示如下：

array<Node> nodes;

來源

2012-07-15 12:38:03

如何存儲非常大的圖空間高效，但有快速索引？

回答

相關問題