JGraphTを使用した従属タスクの順序の管理

Question

私はそれらの間に依存関係のあるタスクのリストを持っています.JGraphTを使用してタスクの順序を管理する方法を検討していました。グラフを有向グラフとして設定し、処理したときに頂点を削除します（またはマスクする必要がありますか？）。一度に1つのタスクしか実行しない場合は、TopologicalOrderIteratorを使用できますが、タスクを並列化したいと考えています。 TopologicalOrderIteratorを取得し、Graphs.vertexHasPredecessorsをチェックすると、一度に実行したいと思うほど多くのものを見つけることができますが、理想的にはGraphs.getVerticesWithNoPredecessorsのようになります。 Netflixは葉の頂点を取得するユーティリティを提供しているので、グラフを逆にして使用することができますが、それはおそらくそれほど価値がありません。誰かが私をより良い方法に向けることができますか？ありがとう！

Answer 1

トポロジカルな順序は、必要なものである必要はありません。なぜそうではないのかの例があります。タスクの位相配置は、[1,2,3,4]、円弧は(1,3)、(2,3)です。つまり、タスク1は、タスク3の前に完了する必要があります。2と4と同様です。また、タスク1が完了するのに本当に時間がかかるとしましょう。したがって、処理1と2を並行して処理することができますが、が完了する前に3を開始することはできません。タスク2が完了しても、タスク3が注文の次のタスクであり、このタスクが1によってブロックされているため、タスク4を開始できません。

あなたができることは次のとおりです。タスクごとに満たされていない依存関係の数を追跡する配列dep[]を作成します。したがって、dep[i]==0は、タスクiのすべての依存関係が満たされていることを意味します。つまり、タスクiを実行できることを意味します。 dep[i]>0の場合、まだタスクiを実行することはできません。タスクiの前に実行する必要があるタスクjがあるとします。タスクjを完了するとすぐに、タスクiの満たされていない依存関係の数、つまりdep[i]=dep[i]-1を減らすことができます。繰り返しますが、dep[i]==0の場合は、タスクiを処理する準備が整いました。 だから要するに、擬似コードにおけるアルゴリズムは次のようになります。

1. dep[]配列を初期化します。 dep[i]==0
2. と並行して、すべてのタスクiで
3. スタート処理タスクi完了した場合、iに依存するすべてのタスクjためdep[j]をデクリメント。 jのタスクがdep[j]==0の場合、処理を開始します。

ダイレクトグラフを使用して依存関係をモデル化できます。タスクを完了するたびに、発信近隣（jgraphtではsuccessorsOf（vertex）関数を使用）を反復するだけです。 DAGは、実行可能性を確認するためにも簡単に使用できます。グラフにサイクルが含まれている場合、依存関係に問題があります。しかし、この重い機械を必要としない場合は、2次元配列を作成するだけで、各タスクに対してiiに依存するタスクを格納することができます。

結果のアルゴリズムはO（n + m）時間で実行されます.nはタスクの数、mはアークの数（依存関係）です。これは非常に効率的です。