求图中的所有闭环

Question

我正在尝试编写一个Python代码，它将识别任意图中的所有封闭循环。

所谓闭环，我指的是一个不超过一次访问顶点的循环，但循环开始的顶点除外(在这幅画的情况下，DGHD是一个例子，BCDB或BCEFDB等等也是如此)。

我试着用矩阵乘法来实现这一点，把图写成一个1s的矩阵，其中2组是连通的，0是不连接的，然后把它们放到第n次方，但是这也会考虑到非闭环。

这个人似乎做过同样的工作，但设法解决了这个问题：

• 在闭图中寻找唯一的循环

我在想，对于该走哪一条路，是否有什么建议？

Answer 1

NetworkX是一个流行的Python包，用于处理许多科学Python发行版中包含的图形。它包括一些计算图圈的算法。特别是，simple_cycles(DiGraph)会回答你的问题。

对这种方法的一个警告是，您必须将图转换为有向图。这意味着您的无向图的每个边都将成为有向版本中的一个循环。(无向边变为两条有向边。)您可以简单地过滤输出，使其只包含长度为3或更长的周期。

下面是一个使用链接到的图形的示例：

from networkx import Graph, DiGraph, simple_cycles

# construct a graph using a dict: {node:[connected_nodes]}
G = Graph(
    {'A':['B','G','H'],
     'B':['A','C','D'],
     'C':['B','D','E'],
     'D':['B','C','E','F','G', 'H'],
     'E':['C','D','F'],
     'F':['D','E','G'],
     'G':['A','D','F','H'],
     'H':['A','D','G'],
    }
)

# optional: draw the graph for verification
#labels = dict(zip(G.nodes(),G.nodes()))
#networkx.draw_networkx(G,labels=labels)

# simple_cycles only accepts DiGraphs. convert G to a bi-directional
# digraph. note that every edge of G will be included in this list!
DG = DiGraph(G)
list(simple_cycles(DG))

(截断的)输出是：

[['B', 'D', 'H', 'G', 'F', 'E', 'C'],
 ['B', 'D', 'H', 'G', 'A'],
 ['B', 'D', 'H', 'A', 'G', 'F', 'E', 'C'],
 ['B', 'D', 'H', 'A'],
 ['B', 'D', 'F', 'G', 'H', 'A'],
 ['B', 'D', 'F', 'G', 'A'],
 ['B', 'D', 'F', 'E', 'C'],
 ['B', 'D', 'G', 'F', 'E', 'C'],
 ...
]

如果您希望自己实现而不使用NetworkX，则simple_cycles()使用约翰逊的算法。(见Donald B. Johnson，查找有向图的所有基本电路，SIAM J. Comput，4(1)，77-84)