使用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並行，但你不能啓動3前1完成。儘管任務2完成，我們不能因爲任務3是我們訂購的下一個任務，這個任務被阻止通過1啓動任務4。

以下是您可以做的事情。創建一個數組dep[]，該數組跟蹤每個任務未實現的依賴項的數量。因此dep[i]==0意味着任務i的所有依賴關係都已完成，這意味着我們現在可以執行任務i。如果dep[i]>0，我們仍然無法執行任務i。讓我們假設有一項任務j需要在任務i之前執行。只要我們完成任務j，我們就可以減少任務i的未實現依賴關係的數量，即：dep[i]=dep[i]-1。再次，如果dep[i]==0，我們現在準備好處理任務i。 因此，在短期，在僞代碼的算法是這樣的：

1. 初始化dep[]陣列。並行所有任務i
2. 開始處理與dep[i]==0
3. 如果任務完成i，遞減dep[j]對於依賴於i所有任務j。如果任務j有dep[j]==0，則開始處理它。

你當然可以用有向圖的依賴關係進行建模。每次完成一項任務時，您都可以簡單地迭代傳出的鄰居（在jgraph中使用successorsOf（vertex）函數）。 DAG也可以簡單地用於檢查可行性：如果圖形包含一個循環，則您的依賴關係中存在問題。但是，如果您不需要這麼重的機器，我只需創建一個2維數組，其中對於每個任務i您都存儲依賴於i的任務。

所得算法運行在O（N + M）的時間，其中n是任務數和m弧（依賴關係）的數量。所以這非常有效。