NetworkX 制作边组合的迭代列表

Question

我有一个 180x180 的邻接矩阵，我正在尝试生成所有合理的组合以使用 NetworkX。我想按顺序删除部分图形，然后确定对新编辑图形的全局效率的影响。在此视图中，一组合理的组合是彼此相邻的所有节点集，以及从假设它们彼此相邻到子图的所有可能的子图组合。运行所有组合的蛮力方法太慢了，对于任何超过 15 个删除序列的运行时间约为 21 小时。因此，我们只想通过查看彼此相邻的组合来解决这个问题。基本上代码需要执行以下操作：导入包含二进制邻接矩阵的 csv，其中 1 表示物理连续性（在本例中为大脑）导入networkx图确定彼此之间的路径长度最多为 1 的所有组合集....换句话说，如果两个节点或两个节点集在任一端的距离大于 1，则它们将被忽略为每个合理的组合生成这些节点集的列表这是基本问题假设大脑某个区域的物理空间包括几个大致像这样的区域......假设这些是镶嵌平面的不规则多边形1 2 3 4 56 7 8 910 11我们可以把它变成一个邻接矩阵，其中 1 表示区域共享边界，0 表示它们在物理上没有相互接壤+--+---------------------------------+|  | 1  2  3  4  5  6  7  8  9  10 11|+--+---------------------------------+|1 | 0  1  0  0  0  1  0  0  0  0  0 ||2 | 1  0  1  0  0  0  1  1  0  0  0 ||3 | 0  1  0  1  0  0  0  1  1  0  0 ||4 | 0  0  1  0  1  0  0  0  1  0  0 ||5 | 0  0  0  1  0  0  0  0  1  0  0 ||6 | 1  0  0  0  0  0  1  0  0  1  0 ||7 | 0  1  0  0  0  1  0  1  0  1  1 ||8 | 0  1  1  0  0  0  1  0  1  0  1 ||9 | 0  0  1  1  0  0  0  1  0  0  0 ||10| 0  0  0  0  0  1  1  0  0  0  1 ||11| 0  0  0  0  0  0  1  1  0  1  0 |+--+---------------------------------+基本上，邻接矩阵代表了彼此相邻的大脑部分......我们想要遍历并生成这些节点的分组列表，这些节点从单个节点开始，并处理每个可能的节点组合需要注意的是，我们不希望这些组合彼此之间没有身体接触......因此，例如，这样的列表将有 1,2,....11 以及 1+2 和 7+8 等最终我们将有 2+7+8 和 6+7+8+10 因为所有这些节点都接触每个其他并形成一个连接的组件 1-11 是不允许的，因为它们不共享边界，4+5+10 也不允许，因为它们不接触这很重要的原因是我们是脑外科医生，我们删除部分图表是为了谋生......即大脑图表......但你永远不会删除不相邻的节点......我们正在尝试使用图表来定义我们可以在手术中走多远......所以我们需要使用 python 来生成所有可能的节点删除组合，这在现实世界中是有意义的......二进制邻接矩阵代表物理空间中的现实一旦我有一个节点删除的合理组合列表，我就有了一个采用不同 pandas 数据帧的代码......将节点和边归零，然后创建一个 networkx 图，我们在其上运行效率指标......我只是需要一种方法来确定所有可能的连续组件集，这样我们就不会运行解剖学上不合理的组合我想解决这个问题的方法是在networkx中使用某种连续组件功能，但是我无论如何都找不到从图中导出连接组件的所有可能组合基本上代码会像这样boundary=pd.read_csv(adjacency.csv)G=networkx.from_pandas_adjacency(boundary)combo="something to iterate the graph g to create a list of all connected components"请注意，我们使用一个 csv 来确定列表并在不同的 CSV 上使用该列表在此先感谢...这是您正在帮助解决的一个重要问题，它将挽救生命

Answer 1

连接组件的正确命名是完整的子图（不要混淆真正的连接组件）。您的问题被称为集团问题。networkx有几种算法可以解决这个问题： networkx cliques

你的问题可以通过这个函数来解决：networkx.algorithms.clique.enumerate_all_cliques

请注意，此函数返回所有可能的团，长度也为 1 和 2（即每个节点和每条边），因此您应该过滤 1-2 长度的团。例如，对于您的图表，此函数返回：

list(nx.enumerate_all_cliques(G))

[[0],

 [1],

 [2],

 [3],

 [4],

 [5],

 [6],

 [7],

 [8],

 [9],

 [10],

 [0, 1],

 [0, 5],

 [1, 2],

 [1, 6],

 [1, 7],

 [2, 3],

 [2, 7],

 [2, 8],

 [3, 4],

 [3, 8],

 [4, 8],

 [5, 6],

 [5, 9],

 [6, 7],

 [6, 9],

 [6, 10],

 [7, 8],

 [7, 10],

 [9, 10],

 [1, 2, 7],

 [1, 6, 7],

 [2, 3, 8],

 [2, 7, 8],

 [3, 4, 8],

 [5, 6, 9],

 [6, 7, 10],

 [6, 9, 10]]

但如果我们过滤所有无用的派系，我们将得到：

list(filter(lambda x: len(x) > 2, nx.enumerate_all_cliques(G)))

[[1, 2, 7],

 [1, 6, 7],

 [2, 3, 8],

 [2, 7, 8],

 [3, 4, 8],

 [5, 6, 9],

 [6, 7, 10],

 [6, 9, 10]]