我正在考虑解决编译目标.假设我有一组编译目标,每个目标都有一组自己的依赖项.
A -> B C B -> C E C -> E F D -> NONE E -> F F -> NONE
除非其依赖项在先前的传递中,否则无法将目标添加到传递中.即：我想要一个看起来像这样的编译步骤列表：
[[D F] [E] [C] [B] [A]]
所以,D和F被编译,然后是E,然后是C,等等……如何做到这一点？
解决方法
地图将是表示直接依赖关系的自然方式
(def direct-dependencies
{:a #{:b :c},:b #{:c :e},:c #{:e :f},:d nil,:e #{:f},:f nil})
然后是一个简单的(没有循环检查)拓扑排序
(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))))))
根据需要输出
(tsort direct-dependencies) ;=> ([:f :d] [:e] [:c] [:b] [:a])
