Алгоритм топологического варианта сортировки

Question

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

• Известно, что отношения данных образуют DAG (поэтому нет циклов, о которых нужно беспокоиться).
• Ребро от A до B указывает, что A зависит от B, поэтому B должен отображаться перед A в топологическом порядке.
• График не обязательно связан; то есть для любых двух узлов N и M не может быть никакого способа получить от N до M следующие ребра (даже если вы игнорируете направление кромки).
• Связи данных связаны друг с другом. Это означает, что когда есть ребро, направленное от А до В, только узел А содержит информацию о существовании края.

Проблема может быть сформулирована следующим образом:

Принимая во внимание множество узлов S в графе G, которые могут или не могут иметь входящие ребра, найти топологическое упорядочение подграфа G', состоящий из все узлы в G, которые достижимы с любого узла в наборе S (подчиняясь направлению кромки).

Это путает обычные подходы к топологической сортировке, поскольку они требуют, чтобы узлы в наборе S не имеют входящие ребра, которая является то, что это не так в моем случае. Патологический случай:

A --> B --> D 
| ^ ^
|  |  | 
\---> C ----/ 

Где S = {B, C}. Соответствующим порядком будет D, B, C, но если обычный алгоритм топологической сортировки рассмотрел B до C, это закончится с C, D, B, что совершенно неверно. (Обратите внимание, что A не появляется в результате упорядочения, поскольку она не достижима из S, это там, чтобы дать пример, в котором все узлы в S может иметь входящие ребра)

Теперь я должен представить себе, что это долгое решение проблемы, так как это, по сути, такие программы, как apt и yum, должны делать, когда вы укажете несколько пакетов в одной команде установки. Однако, когда я ищу ключевые фразы, такие как «алгоритм разрешения зависимостей», я получаю результаты, описывающие нормальную топологическую сортировку, которая не обрабатывает этот конкретный случай.

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

Answer 1

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

Answer 2

Я думаю, что вы можете выполнить топологическую сортировку всего графика, а затем выбрать только узлы, которые доступны из набора узлов (вы можете выполнить глубину первых поисков из узлов в наборе в порядке, указанном после сортировка, и вы попадете в поддерево узла, если раньше он не был посещен).