Enumerating cycles in a graph using the Tarjan algorithm

Question

I am trying to determine the cycles in a directed graph using the Taryan algorithm presented in his research article "Enumeration of elementary schemes of a directed graph" from Septermber 1972.

I use Python to code the algorithm and an adjacency list to track the connections between nodes.

So, in the “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 

The Tarhan 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 also executed the Tiernan algorithm, and it (correctly) finds 2 additional cycles:

[3,4]

[3,6,5]

I would appreciate help in figuring out why Taryan skips these 2 cycles. Perhaps the problem is in my code?

Answer 1

In these lines:

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

you repeat the list and pop out items from it. This stops the iteration from working as expected.

If you change the code to create a copy of the list, it will perform additional loops:

 for w in G[v][:]: