这是使用递归生成器函数的解决方案:我没有使用 NetworkX,因此该图表示为邻居集的列表。
def all_connected_subgraphs(g, m):
def _recurse(t, possible, excluded):
if len(t) == m:
yield t
else:
excluded = set(excluded)
for i in possible:
if i not in excluded:
new_t = (*t, i)
new_possible = possible | g[i]
excluded.add(i)
yield from _recurse(new_t, new_possible, excluded)
excluded = set()
for (i, possible) in enumerate(g):
excluded.add(i)
yield from _recurse((i,), possible, excluded)
这是一种回溯算法,它表示,给定大小的部分子图< m
以及允许添加的一组节点,添加每个节点并扩展可能的选项集以包括从该节点可到达的所有节点。为了减少对称性,我们跟踪哪些节点已经被使用并将它们添加到excluded
set.
使用示例图进行演示:
>>> example_graph = [{1, 2}, {0, 2}, {0, 1, 3}, {2, 4}, {3}]
>>> list(all_connected_subgraphs(example_graph, 3))
[(0, 1, 2), (0, 2, 3), (1, 2, 3), (2, 3, 4)]
这是我用来生成随机图的代码,它应该相当于您从中采样的 G(n, m) 分布:
import random
import itertools as it
def random_graph(n, num_edges):
adj_sets = [set() for i in range(n)]
all_edges = list(it.combinations(range(n), 2))
random.shuffle(all_edges)
for (i, j) in all_edges[:num_edges]:
adj_sets[i].add(j)
adj_sets[j].add(i)
return adj_sets
在我的笔记本电脑上,从具有 100 个节点和 1,000 个边的图中查找大小为 4 的所有连接子图的运行时间不到半秒,如您的基准测试:
>>> g = random_graph(100, 1000)
>>> import timeit
>>> timeit.timeit(lambda: list(all_connected_subgraphs(g, 4)), number=1)
0.42606337900360813
注意list
这里需要耗尽生成器,否则算法实际上不会生成任何子图。如果您只想使用 a 迭代所有连接的子图for
循环,那么你不需要先将它们放入列表中。
有多种“简单”的方法可以优化它,例如每个节点的边集i
可以首先过滤以删除小于节点的“后边缘”i
,并且可以用堆栈替换递归以创建不使用的迭代算法yield
(这可能会产生相对较大的性能开销)。但除非您的输入需要更大或更密集,否则可能不需要这些优化。