Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Enumerating cycles in a graph using Tarjan's algorithm

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.

Graph visualisation

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?

like image 365
janvdl Avatar asked Sep 17 '14 18:09

janvdl


1 Answers

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][:]:
like image 198
Peter de Rivaz Avatar answered Oct 06 '22 00:10

Peter de Rivaz