核心外连接组件算法

Question

对于一个无向图，我有4,000,000(40亿)条边。它们在大型文本文件中表示为成对的节点in。我想计算这个图的连通部分。不幸的是，一旦将带有边的节点ids加载到内存中，就会占用比我可用的128 of更多的内存。

有没有一种核心外的算法来寻找相对容易实现的连接组件？或者更好的是，它可以与Unix命令工具和现有的(python)库拼凑在一起吗？

Answer 1

根据您对问题的描述和您在评论中提供的答案，我认为最简单的方法可能是使用@dreamzor描述的方法。这里有一个更丰富的版本的答案。

基本思想是将数据转换为适合内存的更压缩的格式，对该数据运行常规的连通分量算法，然后解压缩。请注意，如果您为每个节点分配一个32位数字ID，那么存储所有节点所需的总空间最多为40亿个节点和80亿条边(假设您存储每条边的两个副本)，这是120亿个32位整数的空间，只有大约48 at的空间，低于您的内存阈值。

首先，编写一个脚本，读入edges文件，为每个节点分配一个数字ID (可能按节点出现的顺序)。让此脚本将此映射写入到一个文件中，并在执行过程中编写一个新的边文件，该文件使用节点的数字it而不是字符串名称。完成后，您将有一个将ID映射到名称的名称文件和一个占用比以前少得多的边文件。您在注释中提到，您可以将所有节点名称放入内存中，因此这一步应该非常合理。请注意，您不需要将所有的边都存储在内存中-您可以通过程序流式传输它们-所以这不应该是一个瓶颈。

接下来，编写一个程序，将边文件-而不是名称文件-读取到内存中，并使用任何合理的算法(BFS或DFS在这里很好)找到连接的组件。如果你注意你的内存(在这里使用像C或C++这样的东西会是一个很好的调用)，这应该可以轻松地放入主内存中。完成后，将所有集群按数字ID写出到外部文件中，现在您就有了按ID列出的所有容器服务。

最后，编写一个程序，从名称文件中读取ID到节点的映射，然后输入集群ID并将每个集群中所有节点的名称写出到最终文件中。

这种方法的实现应该相对简单，因为其关键思想是保留您习惯的现有算法，但只需更改图形的表示形式，以提高内存效率。我以前在处理巨大的图形(维基百科)时也使用过这样的方法，即使在内存比你的少的系统上，它也能很好地工作。

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是否达到最大值，是否有未使用的颜色数组(在合并中释放)，如果没有颜色可以使用，则跳过对两个顶点的新集合进行着色，然后，如果两种颜色都已使用并且发生任何合并，则重新运行文件读取过程。

更新:由于顶点实际上不是int，而是字符串，因此在解析该文件时，您还应该有一个字符串到int的映射。如果你的字符串有长度限制，你可以把它们都放到内存中作为哈希表，但是我会通过创建另一个文件来预处理这个文件，这个文件将所有的字符串"s1“替换为"1"，"s2”替换为"2"，依此类推，其中"s1"，"s2“是文件中显示为顶点的任何名称，这样数据将被压缩成一个整数对的列表。如果您稍后将处理类似的数据(即，您的图变化不大，并且包含基本相同的顶点名称)，请存储带有从名称到整数的链接的“元数据”文件，以便于进一步的预处理。