topsort.clj

;; https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
(defn topsort [g]
  (let [l (atom ())
        marks (atom (zipmap (keys g) (repeat nil)))
        visit (fn visit [n]
                (case (@marks n)
                  :perm nil
                  :temp (throw (IllegalArgumentException. "Not a DAG"))
                  (do
                    (swap! marks assoc n :temp)
                    (run! visit (g n))
                    (swap! marks assoc n :perm)
                    (swap! l conj n))))]
    (while (->> @marks vals (some nil?))
      (let [n (->> @marks (filter (comp nil? val)) ffirst)]
        (visit n)))
    @l))