查找无向图中的所有循环 [英] Finding all cycles in undirected graphs

问题描述

我需要一个工作算法来查找无向图中的所有简单循环。我知道成本可以是指数型的，问题是NP完全的，但是我将在一个小图中使用它（最多20-30个顶点），而且周期数很少。

经过长期的研究（主要是在这里），我还没有一个工作方法。以下是我的搜索摘要：

在无向图中查找所有循环

无向图中的循环 - >仅检测是否存在循环

- >非常好的描述，但没有解决方案

查找有向图中的所有循环 - >仅在有向图中找到周期

使用boost图库检测无向图中的周期

唯一答案我发现，这接近我的问题，是这样的：

查找图中的所有循环，还原

似乎找到一组基本的循环并对它们进行异或运算诀窍。寻找一个基本的循环集很容易，但我不明白如何组合它们以获得图中的所有循环...

解决方案

对于无向图，标准方法是寻找所谓的循环库：一组简单循环，可以通过组合所有其他循环生成一组简单循环。这些并不一定是图中的所有简单循环。考虑下面的图表：

  A 
 / \ 
 B ----- C 
 $ / 
 
 $ / code> 

这里有3个简单循环：ABCA， BCDB和ABDCA。但是，您可以将其中每2个作为基础，并将3d作为2的组合来获得。这与有向图无法自由组合，因为需要观察边的方向有很大差异。

找到无向图的循环基的标准基线算法是这样的：构建一棵生成树，然后为每个不是树的一部分的边构建一个从该边开始的循环和树上的一些边缘。这样的循环必须存在，因为否则边将是树的一部分。

对于上面的示例图，一个生成树例如是这：

  A 
 / \ 
 BC 
 \ 
 D 
  

不在树中的2个边是BC和CD。对应的简单循环是A-B-C-A和A-B-D-C-A。

您也可以构建以下生成树：

  A 
 / 
 B ----- C 
 \ 
 D 
  

然后你得到的简单周期是ABCA和BCDB。

基线算法可以用不同的方式进行改进。就我所知，最好的改进属于Paton（K.Paton，An algorithm for finding a fundamental set of cycles for an undirected linear graph，Comm.ACM 12（1969），第514-518页）。 Java中的开源实现可以在这里找到： http://code.google.com/p/niographs/ 。

我应该提到如何将来自循环基础的简单循环组合起来以形成新的简单循环。你可以在任何（但是固定的）后面列出图表的所有边。然后，通过在属于循环的边的位置中放置一个零来表示循环，并且在不是循环的一部分的边的位置中放置零。然后你做序列的按位异或（XOR）。您进行XOR的原因是您想要排除属于两个循环的边，从而使联合循环非简单。您还需要通过检查序列的按位AND不全为零来检查2个周期是否有一些共同的边沿。否则，XOR的结果将是2个不相交的循环，而不是一个新的简单循环。

以上是上面示例图的示例：

我们首先列出边缘：（（AB），（AC），（BC），（BD），（CD））。然后，简单循环A-B-C-A，B-D-C-B和A-B-D-C-A被表示为（1,1,1,0,0），（0,0,1,1,1）和（1,1,0,1,1）。现在我们可以例如将XOR A-B-C-A与B-D-C-B进行比较，结果是（1,1,0,1,1），其正好是A-B-D-C-A。或者我们可以对结果是（0,0,1,1,1）进行XOR A-B-C-A和A-B-D-C-A。这就是B-D-C-B。

给定一个循环基数，你可以通过检查2个或更多个不同的基本循环的所有可能组合来发现所有简单循环。该过程在此处更详细地描述： http://dspace.mit.edu/bitstream/handle /1721.1/68106/FTL_R_1982_07.pdf 。

为了完整起见，我会注意到使用它似乎是可能的（并且效率低下）用于查找有向图的所有简单循环的算法。无向图的每一条边都可以被两条相反方向的边所取代。然后，有向图的算法应该可以工作。对于无向图的每条边将有1个假2-节点循环，这将不得不被忽略，并且无向图的每个简单循环将有顺时针和逆时针版本。用JAVA开发的用于查找有向图中所有周期的算法的实现可以在我已经引用的链接中找到。

I need a working algorithm for finding all simple cycles in an undirected graph. I know the cost can be exponential and the problem is NP-complete, but I am going to use it in a small graph (up to 20-30 vertices) and the cycles are small in number.

After a long research (mainly here) I still don't have a working approach. Here is a summary of my search:

Finding all cycles in an undirected graph

Cycles in an Undirected Graph -> detects only whether there is a cycle or not

Finding polygons within an undirected Graph -> very nice description, but no solution

Finding all cycles in a directed graph -> finds cycles only in directed graphs

Detect cycles in undirected graph using boost graph library

The only answer I found, which approaches my problem, is this one:

Find all cycles in graph, redux

It seems that finding a basic set of cycles and XOR-ing them could do the trick. Finding a basic set of cycles is easy, but I don't understand how to combine them in order to obtain all cycles in the graph...

解决方案

For an undirected graph the standard approach is to look for a so called cycle base : a set of simple cycles from which one can generate through combinations all other cycles. These are not necessarily all simple cycles in the graph. Consider for example the following graph:

    A 
  /   \
B ----- C
  \   /
    D

There are 3 simple cycles here : A-B-C-A, B-C-D-B and A-B-D-C-A. You can however take each 2 of these as a basis and obtain the 3d as a combination of the 2. This is a substantial difference from directed graphs where one can not combine so freely cycles due to the need to observe edge direction.

The standard baseline algorithm for finding a cycle base for an undirected graph is this : Build a spanning tree and then for each edge which is not part of the tree build a cycle from that edge and some edges on the tree. Such cycle must exist because otherwise the edge would be part of the tree.

For the sample graph above one spanning tree is e.g. this:

    A 
  /   \
B      C
  \ 
    D

The 2 edges not in the tree are B-C and C-D. And the correspondent simple cycles are A-B-C-A and A-B-D-C-A.

You can also build the following spanning tree:

    A 
  /   
B ----- C
  \   
    D

And then the simple cycles you get are A-B-C-A and B-C-D-B.

The baseline algorithm can be refined in different ways. To the best of my knowledge the best refinement belongs to Paton (K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518.). An open source implementation in Java is available here : http://code.google.com/p/niographs/ .

I should have mentioned how you combine simple cycles from the cycle base to form new simple cycles. You start off by listing in any (but fixed hereafter) order all edges of the graph. Then you represent cycles by sequences of zeros and ones by placing ones in the positions of edges which belong to the cycle and zeros in the positions of edges which are not part of the cycle. Then you do bitwise exclusive OR (XOR) of the sequences. The reason you do XOR is that you want to exclude edges which belong to both cycles and thus make the combined cycle non-simple. You need to check also that the 2 cycles have SOME common edges by checking that the bitwise AND of the sequences is not all zeros. Otherwise the result of XOR will be 2 disjoint cycles rather than a new simple cycle.

Here is an example for the sample graph above:

We start by listing the edges : ((AB), (AC), (BC), (BD), (CD)). Then the simple cycles A-B-C-A, B-D-C-B and A-B-D-C-A are represented as (1, 1, 1, 0, 0), (0, 0, 1, 1, 1) and (1, 1, 0, 1, 1). Now we can for example XOR A-B-C-A with B-D-C-B and the result is (1, 1, 0, 1, 1) which is exactly A-B-D-C-A. Or we can XOR A-B-C-A and A-B-D-C-A with the result being (0, 0, 1, 1, 1). Which is exactly B-D-C-B.

Given a cycle base you can discover all simple cycles by examining all possible combinations of 2 or more distinct base cycles. The procedure is described in more detail here : http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf on page 14.

For the sake of completeness, I would notice that it seems possible (and inefficient) to use algorithms for finding all simple cycles of a directed graph. Every edge of the undirected graph can be replaced by 2 directed edges going in opposite directions. Then algorithms for directed graphs should work. There will be 1 "false" 2-node cycle for every edge of the undirected graph which will have to be ignored and there will be a clockwise and a counterclockwise version of every simple cycle of the undirected graph. Open source implementation in Java of algorithms for finding all cycles in a directed graph can be found at the link I already quoted.

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