一个干净的算法,用于根据定义的依赖项对对象进行排序？

Question

给出从此基础继承的类列表:

class Plugin(object):
    run_after_plugins = ()
    run_before_plugins = ()

......以及以下规则:

• 插件可以提供必须运行的插件列表.
• 插件可以提供之前必须运行的插件列表.
• 插件列表可能包含也可能不包含已在排序约束中指定的所有插件.

任何人都可以提供一个很好的清洁算法来订购插件列表？它还需要检测循环依赖性....

 def order_plugins(plugins):
      pass

我想出了几个版本,但没有什么特别整洁:我相信你们中的一些计算机编程类型的艺术将津津乐道挑战:)

[注意:在Python中给出的问题,但它显然不仅仅是一个Python问题:任何语言的伪代码都可以]

Answer 1

这称为拓扑排序.

拓扑排序(拓扑顺序)的规范应用是调度一系列作业或任务; 拓扑排序算法最早是在20世纪60年代早期在PERT技术中用于项目管理中的调度(Jarnagin 1960).作业由顶点表示,如果在作业y开始之前必须完成作业x,则从x到y存在边缘(例如,洗衣服时,洗衣机必须在我们将衣服晾干之前完成).然后,拓扑排序给出了执行作业的顺序.