Skip to content

Instantly share code, notes, and snippets.

Last active November 18, 2020 03:08
  • Star 8 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Implementing Tarjan in Clojure, step by step
;; initial translation, with an implicit list through ::top and :prev chaining
;; env maps from nodes to {:low n :prev other-node} -- to the exceptions of special keys
(defn tarjan [nodes succs]
(letfn [(sc [env node]
(if (env node)
(let [n (::next env)
env (assoc env node {:low n :prev (::top env)}
::next (inc n) ::top node)
env (reduce (fn [env succ]
(let [env (sc env succ)
low (:low (env succ) n)]
(update-in env [node :low] min low)))
env (succs node))
low (:low (env node))]
(if (= n low)
(loop [scc #{} curr (::top env) env env]
(let [scc (conj scc curr)
prev (:prev (env curr))
env (update-in env [curr] dissoc :low)]
(if (= curr node)
(-> env
(update-in [::sccs] conj scc)
(assoc ::top prev))
(recur scc prev env))))
(::sccs (reduce sc {::top ::bottom ::next 0 ::sccs #{}} nodes))))
=> (def g {:c #{:d} :a #{:b :c} :b #{:a :c}})
=> (tarjan (keys g) g)
#{#{:c} #{:d} #{:a :b}}
Copy link

xsc commented Nov 4, 2016

@cgrand Thank you for this! Would you consider adding a license (maybe MIT?) to this gist?
I'd like to use your implementation in a library but without a license that's not possible.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment