{"id":122,"date":"2019-12-17T09:30:46","date_gmt":"2019-12-17T07:30:46","guid":{"rendered":"http:\/\/jvdl.me\/wordpress\/?p=122"},"modified":"2019-12-17T09:30:46","modified_gmt":"2019-12-17T07:30:46","slug":"tarjans-cycle-enumeration-algorithm-python-implementation","status":"publish","type":"post","link":"https:\/\/jvdl.me\/blog\/?p=122","title":{"rendered":"Tarjan&#8217;s Cycle Enumeration Algorithm &#8211; Python Implementation"},"content":{"rendered":"\n<pre title=\"From my personal implementation which can be found at: https:\/\/github.com\/janvdl\/MSc-Enlarging-Directed-Graphs\/blob\/master\/tarjan.py\" class=\"wp-block-code\"><code lang=\"python\" class=\"language-python line-numbers\">from copy import deepcopy\n\nG = []\ncycles = []\n\npoint_stack = []\nmarked = []\nmarked_stack = []\n\ndef tarjan(s, v):\n    global cycles\n    f = False\n    point_stack.append(v)\n    marked[v] = True\n    marked_stack.append(v)\n    for w in G[v]:\n        if w &lt; s:\n            G[w] = []\n        elif w == s:\n            points_keeper = list(deepcopy(point_stack))\n            if points_keeper not in cycles:\n                cycles.append(points_keeper)\n            f = True\n        elif marked[w] == False:\n            g = tarjan(s,w)\n            f = f or g\n\n    if f == True:\n        while marked_stack[len(marked_stack) - 1] != v:\n            u = marked_stack.pop()\n            marked[u] = False\n        marked_stack.pop()\n        marked[v] = False\n\n    point_stack.pop()\n    return f\n\ndef entry_tarjan(G_):\n    global G, cycles, marked, marked_stack, point_stack\n    G = []\n    cycles = []\n\n    point_stack = []\n    marked = []\n    marked_stack = []\n\n    G = deepcopy(G_)\n\n    marked = [False for x in xrange(0, len(G_))]\n\n    for i in range(len(G)):\n        tarjan(i, i)\n        while marked_stack:\n            u = marked_stack.pop()\n            marked[u] = False\n\n    return cycles<\/code><\/pre>\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-122","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\/122","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=122"}],"version-history":[{"count":1,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/posts\/122\/revisions"}],"predecessor-version":[{"id":123,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=\/wp\/v2\/posts\/122\/revisions\/123"}],"wp:attachment":[{"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jvdl.me\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}