查找非常大圖的組件

Question

我有一個非常大的圖表示在一個大小約爲1TB的文本文件中，每個邊如下所示。

From-node to-node 

我想將它分成它的弱連接組件。如果它更小，我可以將它加載到networkx中並運行他們的組件查找算法。例如 http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.components.connected.connected_components.html#networkx.algorithms.components.connected.connected_components

有沒有什麼辦法可以做到這一點，而無需將全部內容加載到內存中？

Answer 1

如果節點的連號是太大，無法在內存中，可以分而治之，並使用外部內存排序做的大部分工作對你（如包含在Windows和Unix的sort命令排序文件比內存大得多）：

1. 選擇一些閾值頂點k。
2. 閱讀原始文件和它的每一個邊緣的寫至3之一文件：
   • 要a如果其最大編號的頂點是<ķ
   • 要b如果它的最小編號的頂點是> = K
   • 要c否則（即，如果它有一個頂點< k和一個頂點> = K）
3. 如果a足夠小，以解決（找到連接COM ）在記憶中（使用例如Peter de Rivaz's algorithm）然後這樣做，否則遞歸解決它。解決方案應該是一個文件，其每行包含兩個數字x y，並按x排序。每個x是一個頂點編號，y是它的代表 - 與x相同組件中編號最小的頂點。
4. 同樣爲b做。
5. 按c的最小編號端點對邊進行排序。
6. 通過c中的每個邊緣，重新命名端點< k（記住，必須有一個這樣的端點）給它的代表，從解決方案中找到的子問題a。這可以通過使用線性時間合併算法與子問題a的解決方案合併來高效完成。調用生成的文件d。
7. 按d的最大編號端點對邊進行排序。 （事實上​​，我們已經重命名爲最小編號的端點並不會使其變得不安全，因爲重命名永遠不會增加頂點的編號。）
8. 通過d中的每條邊，重命名> = k的端點代表，從解決方案中發現使用線性時間合併的子問題b。調用生成的文件e。
9. 解決e。 （與a和b一樣，如果可能，直接在內存中執行此操作，否則進行遞歸。如果需要遞歸，則需要找到不同的劃分邊的方法，因爲e中的所有邊已經「跨」k。可以例如使用頂點數的隨機置換對頂點重新編號，遞歸解決所產生的問題，然後重新命名它們。）這一步是必要的，因爲可能存在邊緣（1，k），另一邊緣（2，k + 1 ）和第三個邊（2，k），這意味着組件1,2，k和k + 1中的所有頂點都需要組合成一個單獨的組件。
10. 通過子問題a的解決方案中的每一行，使用子問題e的解決方案更新該頂點的代表（如有必要）。這可以使用線性時間合併來高效完成。寫出新的代表列表（由於我們從a的解決方案中創建它，事實上已經按頂點數排序）到文件f。
11. 對於子問題b的解決方案中的每一行，請創建文件g。
12. 連接f和g以產生最終答案。 （爲了提高效率，只需將步驟11直接附加到f）。

上面使用的所有線性時間合併操作都可以直接從磁盤文件中讀取，因爲它們只能按升序從每個列表中訪問項目（即不需要緩慢的隨機訪問）。

Answer 2

如果您有足夠的節點（例如幾億），那麼您可以使用存儲在內存中的disjoint set forest，通過文本文件單遍計算連接的組件。

這個數據結構只存儲每個節點的等級和父指針，所以如果你有足夠的節點，應該適合內存。對於較大數量的節點，您可以嘗試相同的想法，但將數據結構存儲在磁盤上（並可能通過在內存中使用高速緩存來存儲經常使用的項目）。

這裏是實現一個簡單的內存版本分離集森林的一些Python代碼：如果你把它應用到包含所謂的文本文件disjointset.txt

N=7 # Number of nodes 
rank=[0]*N 
parent=range(N) 

def Find(x): 
    """Find representative of connected component""" 
    if parent[x] != x: 
     parent[x] = Find(parent[x]) 
    return parent[x] 

def Union(x,y): 
    """Merge sets containing elements x and y""" 
    x = Find(x) 
    y = Find(y) 
    if x == y: 
     return 
    if rank[x]<rank[y]: 
     parent[x] = y 
    elif rank[x]>rank[y]: 
     parent[y] = x 
    else: 
     parent[y] = x 
     rank[x] += 1 

with open("disjointset.txt","r") as fd: 
    for line in fd: 
     fr,to = map(int,line.split()) 
     Union(fr,to) 

for n in range(N): 
    print n,'is in component',Find(n) 

：

1 2 
3 4 
4 5 
0 5 

它打印

0 is in component 3 
1 is in component 1 
2 is in component 1 
3 is in component 3 
4 is in component 3 
5 is in component 3 
6 is in component 6 

您可以通過不使用rank數組來節省內存，代價爲o f可能增加計算時間。

Answer 3

外部內存圖遍歷很難獲得高性能。我建議不要編寫自己的代碼，實現細節可以區分幾個小時的運行時間和幾個月的運行時間。您應該考慮使用現有的庫，如stxxl。請參閱here瞭解使用它來計算連通組件的紙張。