Topological Sort in Clojure

topological_sort.clj

(ns tnoda.algorithm.topological-sort
  (:import (java.util LinkedList BitSet Stack))
  (:use clojure.test))

(defn- dfs-forest!
  [g ^LinkedList order ^BitSet discovered ^Stack stack ^BitSet on-stack]
  (letfn [(discover
            [u]
            (let [adjacencies (g u)]
              (when (not-any? #(.get on-stack %) adjacencies)
                (.set discovered u)
                (.push stack [u finish])
                (.set on-stack u)
                (doseq [v (remove #(.get discovered %) adjacencies)]
                  (.push stack [v discover]))
                :discovered)))
          (finish
            [u]
            (.clear on-stack u)
            (.addFirst order u)
            :finished)]
    (fn dff!
      [u]
      (.push stack [u discover])
      (loop []
        (if (.empty stack)
          :finished
          (let [[v f] (.pop stack)]
            (and (f v) (recur))))))))

(defn topological-sort
  [g n]
  (let [order (LinkedList.)
        discovered (BitSet. n)
        stack (Stack.)
        on-stack (BitSet. n)
        dff! (dfs-forest! g order discovered stack on-stack)
        discovered? #(.get discovered %)]
    (loop [u 0]
      (if (< u n)
        (if (or (discovered? u) (dff! u))
          (recur (inc u)))
        order))))

(deftest test-topological-sort
  (is (= [8 7 2 3 0 1 5 6 4 9 10 11 12]
         (topological-sort (reduce (fn [m [u v]]
                                     (assoc m u (-> m (get u #{}) (conj v))))
                                   {}
                                   (partition 2 [2 3
                                                 0 6
                                                 0 1
                                                 2 0
                                                 11 12
                                                 9 12
                                                 9 10
                                                 9 11
                                                 3 5
                                                 8 7
                                                 5 4
                                                 0 5
                                                 6 4
                                                 6 9
                                                 7 6]))
                           13))))