使用JGraphT管理相关任务的排序

Question

我有一个任务列表，它们之间有依赖关系，我正在考虑如何使用JGraphT来管理任务的顺序。我会将图形设置为有向图，并在处理顶点时删除顶点（或者我应该屏蔽它们吗？如果我一次只执行一个任务，我可以使用TopologicalOrderIterator，但我希望并行化这些任务。我可以获取TopologicalOrderIterator并检查Graphs.vertexHasPredecessors，直到我找到尽可能多的我想要执行一次，但理想情况下，会有像Graphs.getVerticesWithNoPredecessors这样的东西。我看到Netflix提供了一个获取叶顶点的实用程序，所以我可以反转图形并使用它，但它可能不值得。任何人都可以给我指出一个更好的方法吗？谢谢！

Answer 1

拓扑顺序可能不一定是您想要的。这是一个例子，为什么不呢？给定以下任务的拓扑顺序：[1,2,3,4]，以及弧（1,3），（2,3）。也就是说，任务1需要在任务3之前完成，类似于2和4。我们还假设任务1需要很长时间才能完成。所以我们可以开始并行处理任务1和2，但是您不能在1完成之前启动3。即使任务2完成，我们也无法启动任务4，因为任务3是我们排序中的下一个任务，并且此任务被1阻止。

你可以这么做。创建一个数组< code>dep[]，该数组跟踪每项任务未实现的依赖项的数量。因此< code>dep[i]==0意味着任务< code>i的所有相关性都已满足，这意味着我们现在可以执行任务< code>i。If dep[i]

1. 初始化 dep[] 数组。
2. 使用 dep[i]==0 并行开始处理所有任务 i
3. 如果一个任务 i 完成，则对于依赖于 i 的所有任务 j，递减 dep[j]。如果任务 j 有 dep[j]==0，则开始处理它。

您当然可以使用有向图来对依赖关系进行建模。每次您完成一项任务时，您可以简单地迭代传出的邻居（在jgraph t中使用后续（顶点）函数）。DAG也可以简单地用于检查可行性：如果图包含循环，则您的依赖关系存在问题。但是，如果您不需要这种重型机器，我可以简单地创建一个二维数组，其中为每个任务i您存储依赖于i的任务。

生成的算法在O（n m）时间内运行，其中n是任务数，m是弧数（依赖项）。所以这是非常有效的。