如何在networkx中找到图的所有连接子图? [英] How to find all connected subgraph of a graph in networkx?

问题描述

我正在开发一个 python 应用程序，我想列出所有可能连接的任何大小的子图，并使用 NetworkX 从每个节点开始.

I'm developing a python application, and i want to list all possible connected subgraph of any size and starting from every node using NetworkX.

我只是尝试使用 itertools 库中的组合()来查找所有可能的节点组合，但它太慢了，因为它还搜索未连接的节点:

I just tried using combinations() from itertools library to find all possible combination of nodes but it is very too slow because it searchs also for not connected nodes:

for r in range(0,NumberOfNodes)
for SG in (G.subgraph(s) for s in combinations(G,r):
    if (nx.is_connected(SG)):
        nx.draw(SG,with_labels=True)
        plt.show()

实际输出是正确的.但是我需要另一种更快的方法来做到这一点，因为具有 50 个节点和 8 个作为 LenghtTupleToFind 的图的节点的所有组合都高达 10 亿(n！/r！/(nr)！)但只有其中的一小部分是连接子图所以是我感兴趣的.所以，有可能有一个函数来做到这一点?

The actual output is correct. But i need another way faster to do this, because all combinations of nodes with a graph of 50 nodes and 8 as LenghtTupleToFind are up to 1 billion (n! / r! / (n-r)!) but only a minimal part of them are connected subgraph so are what i am interested in. So, it's possible to have a function for do this?

对不起我的英语，提前谢谢你

Sorry for my english, thank you in advance

编辑:

这是一个例子:

起始图示例

所以，我想要的结果:

[0]
[0,1]
[0,2]
[0,3]
[0,1,4]
[0,2,5]
[0,2,5,4]
[0,1,4,5]
[0,1,2,4,5]
[0,1,2,3]
[0,1,2,3,5]
[0,1,2,3,4]
[0,1,2,3,4,5]
[0,3,2]
[0,3,1]
[0,3,2]
[0,1,4,2]

以及生成连通图的所有组合

and all combination that generates a connected graph

推荐答案

我有同样的要求，最终使用了这个代码，非常接近你正在做的事情.此代码产生您要求的输入.

I had the same requirements and ended up using this code, super close to what you were doing. This code yields exactly the input you asked for.

import networkx as nx
import itertools

G = you_graph
all_connected_subgraphs = []

# here we ask for all connected subgraphs that have at least 2 nodes AND have less nodes than the input graph
for nb_nodes in range(2, G.number_of_nodes()):
    for SG in (G.subgraph(selected_nodes) for selected_nodes in itertools.combinations(G, nb_nodes)):
        if nx.is_connected(SG):
            print(SG.nodes)
            all_connected_subgraphs.append(SG)

这篇关于如何在networkx中找到图的所有连接子图?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！