python - 查找图中的所有闭环

Question

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

闭环是指一个循环不访问任何顶点超过一次，循环开始的顶点除外(在 this picture 的情况下，DGHD 是一个示例，如 BCDB 或 BCEFDB 等)。

我尝试用矩阵乘法来做到这一点，将图形写成一个矩阵，其中 2 个顶点相连，1 为 0，不相连的地方为 0，并将它们的 n 次方计算在内，但是这将考虑非封闭也有循环。

这个人似乎有同样的工作，但设法解决了:

• Finding unique loops in the closed graph

我想知道是否有任何建议可以选择哪个方向？

Answer 1

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

此方法的一个警告是您必须将图形转换为有向图。这意味着无向图的每条边都将成为有向图的循环。 (一条无向边变为两条有向边。)您可以简单地过滤输出以仅包含长度为三或更大的循环。

这是一个使用您链接到的图表的示例:

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()，请使用 Johnson 算法。 (参见 Donald B. Johnson，查找有向图的所有基本电路，SIAM J. Comput.，4(1)，77–84)