查找非常大圖的組件

我有一個非常大的圖表示在一個大小約爲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

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

來源

2013-08-21 phoenix

您是否有估計可能涉及多少個節點，邊緣和組件？另外，你是否需要完美的精度，還是近似值可以接受？ –

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

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

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

來源

2013-08-22 13:58:02

如果您有足夠的節點（例如幾億），那麼您可以使用存儲在內存中的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)

：

它打印

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可能增加計算時間。

來源

2013-08-21 17:42:42

這很好。如果可用內存只是此解決方案所需的一半，您會怎麼做？ – phoenix

您可以通過不使用排名大致減半內存。您可以使用[Python數組數據類型]（http://docs.python.org/2/library/array.html）來節省更多內存。之後，我可能會考慮將數據結構部分存儲在磁盤上，如果您對節點可能的結構有更多的瞭解，那麼您可以設計一個高效的分頁結構來緩存當前重要的部分。順便說一句，如果你不介意我問的話，那麼這麼龐大的圖表有什麼用？ –

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

來源

2013-08-22 12:29:21 adrianN

這是一個很好的建議，但是我沒有發現stxxl的python接口，我很傷心地發現它。 – phoenix

查找非常大圖的組件

回答

相關問題