Skip to content →

Strongly Connected Components in (mostly?) idiomatic Clojure

A friend asked how to find strongly connected components in a graph in idiomatic Clojure. This is what I came up with:

(defn edge-list [g] 
  (mapcat (fn [[k v]] (map (partial vector k) v)) g)) 
(defn reverse-graph [g] 
  (reduce (fn [rev [from to]] (assoc rev to (cons from (get rev to)))) 
	  {} (edge-list g))) 
(import '(java.util HashSet))
(defn reduce-dfs-postorder-graph 
  ([g f init-val root] 
     (reduce-dfs-postorder-graph g f init-val root (HashSet.)))
  ([g f init-val root #^java.util.HashSet visited]
     (.add visited root)
     (f root (reduce (fn [val node] 
		       (if (.contains visited node) 
			 (reduce-dfs-postorder-graph g f val node visited))) 
		     init-val (get g root)))))
(defn kosaraju [g]
  (loop [reversed (reverse-graph g), 
	 s (reduce-dfs-postorder-graph g cons nil (ffirst g)), 
	 ccs nil, 
	 used #{}]
    (cond (empty? s)                 
	  (contains? used (first s)) 
            (recur reversed (rest s) ccs used)
            (let [cc (reduce-dfs-postorder-graph 
		      #(if (contains? used %1) %2 (cons %1 %2)) 
		      (first s))]
	       (apply dissoc reversed cc) 
	       (rest s) 
	       (cons cc ccs) 
	       (clojure.set/union used cc))))))
user> (kosaraju {:a '(:b :c) :b '(:c) :c '(:a :d) :d '(:e) :e '()})
((:e) (:d :c :b :a))

The only non-idiomatic part might be the use of a mutable HashMap in the reduce-dfs function. I used it because it makes the code clearer and faster than with immutable clojure maps; moreover, the mutability is safe since it’s all hidden within the execution of the function. But, I’m not sure if more seasoned users would share my aesthetic here.

Published in Clojure


Leave a Reply

Your email address will not be published. Required fields are marked *