Skip to content

Instantly share code, notes, and snippets.

@cgrand
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
Save cgrand/5188919 to your computer and use it in GitHub Desktop.
Implementing Tarjan in Clojure, step by step
;; Now, replace the loop by more telling operations.
(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
(let [nodes (::stack env)
scc (set (take (- (count nodes) n) nodes))
env (reduce #(assoc %1 %2 nil) env scc)] ; clear all stack lengths for these nodes since this SCC is done
(assoc env ::stack stack ::sccs (conj (::sccs env) scc)))
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}}
@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