{"id":119,"date":"2019-12-17T09:28:08","date_gmt":"2019-12-17T07:28:08","guid":{"rendered":"http:\/\/jvdl.me\/wordpress\/?p=119"},"modified":"2019-12-17T09:28:08","modified_gmt":"2019-12-17T07:28:08","slug":"tarjans-cycle-enumeration-algorithm-go-implementation","status":"publish","type":"post","link":"https:\/\/jvdl.me\/blog\/?p=119","title":{"rendered":"Tarjan&#8217;s Cycle Enumeration Algorithm &#8211; Go Implementation"},"content":{"rendered":"\n<pre title=\"From my personal implementation which can be found at: https:\/\/github.com\/janvdl\/go_tarjan\/blob\/master\/tarjan.go\" class=\"wp-block-code\"><code lang=\"go\" class=\"language-go line-numbers\">package main\n\nimport \"fmt\"\n\nvar (\n\tG            [][]int\n\tpoint_stack  []int\n\tmarked       []bool\n\tmarked_stack []int\n)\n\nfunc main() {\n\t\/\/Example graph - adjacency list\n\tG = [][]int{[]int{1}, []int{10}, []int{0}, []int{0}, []int{3}, []int{8}, []int{9}, []int{4, 5}, []int{2}, []int{6}, []int{7}}\n\tentry_tarjan(G)\n}\n\nfunc entry_tarjan(G [][]int) {\n\tmarked = make([]bool, len(G))\n\n\tfor i := 0; i &lt; len(G); i++ {\n\t\ttarjan(i, i)\n\t\tfor len(marked_stack) > 0 {\n\t\t\tu := marked_stack[len(marked_stack)-1]\n\t\t\tmarked_stack = marked_stack[:len(marked_stack)-1]\n\t\t\tmarked[u] = false\n\t\t}\n\t}\n}\n\nfunc tarjan(s int, v int) bool {\n\tf := false\n\tpoint_stack = append(point_stack, v)\n\tmarked[v] = true\n\tmarked_stack = append(marked_stack, v)\n\n\tfor _, w := range G[v] {\n\t\tcb := make(chan bool, len(G[v]))\n\t\tgo branch(s, v, w, cb)\n\t\tf = &lt;-cb\n\t}\n\n\tif f == true {\n\t\tfor marked_stack[len(marked_stack)-1] != v {\n\t\t\tu_ := marked_stack[len(marked_stack)-1]\n\t\t\tmarked_stack = marked_stack[:len(marked_stack)-1]\n\t\t\tmarked[u_] = false\n\t\t}\n\t\tmarked_stack = marked_stack[:len(marked_stack)-1]\n\t\tmarked[v] = false\n\t}\n\n\tpoint_stack = point_stack[:len(point_stack)-1]\n\treturn f\n}\n\nfunc branch(s int, v int, w int, cb chan bool) {\n\tf_ := false\n\tif w &lt; s {\n\t\tG[w] = []int{}\n\t} else if w == s {\n\t\tfmt.Println(point_stack)\n\t\tf_ = true\n\t} else if marked[w] == false {\n\t\tg_ := tarjan(s, w)\n\t\tf_ = f_ || g_\n\t}\n\n\tcb &lt;- f_\n}<\/code><\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,53],"tags":[],"class_list":["post-119","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-programming"],"_links":{"self":[{"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/posts\/119","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=119"}],"version-history":[{"count":2,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/posts\/119\/revisions"}],"predecessor-version":[{"id":121,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/posts\/119\/revisions\/121"}],"wp:attachment":[{"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}