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