Simple Clojure code to solve a DAG

clj-dag.clj

; Takes a list of tasks and their dependencies, solves a DAG
; and returns the order in which the tasks
; should be run, grouping the paralellizable tasks into lists.
;
; Transforms this task list:
;     {:sql_1 [] 
;      :sql_sum [:sql_1]
;      :sql_3 []
;      :view [:sql_1 :sql_sum]}
;
; Into the following execution order
;    ((:sql_1 :sql_3) (:sql_sum) (:view))
;
;
(defn solve-dag [nodes]
  (let
    ; let solvable = the keys of all the nodes without any dependencies.
    [solvable (set (map first (filter (fn [t] (empty? (last t))) nodes )))]
    ; If solvable contains any items (can we solve anything?)
    (if (seq solvable)
      ; If yes then recurse with removing all the solvable nodes from the nodes seq
      ; and removing all the solved nodes from the dependencies list of the
      ; remaining ones.
      ; Then prepend the nodes solved in the current round to the execution\
      ; order returned from the recursion
      (cons (seq solvable) (solve-dag (remove-solvable solvable nodes)))
      ; otherwise return an empty list
      (list))))

; Remove all solvable elements from the list of nodes and from
; their dependencies.
; solvable is a set containing the keys solved in the current round
; nodes is the seq of nodes passed to solve-dag
(defn remove-solvable [solvable nodes]
  (map (fn [node]
         ; node is a (key dependencies) pair.
         ; remove the solved ones from the dependencies of all the elements
         (list (first node) (remove (fn [n] (contains? solvable n)) (last node))))
       ; n is a (key dependencies) pair 
       ; Remove the solved nodes (nodes whose key is in the solvable set.
       (remove (fn [n] (contains? solvable (first n))) nodes)))

; A simple test of four tasks. Output should be
; ((:sql_1 :sql_3) (:sql_sum) (:view))
(solve-dag {:sql_1 []
                 :sql_sum [:sql_1]
                 :sql_3 []
                 :view [:sql_1 :sql_sum]})