2

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

我需要导出正确的执行顺序，以便在它所依赖的插件之前不执行任何插件。

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

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

解决此案的任何帮助或指示？？？我并不期待整个 java 代码，任何关于图论（使用算法）的指针都会同样有帮助....

谢谢 ！！！

[解决方案：] @Artium 导致解决方案，这个链接显示了一个非常相似的实现。

4

2 回答 2

3

我建议使用拓扑排序。

在快速检查之后，使用 JGraphT很容易做到。另请注意：

要使此迭代器正常工作，该图必须是非循环的，并且不得在迭代期间进行修改。目前没有办法确保这一点，也没有快速失败的方法；循环输入（包括自循环）或并发修改的结果未定义。要预先检查循环图，请考虑使用 CycleDetector 或 StrongConnectivityInspector。

于 2011-06-25T10:56:45.233 回答
0

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

几点观察：

  1. 如果依赖树非常深（> 1,000 个插件），这可能会导致 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;
        }
    }
}
于 2011-06-25T11:08:44.603 回答