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_
}
Filed under: Computer Science,Programming - @ December 17, 2019 09:28