Estoy tratando de determinar los ciclos en un gráfico dirigido usando el algoritmo de Tarjan, presentado en su trabajo de investigación "Enumeración de los circuitos elementales de un gráfico dirigido" de septiembre de 1972.

Estoy usando Python para codificar el algoritmo y una lista de adyacencia para realizar un seguimiento de las relaciones entre los nodos.

Entonces, en "G" a continuación, el nodo 0 apunta al nodo 1, el nodo 1 apunta a los nodos 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

El algoritmo de Tarjan detecta los siguientes ciclos:

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

También hice el algoritmo de Tiernan, y (correctamente) encuentra 2extra ciclos:

[3,4]

[3,6,5]

Agradecería cualquier ayuda para descubrir por qué Tarjan omite esos 2 ciclos. ¿Un problema en mi código quizás?