Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# cgrand/tarjan.clj

Last active Nov 18, 2020
Implementing Tarjan in Clojure, step by step
 ;; 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}}

### 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.
to join this conversation on GitHub. Already have an account? Sign in to comment