Last active
November 18, 2020 03:08
-
-
Save cgrand/5188919 to your computer and use it in GitHub Desktop.
Implementing Tarjan in Clojure, step by step
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; Relaize that only the stack size matters, env now maps nodes to "low" or nil. | |
(defn tarjan | |
"Returns the strongly connected components of a graph specified by its nodes | |
and a successor function succs from node to nodes. | |
The used algorithm is Tarjan's one." | |
[nodes succs] | |
(letfn [(sc [env node] | |
; env is a map from nodes to stack length or nil, nil means the node is known to belong to another SCC | |
; there are two special keys: ::stack for the current stack and ::sccs for the current set of SCCs | |
#_{:post [(contains? % node)]} | |
(if (contains? env node) | |
env | |
(let [stack (::stack env) | |
n (count stack) | |
env (assoc env node n ::stack (conj stack node)) | |
env (reduce (fn [env succ] | |
(let [env (sc env succ)] | |
(assoc env node (min (or (env succ) n) (env node))))) | |
env (succs node))] | |
(if (= n (env node)) ; no link below us in the stack, call it a SCC | |
(loop [scc #{} nodes (::stack env) env env] | |
(let [curr (peek nodes) | |
scc (conj scc curr) | |
env (assoc env curr nil)] ; clear all stack lengths for this SCC's nodes since this SCC is done | |
(if (= curr node) | |
(assoc env ::stack stack ::sccs (conj (::sccs env) scc)) | |
(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
@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.