Skip to content

Instantly share code, notes, and snippets.

@cgrand
Last active November 18, 2020 03:08
Show Gist options
  • Save cgrand/5188919 to your computer and use it in GitHub Desktop.
Save cgrand/5188919 to your computer and use it in GitHub Desktop.
Implementing Tarjan in Clojure, step by step
;; switch to explicit lists, instead of implicit chaining
;; the explicit list is the the "lowest" stack so :low is not needed anymore
(defn tarjan [nodes succs]
(letfn [(sc [env node]
(if (env node)
env
(let [prevs (::prevs env)
env (assoc env node {:prevs prevs}
::prevs (conj prevs node))
env (reduce (fn [env succ]
(let [env (sc env succ)
prevs (:prevs (env succ) prevs)]
(update-in env [node :prevs]
(partial min-key count) prevs)))
env (succs node))
prevs' (:prevs (env node))]
(if (= prevs prevs')
(loop [scc #{} nodes (::prevs env) env env]
(let [curr (peek nodes)
scc (conj scc curr)
env (update-in env [curr] dissoc :prevs)]
(if (= curr node)
(-> env
(update-in [::sccs] conj scc)
(assoc ::prevs prevs))
(recur scc (pop nodes) env))))
env))))]
(::sccs (reduce sc {::prevs () ::sccs #{}} nodes))))
=> (def g {:c #{:d} :a #{:b :c} :b #{:a :c}})
=> (tarjan (keys g) g)
#{#{:c} #{:d} #{:a :b}}
@xsc
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