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.

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?

Smalltime

Is this the same thing as graph interval analysis? – Unrivaled

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: github.com/janvdl/python_tarjan/blob/master/tarjan.py – Smalltime

For those interested in implementing this algorithm, the code above contains a mistake. I have both a Python (github.com/janvdl/python_tarjan/blob/master/tarjan.py) and Golang (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 (github.com/janvdl/python_tiernan/blob/master/tiernan.py) too. – Smalltime

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

Josephjosepha

StackOverflow never disappoints. Thank you very much, you have saved me plenty of headaches! – Smalltime

Hi, I would like to make a question: what is the 'g' flag used for? – Teleology

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. – Josephjosepha

@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 :) – Polyclinic

Answer 2

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

Polyclinic

Answer 3

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]

Teleology