查找图中的所有闭环

Question

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

通过闭环，我的意思是一个循环访问任何顶点不超过一次，除了循环开始的顶点（在这张图片的情况下，DGHD是一个例子，如BCDB、 或BCEFDB、 或 等）。

我尝试用矩阵乘法来做到这一点，将图写成一个矩阵，其中 2 个顶点连接的地方为 1，未连接的顶点为 0，并将它们的 n 次方，但这也会考虑到非闭环。

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

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

我想知道是否有关于采取哪个方向的建议？

Answer 1

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

\n\n

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

\n\n

这是使用您链接到的图表的示例：

\n\n

from networkx import Graph, DiGraph, simple_cycles\n\n# construct a graph using a dict: {node:[connected_nodes]}\nG = Graph(\n    {\'A\':[\'B\',\'G\',\'H\'],\n     \'B\':[\'A\',\'C\',\'D\'],\n     \'C\':[\'B\',\'D\',\'E\'],\n     \'D\':[\'B\',\'C\',\'E\',\'F\',\'G\', \'H\'],\n     \'E\':[\'C\',\'D\',\'F\'],\n     \'F\':[\'D\',\'E\',\'G\'],\n     \'G\':[\'A\',\'D\',\'F\',\'H\'],\n     \'H\':[\'A\',\'D\',\'G\'],\n    }\n)\n\n# optional: draw the graph for verification\n#labels = dict(zip(G.nodes(),G.nodes()))\n#networkx.draw_networkx(G,labels=labels)\n\n# simple_cycles only accepts DiGraphs. convert G to a bi-directional\n# digraph. note that every edge of G will be included in this list!\nDG = DiGraph(G)\nlist(simple_cycles(DG))\n

\n\n

（截断的）输出是：

\n\n

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

\n\n

如果您希望自己实现这一点而不使用 NetworkX，simple_cycles()请使用 Johnson 算法。（参见 Donald B. Johnson，查找有向图的所有基本电路，SIAM J. Comput., 4(1), 77\xe2\x80\x9384）

\n