Python：在显示为边列表的图中查找连通分量

Question

我有一个形式为

的边列表

start | end
 a       c
 b       d
 e       b

我有数千万条边（大约 3000 万条），我无法将整个图读入内存 - 至少不能使用像 networkx 这样有点占用内存的库。

我的目标是在该列表表示的图中找到包含少于 x 个节点的所有连通分量。

例如，我想得到所有少于x=30个节点的连通分量。但是我不想通过构建整个图然后搜索连接的组件来做到这一点（例如调用这个 networkx 命令：nx.connected_component_subgraphs(nxg)）。

有没有一种方法可以只使用边列表文件搜索连通分量而无需构建整个图？

附加信息：节点名称是长度为 10-20 asci 值的字符串。

Answer 1

您首先需要通过为节点分配较短的标识符来减少数据占用空间。您可以将那些较短的标识符和原始名称之间的映射写入另一个文件，这样您就可以在运行算法之后将任何解决方案转换为这些名称。

假设您的节点标识符足够短，您可以将所有内容加载到内存中，在由节点标识符键入的字典中。

然后使用Union-Find结构&算法识别连通分量

最后按允许的最大尺寸过滤那些。

有一些库提供 Union-Find 实现，可以提供更好的性能。这是 Union-Find 的简单实现：

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = self
        self.size = 1

class UnionFind(dict):
    def find(self, key):
        node = self.get(key, None)
        if node is None:
            node = self[key] = Node(key)
        else:
            while node.parent != node: 
                # walk up & perform path compression
                node.parent, node = node.parent.parent, node.parent
        return node

    def union(self, key_a, key_b):
        node_a = self.find(key_a)
        node_b = self.find(key_b)
        if node_a != node_b:  # disjoint? -> join!
            if node_a.size < node_b.size:
                node_a.parent = node_b
                node_b.size += node_a.size
            else:
                node_b.parent = node_a
                node_a.size += node_b.size

然后，以下函数将从迭代器加载该结构，return 大小满足要求的组件：

from collections import defaultdict

def find_components(line_iterator, max_size):
    forest = UnionFind()

    for line in line_iterator:
        forest.union(*line.split())

    result = defaultdict(list)
    for key in forest.keys():
        root = forest.find(key)
        if root.size <= max_size:
            result[root.key].append(key)

    return list(result.values())

下面是下图的演示：

data = """x d
c j
i e
f x
n z
a u
g r
w x
p l
u o
m g
k s
t q
y l
h m
n b
k v
e u
i o
r m
n c
x q
f q
j l
s v"""

results = find_components(data.splitlines(), 5)
print(results)

此演示的输出是：

[['i', 'e', 'a', 'u', 'o'], ['g', 'r', 'm', 'h'], ['k', 's', 'v']]

Python：在显示为边列表的图中查找连通分量

Python: Finding connected components in a graph presented as edge lists

python

algorithm

search

graph

networkx