Алгоритм для одновременного обхода графа

Question

В ориентированном ациклическом графе, описывающем набор задач для обработки, мне нужно найти все задачи, которые можно обрабатывать одновременно. График не имеет циклов и довольно мал (~ 1000 узлов, ~ 2000 ребер), производительность не является основной проблемой.

Примеры с желаемым результатом:

• []группа. Все задачи в группе должны быть обработаны перед продолжением
• [x & y] означает, что x и y могут обрабатываться одновременно (x и y параллельно)
• x -> y означает x и y должны обрабатываться последовательно (x перед y)

1

a -> [b & c] -> c

2

[a & e] -> b -> c -> [d & f]

3

[ [a -> b] & [e -> f] ] -> [ [c -> d] & g ]

Я не хочу на самом деле выполнять график, а скорее построить структуру данных, которая будет как можно более параллельной при сохранении порядка. Номенклатура и названия алгоритмов мне не очень знакомы, поэтому я с трудом пытаюсь найти похожие проблемы / решения в Интернете.

Answer 1

Вот решение, которое я придумал (псевдокод):

sequence = []
for each (node, depth) in depthFirstSearch(graph)
  sequence[depth].push(node)
return sequence

sequence определяет порядок обработки графа. Если элемент в нем содержит более одного узла, они могут обрабатываться одновременно.

Хотя это допускает некоторый параллелизм, он не продвигается так быстро, как мог бы. Например, f в примере 3 в вопросе потребует, чтобы сначала было выполнено a (как это будет на глубине 1, когда a и e - глубина 0),В идеале работа над f может начаться после завершения e.