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

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

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

Задачу можно сформулировать так:

Учитывая набор узлов 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, когда вы указываете несколько пакетов в одной команде установки. Однако, когда я ищу ключевые фразы, такие как «алгоритм разрешения зависимостей», я получаю результаты, описывающие обычную топологическую сортировку, которая не обрабатывает этот конкретный случай.

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


graph algorithm topological-sort
person Tyler McHenry    schedule 22.07.2010    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

person Peter Ruderman    schedule 22.07.2010
comment
В конце концов, я пошел с этим, хотя мне все равно было бы интересно узнать, есть ли что-нибудь лучше и менее грубой силы. - person Tyler McHenry; 24.07.2010

arrow_upward
1
arrow_downward

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

person Teodor Pripoae    schedule 22.07.2010
comment
Для меня нецелесообразно сортировать весь граф, так как граф очень большой, часть, которую я хочу отсортировать, будет довольно маленькой, а информация об узлах поступает из базы данных, что сделало бы сортировку всего графа очень сложной. , очень медленно. - person Tyler McHenry; 22.07.2010
comment
Хорошо, поэтому вы можете выполнить поиск в глубину, входя в узел, если узел не был посещен ранее, поэтому вы получите подграф, а затем отсортируете подграф. Временная сложность равна o (k + m), где k - размер подграфа, а m - количество ссылок в этом подграфе. - person Teodor Pripoae; 22.07.2010