Tarjan’s strongly connected components algorithm

unsorted — cgrand, 18 March 2013 @ 19 h 48 min

I dislike algorithms that are full of indices and mutations. Not because they are bad but because I always have the feeling that the core idea is buried. As such, Tarjan’s SCC algorithm irked me.

So I took the traditional algorithm, implemented it in Clojure with explicit environment passing, then I replaced indices by explicit stacks (thanks to persistence!) and after some tweaks, I realized that I’ve gone full circle and could switch to stacks lengths instead of stacks themselves and get rid of the loop. However the whole process made the code cleaner to my eye. You can look at the whole history.

Here is the resulting code:

(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
            (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))
                        ; clear all stack lengths for these nodes since this SCC is done
                        env (reduce #(assoc %1 %2 nil) env scc)]
                    (assoc env ::stack stack ::sccs (conj (::sccs env) scc)))
                  env))))]
    (::sccs (reduce sc {::stack () ::sccs #{}} nodes))))

As always, if you need some short-term help with Clojure (code review, consulting, training etc.), contact me!

12 Comments »

  1. Hi,

    Interesting article as always!

    The link to “Tarjan’s SCC algorithm” is broken. I guess you meant to use http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm .

    – Max

    Comment by mpenet — 18 March 2013 @ 21 h 54 min
  2. @Max link fixed, thanks!

    Comment by cgrand — 19 March 2013 @ 12 h 02 min
  3. Any example usage? like if I invoked it like this: (tarjan {:a [:b :c] :b [:c] :c [:a] :d [:e] :e [:a]} :e) …is it right?

    Comment by Lee Wei — 1 October 2014 @ 11 h 39 min
  4. One of the nice things about Tarjan’s algorithm is that its output is topologically sorted. Would it be possible to change yours to achieve that as well?

    Comment by Eduardo — 2 September 2015 @ 19 h 44 min
  5. I suspect a bug.

    Testcase: (tarjan [:a :b :c] {:a #{:b :c} :b #{:a} :c #{:a}})
    Expected: #{#{:a :b} #{:a :c}}
    Result: #{#{:c :b :a}}

    Comment by Niels IJsselstein — 15 December 2015 @ 20 h 54 min
  6. My mistake, no bug…

    Comment by Niels IJsselstein — 15 December 2015 @ 21 h 09 min
  7. djn ndac bvmfs bhkvnfavs bhn

    Comment by neymar — 3 January 2024 @ 2 h 33 min
  8. 3kmklfw r egjnorfjnwfjnrwf knfg nrwnfk fs nkvfs njnwkefjnketjnhkjnkwda s kqwfnw hnvhjfhj

    Comment by ANGELA — 7 January 2024 @ 12 h 36 min
  9. u9ijknewd nwefuirjnkdfsuijnk2r4ewfduijnk35wrioefujk35tbrjhwfd bn bjhb 3nrwfds jhwfjh nyh5jterjk2nemwd bjhewdjh erfjkdn

    Comment by Chief J — 11 January 2024 @ 1 h 28 min
  10. u2ejw nkdfasbhisdjqwhib rendfscbjhk ad bjbwfsv bhknwrefjnkwfbjhks m
    efdbjhn dasbjc dbhisd fncbjhd fbjhk fsbvhjd nabjhsdfbjh bjmsd nds
    sjnk edfbjhcx bhirnfsbhkj ncejilhsfnkcbjhknwdfbhsjn

    Comment by galado — 13 January 2024 @ 15 h 01 min
  11. y78y9uji453rhit5br4bht4ghtr4gefbhibht5bhrbhtbhrebhrbuht5hrh
    uht4gbthjtjbhjgtbh4efg bjtrbjhtg4 brfg jbhjtgjrefbjht4g bj jgrf bjhgr jbgrf
    tg jntrgefjt4gjefbhtg4befbjhrf

    Comment by Melo D — 16 January 2024 @ 13 h 58 min
  12. j4iterfn j3treifnsd bn t4efh j tge jt4gefh5ytjrge fjnt4 rjnt4hrgj n5yrgfd
    tefjb4nterf nj4ngerfj nt4 gje t4nt54re jt4gefn jnt45e fnhitn jegf n3r b4tgeb
    3rfjn3r jn3wfdnefv jnefjdj nrefjdn hwbr3hbut4erhbrubht4gefhubrghrf je fb bgtef

    Comment by Treasure — 23 January 2024 @ 8 h 56 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2024 Clojure and me | powered by WordPress with Barecity