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) val (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) ccs (contains? used (first s)) (recur reversed (rest s) ccs used) :else (let [cc (reduce-dfs-postorder-graph reversed #(if (contains? used %1) %2 (cons %1 %2)) nil (first s))] (recur (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.

## Comments