Каковы алгоритмы для решения сборки зависимостей?

Question

Я строю систему, похожую на сборку проекта. Проект имеет набор входов и выходов. Проект может зависеть от других проектов. Я могу использовать топологическую сортировку и найти последовательность, в которой я должен оценивать проекты. Но как сделать параллельную сборку. Toposort не дает равных рядов проектам, которые могут строить параллельно. Кроме того, как мне делать инкрементные сборки.

Answer 1

Вы можете параллельно строить все проекты, не имеющие каких-либо зависимостей. После сборки удалите построенный проект из графика и снова создайте проекты без зависимостей. Повторяйте до тех пор, пока граф не станет пустым.

В псевдокоде

1. Построить проект граф
2. Validate графика (например, циклическая зависимость)
3. Найти все проекты без зависимостей, а не по сборке
4. Начать строить все найденные в 3 и отметьте их under build
5. Подождите, пожалуйста, один из построек end and romove строительный проект из графика
6. если граф не улажен у перейти на 3
7. Wait отдых строит