查找图中的所有闭环 [英] Finding all closed loops in a graph

问题描述

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

闭环"是指一个循环，该循环最多访问一次顶点，但循环开始的顶点除外(对于在闭合图中找到唯一循环

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

解决方案

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)

I am trying to write a Python code which will identify all of the closed loops within an arbitrary graph.

By a closed loop, I mean a loop which visits no vertex more than once, with the exception of the vertex the loop starts on (in the case of this picture, DGHD is an example, as is BCDB, or BCEFDB, or etc).

I tried doing this with matrix multiplication, writing the graph as a matrix with 1s where 2 verticies are connected, and a 0 where they aren't, and putting them to the nth power, however this will take into account non closed loops also.

This person seems to have had the same job, but managed to solve it:

• Finding unique loops in the closed graph

I was wondering if there was any advice on which direction to take?

解决方案

NetworkX is a popular Python package for working with graphs included in many scientific Python distributions. It includes some algorithms for computing graph cycles. In particular, simple_cycles(DiGraph) would answer your question.

One caveat to this approach is that you have to convert your graph into a digraph. This means that every edge of your undirected graph will become a cycle in your directed version. (An undirected edge becomes two directed edges.) You can simply filter the output to only contain cycles of length three or greater.

Here's an example using the graph you linked to:

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))

The (truncated) output is:

[['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'],
 ...
]

If you'd prefer to implement this yourself without using NetworkX simple_cycles() uses Johnson's algorithm. (See Donald B. Johnson, Finding All the Elementary Circuits of a Directed Graph, SIAM J. Comput., 4(1), 77–84)

这篇关于查找图中的所有闭环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！