Topological sort in Clojure

Several years ago I needed a topological sort in Clojure, and I recall copying the one from Rosetta Code. Looking at the original code again, I was surprised by how verbose it was, since the algorithm I've been using since is just this:

(defn topological-sort [graph]
  (when (seq graph)
    (when-let [depless (seq (keep (fn [[k v]]
                                    (when (empty? v) k))
                                  graph))]
      (concat depless
              (topological-sort
                (into {}
                      (map (fn [[k v]]
                             [k (apply disj v depless)]))
                      (apply dissoc graph depless)))))))

(topological-sort
  {:a #{:b :c :d}
   :b #{:c :d}
   :c #{:d :e}
   :d #{}
   :e #{:d}})

(:d :e :c :b :a)

My version isn't as full featured as the one on Rosetta Code. It takes a few shortcuts, such as assuming all items to sort are included as keys in the map, even if they have no dependencies of their own. It's also not tail recursive, so large dependency graphs could hit stack limits.

Beyond taking shortcuts, some of the above succinctness comes from not giving sub-operations names such as no-dep-items and remove-items. That does make the code harder for initiates to comprehend, but I've often found it easier to understand code that's together in one place than code that's broken out into simpler functions but which introduces a layer of indirection, and the sub-components aren't too long to distract from the overall function.

I usually need to adapt this code to a particular use case, so it's helpful to have everything in one function and break pieces out after making changes, rather than gathering up all the necessary functions, copying, pasting, then possibly re-combining the functions so I can break them out differently. The above function is, in a sense, mid-refactor, which allows me to use it as a template for more specific scenarios. I've even used it as the basis for implementing topological sort in a different programming language.

The code is also so brief because I adapted it from a version that was short enough to post to Twitter. What's shown above is about twice as long as Twitter allows, mainly due to indentation adding so many whitespace characters. Here's a version that is short enough:

(defn topo-sort [graph]
 (when (seq graph)
  (when-let [ks (seq (keep (fn [[k v]] (when (empty? v) k)) graph))]
   (concat ks
    (topo-sort
     (into {}
      (map (fn [[k v]] [k (apply disj v ks)]))
      (apply dissoc graph ks)))))))