Получение параллельных элементов в разрешении зависимостей

13

Я реализовал топологическую сортировку на основе статьи в Википедии, которую я использую для разрешения зависимостей, но она возвращает линейный список. Какой алгоритм я могу использовать, чтобы найти независимые пути?

Masse
источник
1
Один из способов решить эту проблему - смоделировать узлы в графе как акторы и позволить некоторой библиотеке акторов позаботиться о порядке.
svick

Ответы:

16

Я предполагаю, что ребро означает, что u должно быть выполнено до v . Если это не так, разверните все края. Кроме того, я предполагаю, что вас меньше интересуют пути (те, которые уже определены DAG), чем хорошая стратегия выполнения с учетом зависимостей.(U,v)Uv

Sяграммзнак равно(В,Е)

S0знак равно{vВ|UВ,(U,v)Е}Sя+1знак равно{vВ|UВ,(U,v)ЕUКзнак равно0яSК}

К

for i=0 to k
  parallel foreach T in S_k
    execute T

S0

parallel foreach T in S_0
  recursive_execute T

где

recursive_execute T {
  atomic { if T.count++ < T.indeg then return }
  execute T
  parallel foreach T' in T.succ
    recursive_execute T'
}

и T.countпредставляет собой простой счетчик, содержащий количество предшественников, Tкоторые уже были выполнены, T.indegколичество предшественников и T.succнабор преемников.

Рафаэль
источник