Ordering of results based upon dependencies

clojure

Solution

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])

Problem

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?

Original source