У меня есть список задач, между которыми есть зависимости, и я обдумывал, как можно использовать JGraphT для управления порядком задач. Я бы настроил граф как ориентированный и удалял вершины по мере их обработки (или мне их замаскировать?). Я мог бы использовать TopologicalOrderIterator, если бы собирался выполнять только одну задачу за раз, но я надеюсь распараллелить задачи. Я мог бы получить TopologicalOrderIterator и проверять Graphs.vertexHasPredecessors, пока не найду столько, сколько я хочу выполнить за один раз, но в идеале должно быть что-то вроде Graphs.getVerticesWithNoPredecessors. Я вижу, что Netflix предоставляет утилиту для получения вершин листа, поэтому я мог бы перевернуть график и использовать это, но, вероятно, это того не стоит. Может ли кто-нибудь указать мне лучший способ? Спасибо!
Использование JGraphT для управления порядком зависимых задач
Ответы (1)
Топологический порядок может быть не таким, каким вы хотите. Вот пример, почему бы и нет. Дан следующий топологический порядок задач: [1,2,3,4] и дуги (1,3), (2,3). То есть задача 1 должна быть завершена перед задачей 3, аналогичной для 2 и 4. Предположим также, что задача 1 выполняется очень долго. Таким образом, мы можем начать обработку задач 1 и 2 параллельно, но вы не можете начать 3 до завершения 1. Несмотря на то, что задача 2 завершена, мы не можем запустить задачу 4, потому что задача 3 является следующей задачей в нашем порядке, и эта задача заблокирована 1.
Вот что ты мог сделать. Создайте массив dep[], который отслеживает количество невыполненных зависимостей для каждой задачи. Итак, dep[i]==0 означает, что все зависимости для задачи i выполнены, а это означает, что теперь мы можем выполнять задачу i. Если dep[i]>0, мы пока не можем выполнить задачу i. Предположим, что есть задача j, которую нужно выполнить до задачи i. Как только мы завершим задачу j, мы можем уменьшить количество невыполненных зависимостей задачи i, то есть: dep[i]=dep[i]-1. Опять же, если dep[i]==0, теперь мы готовы обрабатывать задачу i. Короче говоря, алгоритм в псевдокоде будет выглядеть так:
- Инициализировать массив
dep[]. - Начать параллельную обработку всех задач
iсdep[i]==0 - если задача
iзавершена, уменьшитьdep[j]для всех задачj, которые зависят отi. Если в задачеjестьdep[j]==0, начните ее обработку.
Вы, безусловно, можете использовать направленный график для моделирования зависимостей. Каждый раз, когда вы выполняете задачу, вы можете просто перебирать исходящих соседей (в jgrapht используйте функцию successorsOf (vertex)). DAG также можно просто использовать для проверки выполнимости: если график содержит цикл, у вас есть проблема с вашими зависимостями. Однако, если вам не нужна эта тяжелая техника, я бы просто создал двумерный массив, в котором для каждой задачи i вы сохраняете задачи, зависящие от i.
Результирующий алгоритм выполняется за O (n + m) времени, где n - количество задач, а m - количество дуг (зависимостей). Так что это очень эффективно.
