Enumerating cycles in a graph using Tarjan's algorithm

Question

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?

Hi Paul, I'm not entirely sure, but after checking the Wikipedia page on graph intervals, I think the answer is no, they're not the same. It's possible (I think) that the cycles within the graph could be seen as intervals of the graph, but the cycles will only be a subset of the intervals of the graph. I should note that there was a mistake in this code, the updated code is available at: https://github.com/janvdl/python_tarjan/blob/master/tarjan.py — janvdl, Dec 05 '14 at 06:02
For those interested in implementing this algorithm, the code above contains a mistake. I have both a Python (https://github.com/janvdl/python_tarjan/blob/master/tarjan.py) and Golang (https://github.com/janvdl/go_tarjan/blob/master/tarjan.go) implementation of Tarjan's available on my Github page, along with a Python implementation of Tiernan's algorithm (https://github.com/janvdl/python_tiernan/blob/master/tiernan.py) too. — janvdl, Jul 14 '15 at 09:33

score 6 · Accepted Answer · answered Sep 17 '14 at 19:11

6

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

answered Sep 17 '14 at 19:11

Peter de Rivaz

33,126
4
46
75

StackOverflow never disappoints. Thank you very much, you have saved me plenty of headaches! – janvdl Sep 17 '14 at 19:13
Hi, I would like to make a question: what is the 'g' flag used for? – Bruno Peixoto Jan 12 '22 at 13:05
In Tarjan's paper g is used to hold the return value from a recursive call of backtrack, which indicates if an elementary circuit continuing the partial path on the stack has been found (in which case vertices need to be unmarked because more cycles may be present). If you want more detail probably best to ask a new question. – Peter de Rivaz Jan 12 '22 at 20:43
@PeterdeRivaz - Asked a question about this vs. the algorithm version with low-link values and assigning indices on the fly! You seem to have deep expertise so I wanted to tag you :) – aksg87 Mar 27 '22 at 05:37

aksg87 · Answer 2 · 2022-03-27T05:26:42.847

I am a bit intrigued as I don't see the use of low-link values or assigning indexes on the fly as I thought is the case for Tarjan's Algorithm for finding SCC. Is this a different algorithm or a modification?

I renamed some of the variables to try to make this easier to understand:

G = [
    [1],
    [4, 6, 7],
    [4, 6, 7],
    [4, 6, 7],
    [2, 3],
    [2, 3],
    [5, 8],
    [5, 8],
    [],
    [],
]
# %%


def entry_tarjan(G_):

    G = G_.copy()

    marked = [False] * len(G_)
    cycles = []
    point_stack = []
    marked_stack = []

    def tarjan(src, v):
        nonlocal cycles, marked, G
        cycle_found = False
        point_stack.append(v)
        marked_stack.append(v)
        marked[v] = True

        for nei in G[v]:
            if nei < src:
                # prevent prior traversals
                G[nei] = []

            elif nei == src:
                # neighbor is source => cycle
                cycles.append(point_stack.copy())
                cycle_found = True

            elif marked[nei] == False:
                # dfs continues
                cycle_in_nei = tarjan(src, nei)
                cycle_found = cycle_found or cycle_in_nei

        if cycle_found == True:
            # adjust marked to current vertex
            while marked_stack[len(marked_stack) - 1] != v:
                u = marked_stack.pop()
                marked[u] = False
            marked_stack.pop()
            marked[v] = False

        point_stack.pop()
        return cycle_found

    for i in range(len(G)):
        # start at each vertex
        tarjan(i, i)

        while marked_stack:
            u = marked_stack.pop()
            marked[u] = False

    return cycles


print(entry_tarjan(G))

score -1 · Answer 3 · answered Jan 12 '22 at 14:00

The code below runs without an error and with expected output.

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

Output:

[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, 4]
[3, 6, 5]
[3, 7, 5]

Enumerating cycles in a graph using Tarjan's algorithm

3 Answers3

Linked