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

Question

[注意：答案中给出了快速解决方案，但需要进一步改进速度。]

\n

给定一个具有n 个顶点的无向稀疏连接图G。我正在寻找一种快速方法来查找具有m 个顶点的G的所有连通子图。可以假设m \xe2\x89\xaa n且G的顶点度为deg(v) \xe2\x89\xaa n。

\n

图解示例

\n

对于这个例子，我们有n = 5，m = 3。

\n

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

\n\n

代码示例

\n

下面的代码使用networkxandego_graph非常慢。对于n = 100、deg(v) = 10、m = 4的图，大约需要 100 秒。这是m \xe2\x89\xaa n和deg(v) \xe2\x89\xaa n的示例。n =10000的情况将需要永恒的时间。

\n

import networkx as nx\nimport itertools\nimport time\n\nn=100   #nodes in graph\ndeg=10  #node degree in graph\nm=4     #nodes in subgraph\n\ngraph=nx.gnm_random_graph(n,n*deg,seed=1)#construct random graph\n\nstarttime=time.time()\nG = graph.copy()\nall_connected_subgraphs = []\nradius=m-1\nfor n in graph.nodes():\n    egoG = nx.ego_graph(G,n,radius=radius,center=False)# all closeby nodes\n    for sn in itertools.combinations(egoG, radius):# test all combinations of closeby nodes\n        SG=[n,*sn]\n        G_sub=G.subgraph(SG)\n        if nx.is_connected(G_sub):\n            all_connected_subgraphs.append(SG)\n    G.remove_node(n)\n\nendtime=time.time()\nprint(endtime-starttime)        \n

\n

慢速步骤是 和G_sub=G.subgraph(SG)，if nx.is_connected(G_sub):分别消耗总计算时间的 20% 和 80%。

\n

在相关问题中没有给出有效的解决方案。

\n

Answer 1

这是使用递归生成器函数的解决方案：我没有使用 NetworkX，因此该图表示为邻居集的列表。

\n

def all_connected_subgraphs(g, m):\n    def _recurse(t, possible, excluded):\n        if len(t) == m:\n            yield t\n        else:\n            excluded = set(excluded)\n            for i in possible:\n                if i not in excluded:\n                    new_t = (*t, i)\n                    new_possible = possible | g[i]\n                    excluded.add(i)\n                    yield from _recurse(new_t, new_possible, excluded)\n    excluded = set()\n    for (i, possible) in enumerate(g):\n        excluded.add(i)\n        yield from _recurse((i,), possible, excluded)\n

\n

这是一种回溯算法，它表示，给定大小的部分子图< m和允许添加的一组节点，添加每个节点并扩展可能的选项集以包括从该节点可到达的所有节点。为了减少对称性，我们跟踪哪些节点已被使用并将它们添加到集合中excluded。

\n

使用示例图进行演示：

\n

>>> example_graph = [{1, 2}, {0, 2}, {0, 1, 3}, {2, 4}, {3}]\n>>> list(all_connected_subgraphs(example_graph, 3))\n[(0, 1, 2), (0, 2, 3), (1, 2, 3), (2, 3, 4)]\n

\n

这是我用来生成随机图的代码，它应该相当于您从中采样的 G(n,\xc2\xa0m) 分布：

\n

import random\nimport itertools as it\n\ndef random_graph(n, num_edges):\n    adj_sets = [set() for i in range(n)]\n    all_edges = list(it.combinations(range(n), 2))\n    random.shuffle(all_edges)\n    for (i, j) in all_edges[:num_edges]:\n        adj_sets[i].add(j)\n        adj_sets[j].add(i)\n    return adj_sets\n

\n

在我的笔记本电脑上，从具有 100 个节点和 1,000 个边的图中查找大小为 4 的所有连接子图（如您的基准测试）的运行时间不到半秒：

\n

>>> g = random_graph(100, 1000)\n>>> import timeit\n>>> timeit.timeit(lambda: list(all_connected_subgraphs(g, 4)), number=1)\n0.42606337900360813\n

\n

请注意，list此处需要耗尽生成器，否则算法实际上不会生成任何子图。如果您只想用for循环迭代所有连接的子图，那么您不需要先将它们放入列表中。

\n

有各种“简单”的方法来优化它，例如，可以首先过滤每个节点的边集，i以删除小于 的节点的“后边” i，并且可以用堆栈替换递归，以制定迭代算法不使用yield（这可能会产生相对较大的性能开销）。但除非您的输入需要更大或更密集，否则可能不需要这些优化。

\n