寻找非常大的图形的组件

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

如果您有足够的节点(例如几亿),那么您可以通过使用存储在内存中的不相交的集合林,通过文本文件单次传递来计算连接的组件.

此数据结构仅存储每个节点的排名和父指针,因此如果节点足够少,则应该适合内存.

对于大量节点,您可以尝试相同的想法,但将数据结构存储在磁盘上(并且可能通过在内存中使用缓存来存储经常使用的项目来改进).

下面是一些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

您可以通过不使用秩数组来节省内存,但代价是可能会增加计算时间.

Answer 2

如果甚至节点数量太大而无法容纳在内存中，您可以分而治之并使用外部内存排序来为您完成大部分工作（例如sortWindows和Unix中包含的命令可以对比内存大得多的文件进行排序）：

1. 选择一些阈值顶点k。
2. 读取原始文件并将其每个边写入 3 个文件之一：
   • 如果a其最大编号顶点 < k
   • 如果b其最小编号顶点 >= k
   • 否则c（即如果它有一个顶点 < k 并且一个顶点 >= k）
3. 如果a足够小，可以在内存中求解（找到连通分量）（使用例如Peter de Rivaz 的算法），则执行此操作，否则递归求解。解决方案应该是一个文件，其每行由两个数字组成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）。

上面使用的所有线性时间合并操作都可以直接从磁盘文件读取，因为它们仅以递增顺序访问每个列表中的项目（即不需要缓慢的随机访问）。