Tarjan’s Cycle Enumeration Algorithm – Python Implementation

from copy import deepcopy

G = []
cycles = []

point_stack = []
marked = []
marked_stack = []

def tarjan(s, v):
    global cycles
    f = False
    point_stack.append(v)
    marked[v] = True
    marked_stack.append(v)
    for w in G[v]:
        if w < s:
            G[w] = []
        elif w == s:
            points_keeper = list(deepcopy(point_stack))
            if points_keeper not in cycles:
                cycles.append(points_keeper)
            f = True
        elif marked[w] == False:
            g = tarjan(s,w)
            f = f or g

    if f == True:
        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 f

def entry_tarjan(G_):
    global G, cycles, marked, marked_stack, point_stack
    G = []
    cycles = []

    point_stack = []
    marked = []
    marked_stack = []

    G = deepcopy(G_)

    marked = [False for x in xrange(0, len(G_))]

    for i in range(len(G)):
        tarjan(i, i)
        while marked_stack:
            u = marked_stack.pop()
            marked[u] = False

    return cycles

Tarjan’s Cycle Enumeration Algorithm – Go Implementation

package main

import "fmt"

var (
	G            [][]int
	point_stack  []int
	marked       []bool
	marked_stack []int
)

func main() {
	//Example graph - adjacency list
	G = [][]int{[]int{1}, []int{10}, []int{0}, []int{0}, []int{3}, []int{8}, []int{9}, []int{4, 5}, []int{2}, []int{6}, []int{7}}
	entry_tarjan(G)
}

func entry_tarjan(G [][]int) {
	marked = make([]bool, len(G))

	for i := 0; i < len(G); i++ {
		tarjan(i, i)
		for len(marked_stack) > 0 {
			u := marked_stack[len(marked_stack)-1]
			marked_stack = marked_stack[:len(marked_stack)-1]
			marked[u] = false
		}
	}
}

func tarjan(s int, v int) bool {
	f := false
	point_stack = append(point_stack, v)
	marked[v] = true
	marked_stack = append(marked_stack, v)

	for _, w := range G[v] {
		cb := make(chan bool, len(G[v]))
		go branch(s, v, w, cb)
		f = <-cb
	}

	if f == true {
		for marked_stack[len(marked_stack)-1] != v {
			u_ := marked_stack[len(marked_stack)-1]
			marked_stack = marked_stack[:len(marked_stack)-1]
			marked[u_] = false
		}
		marked_stack = marked_stack[:len(marked_stack)-1]
		marked[v] = false
	}

	point_stack = point_stack[:len(point_stack)-1]
	return f
}

func branch(s int, v int, w int, cb chan bool) {
	f_ := false
	if w < s {
		G[w] = []int{}
	} else if w == s {
		fmt.Println(point_stack)
		f_ = true
	} else if marked[w] == false {
		g_ := tarjan(s, w)
		f_ = f_ || g_
	}

	cb <- f_
}