在Python中快速找到给定大小的所有连通子图的方法？

[注：快速解决方案在answer https://stackoverflow.com/a/75751315/12842085然而，需要进一步改进速度。]

给定一个无向稀疏连接图G with n顶点。我正在寻找一种快速的方法来找到所有连接的子图G with m顶点。可以假设m ≪ n并且顶点的度数G is deg(v)≪n.

图解示例

对于我们的例子n=5, m=3.

4个连通子图为：(0,1,2),(1,2,3),(0,2,3),(2,3,4)

代码示例

以下代码使用networkx and ego_graph是相当慢的。绘制一张图大约需要 100 秒n=100, deg(v)=10, m=4。这是一个例子m ≪ n and deg(v)≪n。案子n=10000 需要永恒的时间。

import networkx as nx
import itertools
import time

n=100   #nodes in graph
deg=10  #node degree in graph
m=4     #nodes in subgraph

graph=nx.gnm_random_graph(n,n*deg,seed=1)#construct random graph

starttime=time.time()
G = graph.copy()
all_connected_subgraphs = []
radius=m-1
for n in graph.nodes():
    egoG = nx.ego_graph(G,n,radius=radius,center=False)# all closeby nodes
    for sn in itertools.combinations(egoG, radius):# test all combinations of closeby nodes
        SG=[n,*sn]
        G_sub=G.subgraph(SG)
        if nx.is_connected(G_sub):
            all_connected_subgraphs.append(SG)
    G.remove_node(n)

endtime=time.time()
print(endtime-starttime)        

缓慢的脚步是线条G_sub=G.subgraph(SG) and if nx.is_connected(G_sub):分别消耗总计算时间的 20% 和 80%。

In a 相关问题 https://stackoverflow.com/q/54440779/12842085没有给出有效的解决方案。

这是使用递归生成器函数的解决方案：我没有使用 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（这可能会产生相对较大的性能开销）。但除非您的输入需要更大或更密集，否则可能不需要这些优化。