核心连通组件算法

Question

对于无向图,我有4,000,000,000(40亿)个边.它们在大型文本文件中表示为节点ID对.我想计算此图的连接组件.不幸的是,一旦你将带有边缘的节点ID加载到内存中,这就需要超过128GB的RAM.

是否有一个用于查找相对简单的连接组件的核心算法？或者甚至更好,它可以与Unix命令工具和现有(python)库拼凑在一起吗？

Answer 1

您可以只保存一组顶点作为它们的“颜色”（一个 int 值），然后运行文件而不加载整组链接，用颜色标记顶点，如果两个顶点都没有着色，则标记新的颜色，颜色相同如果一个已着色而另一个未着色，则使用两种颜色中最低的颜色，并重新绘制数组中使用最高颜色绘制的所有其他顶点（如果两者都已着色）。伪代码示例：

int nextColor=1;
int merges=0;
int[] vertices;
while (!file.eof()) {
    link=file.readLink();
    c1=vertices[link.a];
    c2=vertices[link.b];
    if ((c1==0)&&(c2==0)) {
        vertices[link.a]=nextColor;
        vertices[link.b]=nextColor;
        nextColor++;
    } else if ((c1!=0)&&(c2!=0)) {
        // both colored, merge
        for (i=vertices.length-1;i>=0;i--) if (vertices[i]==c2) vertices[i]=c1;
        merges++;
    } else if (c1==0) vertices[link.a]=c2; // only c1 is 0
    else vertices[link.b]=c1; // only c2 is 0
}

如果您选择小于 32 位的类型来存储顶点的颜色，您可能需要首先检查是否nextColor已达到最大，是否有未使用的颜色数组（在合并中释放），并在以下情况下跳过对两个新顶点集的着色无法使用任何颜色，如果两种颜色均已使用并且发生任何合并，则重新运行文件读取过程。

更新：由于顶点并不是真正的整数而是字符串，因此在解析该文件时还应该有一个字符串到整数的映射。如果您的字符串受到长度限制，您可能可以将它们作为哈希表全部放入内存中，但我会通过创建另一个文件来预处理该文件，该文件将所有字符串“s1”替换为“1”，“s2” ”与“2”等，其中“s1”、“s2”是文件中作为顶点出现的任何名称，以便数据将被压缩为整数对列表。如果您稍后将处理类似的数据（也就是说，您的图形没有太大变化，并且包含基本相同的顶点名称，请存储包含从名称到整数的链接的“元数据”文件，以方便进一步的预处理。