tarjan.clj

## tarjan.clj
;; 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}}