java如何使用图论来调度执行顺序？

Question

我正在设计一个应用程序，它执行一系列插件。一个插件的执行可能/可能不依赖于另一个/其他插件的执行。i、 e一些（不是全部）插件希望在开始执行之前执行其他插件

我需要导出正确的执行顺序，这样就不会在它所依赖的插件之前执行任何插件

我相信图论可以用来解决这个问题（插件作为顶点，依赖关系作为边，并使用某种遍历导出执行顺序）

我计划使用JGraphT，因为应用程序是用Java开发的

有什么帮助或建议来解决这个问题吗？？？我不期望整个java代码，任何关于图论（要使用的算法）的指针都同样有用

谢谢

[solution:@Artium导致解决方案，这个link显示了一个非常类似的实现

Answer 1

我建议采用一种简单的按需加载方法，加载插件依赖的所有插件（如果尚未加载）

一些意见：

1. 如果依赖关系树非常深（>；1000个插件），这可能会导致StackOverflowException
2. 这个解决方案是线程安全的，假设所有插件都是逐个同步加载的
3. 在“图形”中查找非法循环是通过使用starting标志来处理的，该标志在加载所有依赖项之前设置为true，只有在插件初始化之后才设置回false
4. 本例处理插件显式启动另一个插件的情况（不作为其依赖项的一部分，但不考虑异步初始化）

下面是一个未经测试的示例，可以提供一个想法：

class Plugin {
    Set<Plugin> dependencies;
    boolean started, starting;

    Plugin(Set<Plugin> deps) { dependencies = deps; }

    void start() {
        if (started) { /* already initialized */ }
        else if (starting) { throw new IllegalArgumentException("Cyclic plugin dependency"); }
        else {
            starting = true;
            for (Plugin p : dependencies) { p.start(); }
            /* initialize this plugin here */
            starting = false;
            started = true;
        }
    }
}

Answer 2

我建议一个topological sort

在快速检查之后，它与JGraphT有关。 另请注意：

For this iterator to work correctly the graph must be acyclic, and must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast; the results with cyclic input (including self-loops) or concurrent modifications are undefined. To precheck a graph for cycles, consider using CycleDetector or StrongConnectivityInspector.