我需要一个工作算法来查找无向图中的所有简单循环 . 我知道成本可能是指数级的,问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少 .
经过长时间的研究(主要是在这里),我仍然没有工作方法 . 以下是我的搜索摘要:
Finding all cycles in an undirected graph
Cycles in an Undirected Graph - >仅检测是否存在循环
Finding polygons within an undirected Graph - >非常好的描述,但没有解决方案
Finding all cycles in a directed graph - >仅在有向图中查找周期
Detect cycles in undirected graph using boost graph library
我发现的唯一一个解决我问题的答案是:
Find all cycles in graph, redux
似乎找到一组基本循环并对它们进行异或可以做到这一点 . 找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...
10 回答
对于无向图,标准方法是寻找所谓的循环基:一组简单循环,人们可以通过组合生成所有其他循环 . 这些不一定是图中的所有简单循环 . 考虑以下图表:
这里有3个简单的循环:A-B-C-A,B-C-D-B和A-B-D-C-A . 然而,您可以将这两个中的每一个作为基础,并将第三个作为2的组合获得 . 这与有向图形的实质差异在于,由于需要观察边缘方向,因此无法组合如此自由的周期 .
用于查找无向图的循环基础的标准基线算法是:构建生成树,然后对于不属于树的每个边构建从该边创建循环和树上的一些边 . 必须存在这样的循环,否则边缘将是树的一部分 .
例如,上面示例图的一个可能的生成树是这样的:
不在树中的2个边是B-C和C-D . 相应的简单循环是A-B-C-A和A-B-D-C-A .
您还可以构建以下生成树:
对于这个生成树,简单的循环是A-B-C-A和B-C-D-B .
可以以不同方式细化基线算法 . 据我所知,最佳细化属于Paton(K.Paton,一种用于寻找无向线性图的基本循环集的算法,Comm.ACM 12(1969),pp.514-518 . ) . 这里有一个Java开源实现:http://code.google.com/p/niographs/ .
我应该提到如何将循环基础中的简单循环组合成新的简单循环 . 您首先列出图表的所有边缘(但在此后修复) . 然后通过将0和1的序列放置在属于循环的边缘位置和在不属于循环的边缘位置的零的位置来表示循环 . 然后,您对序列进行按位异或(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) . 现在我们可以例如使用B-D-C-B的XOR A-B-C-A,结果是(1,1,0,1,1),它恰好是A-B-D-C-A . 或者我们可以异或A-B-C-A和A-B-D-C-A,结果为(0,0,1,1,1) . 这正是B-D-C-B .
给定循环基础,您可以通过检查2个或更多不同基本循环的所有可能组合来发现所有简单循环 . 此处详细介绍了该过程:第14页的http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .
为了完整起见,我会注意到使用算法来查找有向图的所有简单循环似乎是可能的(并且效率低下) . 无向图的每个边都可以被相反方向的2个有向边代替 . 然后有向图的算法应该有效 . 对于无向图的每个边缘将存在1个“假”2节点循环,其将被忽略,并且将存在无向图的每个简单循环的顺时针和逆时针版本 . 用于在有向图中查找所有周期的算法的Java开源实现可以在我已经引用的链接中找到 .
以下是基于深度优先搜索的C#(和Java,请参见答案结尾)的演示实现 .
外部循环扫描图形的所有节点,并从每个节点开始搜索 . 节点邻居(根据边缘列表)被添加到循环路径中 . 如果不能添加更多未访问的邻居,则递归结束 . 如果路径长于两个节点并且下一个邻居是路径的开始,则找到新的循环 . 避免重复循环,通过将最小节点旋转到开始来对循环进行归一化 . 反向排序的周期也被考虑在内 .
这只是一个天真的实现 . 经典论文是:Donald B. Johnson . 找到有向图的所有基本电路 . SIAM J. Comput . ,4(1):77-84,1975 .
可以找到最近对现代算法的调查here
演示图的周期:
用Java编码的算法:
Axel,我已经将你的代码翻译成了python . 大约1/4的代码行和更清晰的阅读 .
这里只是一个非常蹩脚的MATLAB版本,该算法改编自上面的python代码,适用于任何可能需要它的人 .
灵感来自@LetterRip和@Axel Kemper这是Java的缩写版本:
这是上面的python代码的C版本:
这是上面python代码的vb .net版本:
结束模块
上面的循环查找器似乎有一些问题 . C#版本找不到一些周期 . 我的图是:
例如,找不到循环:
1-9-3-12-5-10
. 我也尝试了C版本,它返回非常大(数千万)个循环次数,这显然是错误的 . 它可能无法匹配周期 .对不起,我有点紧张,我没有进一步调查 . 我根据Nikolay Ognyanov的帖子写了我自己的版本(非常感谢您的帖子) . 对于上图,我的版本返回8833个周期,我正在尝试验证它是否正确 . C#版本返回8397个周期 .
这是python代码的节点版本 .
Matlab版本遗漏了一些东西,函数findNewCycles(path)应该是:
function findNewCycles(path)