Ordering of results based upon dependencies

Question

I'm looking at resolving compilation targets.. Say if I have a set of compilation targets, each with a set of its own dependencies.

A -> B C

B -> C E 

C -> E F

D -> NONE

E -> F

F -> NONE

The targets cannot be added to a pass unless its dependencies are are in a previous pass. i.e: I want to have a list of compilation steps looking like this:

[[D F] [E] [C] [B] [A]]

So, D and F are compiled, then E, then C, etc... How can this be done?

Answer 1

A map would be a natural way to represent your direct dependencies

(def direct-dependencies 
  {:a #{:b :c}, :b #{:c :e}, :c #{:e :f}, :d nil, :e #{:f}, :f nil})

Then a no-frills (no cycle check) topological sort

(defn tsort [m] 
  (let [depth (fn depth [x] 
                (if (empty? (m x)) 
                  0 
                  (->> x m (map depth) (apply max) inc)))]
    (map val (sort-by key (group-by depth (keys m))))))

With output as desired

(tsort direct-dependencies)
;=> ([:f :d] [:e] [:c] [:b] [:a])