查找非常大图的组件

我有一个非常大的图表示在一个大小约为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

查找非常大图的组件

回答

相关问题