核外连通组件算法

Question

我有一个无向图，其中有4,000,000,000（四十亿）个边，它们以节点id对的形式在一个大型文本文件中表示。 我想计算这个图的连通组件。不幸的是，一旦你将带有边缘的节点id加载到内存中，这将占用超过我可用的128GB RAM。

是否有一种外部算法可以找到相对简单的连接组件实现？ 或者更好的是，它能够通过Unix命令工具和现有的（Python）库拼凑在一起吗？

- Simd

---

你有多少个顶点？ - dreamzor

@dreamzor 大约20亿。 - Simd

我猜你需要简单的连通分量而不是“强连通分量”，因为图是无向的？ - dreamzor

实际上，将40亿个边存储到128 GB的RAM中应该是可行的。你如何存储它？希望不是作为邻接矩阵？但是，同样，您需要执行一个简单的BFS / DFS，这也需要O（N）内存。 - dreamzor

@RBarryYoung 嗯，这个想法是你可以输出连接组件，而不必在 RAM 中存储它们。 - Simd

Answer 1

根据您提供的问题描述和评论中的答案，我认为最简单的方法可能是使用类似@dreamzor所描述的方法。以下是该答案的详细版本。 基本思路是将数据转换为更紧凑的格式，以适合内存，对该数据运行常规连接组件算法，然后解压缩它。请注意，如果将32位数字ID分配给每个节点，则存储所有节点所需的总空间最多为四十亿个节点和八十亿条边的空间（假设您存储了每个边的两个副本），这是十二十亿个32位整数的空间，仅约48GB的空间，低于您的内存阈值。 首先，编写一个脚本，读取边文件，并为每个节点分配一个数字ID（可能按它们出现的顺序顺序）。让此脚本将此映射写入文件，并在处理时编写一个新的边文件，其中使用数字节点的ID而不是字符串名称。完成后，您将拥有将ID映射到名称的名称文件和占用比以前少得多的边文件。您在评论中提到您可以将所有节点名称放入内存中，因此此步骤应该非常合理。请注意，您无需将所有边存储在内存中-您可以通过程序将它们流式传输-因此这不应该是瓶颈。 接下来，编写一个程序，将边文件（但不是名称文件）读入内存，并使用任何合理的算法（BFS或DFS在这里非常好）查找连接组件。如果您小心处理内存（在这里使用类似C或C ++的东西会是一个不错的选择），则这应该可以轻松地适合主存储器。完成后，通过数字ID将所有群集写入外部文件。现在，您拥有按ID列出的所有CC列表。 最后，编写一个程序，从名称文件中读取ID到节点映射，然后流式传输群集ID，并将每个群集中所有节点的名称写入最终文件。 此方法应该相对容易实现，因为关键思想是保留您已经习惯的现有算法，只需更改图的表示方式以使其更具内存效率。我以前在处理巨大的图表（维基百科）时使用过此类方法，即使在比您的内存更少的系统上也能完美运行。

- templatetypedef

Answer 2

你只能持有一个顶点数组作为它们的"颜色"（一个整数值），然后在不加载整个链接集的情况下运行文件，用颜色标记顶点，如果两个顶点都没有被标记，则使用新的颜色进行标记，如果其中一个被标记，则使用相同的颜色进行标记，如果两个都被标记，则使用最低的两种颜色，并重新绘制所有已经用最高颜色绘制的其他顶点。以下是伪代码示例：

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"是文件中出现的顶点名称，以便将数据压缩为一对整数的列表。如果您稍后将处理类似的数据（即，您的图形变化不大，并且包含大部分相同的顶点名称），请将“元数据”文件与名称到整数的链接存储起来，以便进一步预处理。

- Vesper