python - 查找非常大的图的组件

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

如果您的节点足够少(例如几亿个)，那么您可以通过使用 disjoint set forest 单次遍历文本文件来计算连通分量。存储在内存中。

此数据结构仅存储每个节点的等级和父指针，因此如果节点足够少，应该适合内存。

对于更多节点，您可以尝试相同的想法，但将数据结构存储在磁盘上(并可能通过使用内存中的缓存来存储常用项来改进)。

下面是一些 Python 代码，它们实现了一个简单的内存中版本的不相交集森林:

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)

如果将它应用于名为 disjointset.txt 的文本文件，其中包含:

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

您可以通过不使用排名数组来节省内存，但可能会增加计算时间。