使用Tarjan算法枚举图形中的循环 [英] Enumerating cycles in a graph using Tarjan's algorithm

问题描述

我正在尝试使用Tarjan的算法确定有向图的循环，该算法在1972年9月发表在他的研究论文有向图的基本电路的枚举中。

我正在使用Python编写算法代码，并使用邻接表来跟踪节点之间的关系。

因此，在下面的 G中，节点0指向节点1，节点1指向到节点4,6,7 ...等。

  G = [[1]，[4，6，7] ，[4、6、7]，[4、6、7]，[2、3]，[2、3]，[5、8]，[5、8]，[]，[]] 
 N = len（G）
 
点= [] 
标记堆栈= [] 
标记= [xrange（0，N）中x的错误] 
 
g =无
 def tarjan（s，v，f）：
全局g 
 points.append（v）
marked_stack.append（v）
marked [v] = G [v]中w的真
 
：如果w< s：
 G [v] .pop（G [v] .index（w））
 elif w == s：
打印点
f =真
 elif marked [w] == False：
如果f == g和f == False：
f = False 
 else：
f = True 
 tarjan（s，w ，g）
 
g = f 
 
如果f == True：
u = marked_stack.pop（）
 while（u！= v）：
marked [u] = False 
u = marked_stack.pop（）
 #v现在已从标记堆叠中删除，并且被称为u 
 #unmark v 
marked [ u] =错误的
 points.pop（points.index（v））
 
 for xrange（0，N）中的i：
被标记为[i] =错误的
在我xrange（0，N）中的
：
点= [] 
 tarjan（i，i，False）
而（len（marked_stack）> 0）： 
u = marked_stack.pop（）
marked [u] =假
  

Tarjan's算法检测s以下循环：

[2，4]

[2， 4，3，6，5]

[2，4，3，7，5]

[ 2，6，5]

[2，6，5，3，4]

[2， 7，5]

[2，7，5，5，3，4]

[3，7， 5]

我也完成了Tiernan的算法，（正确地）找到了2个额外周期：

[3,4]

[3,6,5]

我非常感谢您能找到Tarjan跳过这两个周期的任何帮助。也许我的代码有问题？

解决方案

在这些行中：

<$ G [v]中w的p $ p> ：如果w< s：
G [v] .pop（G [v] .index（w））


您正在遍历列表并从中弹出元素。

如果更改代码以复制列表，则会产生额外的循环：

  for G [v] [：]：
  

I'm trying to determine the cycles in a directed graph using Tarjan's algorithm, presented in his research paper "Enumeration of the elementary circuits of a directed graph" from Septermber 1972.

I'm using Python to code the algorithm, and an adjacency list to keep track of the relationships between nodes.

So in "G" below, node 0 points to node 1, node 1 points to nodes 4,6,7... etc.

G = [[1], [4, 6, 7], [4, 6, 7], [4, 6, 7], [2, 3], [2, 3], [5, 8], [5, 8], [], []]
N = len(G)

points = []
marked_stack = []
marked = [False for x in xrange(0,N)]

g = None
def tarjan(s, v, f):
    global g
    points.append(v)
    marked_stack.append(v)
    marked[v] = True

    for w in G[v]:
        if w < s:            
            G[v].pop(G[v].index(w))
        elif w == s:
            print points
            f = True
        elif marked[w] == False:
            if f == g and f == False:
                f = False
            else:
                f = True
            tarjan(s, w, g)

    g = f

    if f == True:
        u = marked_stack.pop()
        while (u != v):
            marked[u] = False
            u = marked_stack.pop()
        #v is now deleted from mark stacked, and has been called u
        #unmark v
        marked[u] = False
    points.pop(points.index(v))

for i in xrange(0,N):
    marked[i] = False

for i in xrange(0,N):
    points = []
    tarjan(i,i, False)
    while (len(marked_stack) > 0):
        u = marked_stack.pop()
        marked[u] = False

Tarjan's algorithm detects the following cycles:

[2, 4]

[2, 4, 3, 6, 5]

[2, 4, 3, 7, 5]

[2, 6, 5]

[2, 6, 5, 3, 4]

[2, 7, 5]

[2, 7, 5, 3, 4]

[3, 7, 5]

I've also done Tiernan's algorithm, and it (correctly) finds 2 extra cycles:

[3,4]

[3,6,5]

I'd appreciate any help in finding out why Tarjan skips over those 2 cycles. A problem in my code perhaps?

解决方案

In these lines:

for w in G[v]:
    if w < s:            
        G[v].pop(G[v].index(w))

you are iterating through a list and popping elements from it. This stops the iteration from working as expected.

If you change the code to make a copy of the list it produces the extra cycles:

for w in G[v][:]:

这篇关于使用Tarjan算法枚举图形中的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！