Implementing Tarjan in Clojure, step by step
;; having a map with only one entry is a bit of a waste, so env now directly maps a node | |
;; to a "lowest" stack or nil if not "on stack" anymore | |
(defn tarjan [nodes succs] | |
(letfn [(sc [env node] | |
(if (contains? env node) | |
env | |
(let [stack (::stack env) | |
env (assoc env node stack ::stack (conj stack node)) | |
env (reduce (fn [env succ] | |
(let [env (sc env succ)] | |
(if-let [stack (env succ)] | |
(assoc env node | |
(min-key count stack (env node))) | |
env))) | |
env (succs node))] | |
(if (= stack (env node)) | |
(loop [scc #{} nodes (::stack env) env env] | |
(let [curr (peek nodes) | |
scc (conj scc curr) | |
env (assoc env curr nil)] | |
(if (= curr node) | |
(-> env | |
(update-in [::sccs] conj scc) | |
(assoc ::stack stack)) | |
(recur scc (pop nodes) env)))) | |
env))))] | |
(::sccs (reduce sc {::stack () ::sccs #{}} nodes)))) | |
=> (def g {:c #{:d} :a #{:b :c} :b #{:a :c}}) | |
=> (tarjan (keys g) g) | |
#{#{:c} #{:d} #{:a :b}} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
@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.