我正在尝试编写Python代码,该代码将识别任意图中的所有闭环。

闭环是指不重复访问顶点的循环,除了循环开始的顶点(在this picture的情况下,DGHD是示例,BCDB也是这样),或者BCEFDB等)。

我尝试使用矩阵乘法进行此操作,将图形编写为矩阵,其中连接2个顶点的1s,不连接2个顶点的0,并将它们置于n次方,但是这也要考虑非闭环。

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


Finding unique loops in the closed graph


我想知道在哪个方向上有什么建议吗?

最佳答案

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

关于python - 查找图中的所有闭环,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/29244965/

10-12 14:09