Enumerating cycles in a graph using Tarjan's a

问题:

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?

回答1:

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][:]: