Топологическая сортировка

В информатике , топологическая сортировка или топологическое упорядочение из ориентированного графа является линейным упорядочением его вершин , что для каждого направленного ребра уф из вершин U в вершину V , U предшествует V в упорядочении. Например, вершины графа могут представлять задачи, которые должны быть выполнены, а ребра могут представлять ограничения, согласно которым одна задача должна быть выполнена раньше другой; в этом приложении топологический порядок - это просто допустимая последовательность для задач. Топологический порядок возможен тогда и только тогда, когда граф не имееториентированные циклы , то есть если это ориентированный ациклический граф (DAG). Любой DAG имеет по крайней мере одно топологическое упорядочение, и известны алгоритмы построения топологического упорядочения любого DAG за линейное время . Топологическая сортировка имеет множество приложений, особенно в задачах ранжирования, таких как набор дуг обратной связи .

Примеры [ править ]

Каноническое применение топологической сортировки заключается в планировании последовательности заданий или задач на основе их зависимостей . Задания представлены вершинами, и есть ребро от x до y, если задание x должно быть завершено до начала задания y (например, при стирке одежды стиральная машина должна закончить, прежде чем мы поместим одежду в сушилку) . Затем топологическая сортировка определяет порядок выполнения работ. Тесно связанное с этим применение алгоритмов топологической сортировки было впервые изучено в начале 1960-х годов в контексте метода PERT для планирования в управлении проектами . ^[1]В этом приложении вершины графа представляют вехи проекта, а ребра представляют задачи, которые должны быть выполнены между одним этапом и другим. Топологическая сортировка составляет основу алгоритмов линейного времени для поиска критического пути проекта, последовательности этапов и задач, которые контролируют продолжительность общего расписания проекта.

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

Граф, показанный слева, имеет много допустимых топологических типов, в том числе: 5, 7, 3, 11, 8, 2, 9, 10 (визуально сверху вниз, слева направо) 3, 5, 7, 8, 11, 2, 9, 10 (первая доступная вершина с наименьшим номером) 5, 7, 3, 8, 11, 10, 9, 2 (сначала наименьшее количество краев) 7, 5, 11, 3, 10, 8, 9, 2 (доступная вершина с наибольшим номером первая) 5, 7, 11, 2, 3, 8, 9, 10 (попытки сверху вниз, слева направо) 3, 7, 8, 5, 11, 10, 2, 9 (произвольно)

Алгоритмы [ править ]

Обычные алгоритмы топологической сортировки имеют время работы, линейное по количеству узлов плюс количество ребер, асимптотически ${\ Displaystyle O (\ left | {V} \ right | + \ left | {E} \ right |).}$

Алгоритм Кана [ править ]

Один из этих алгоритмов, впервые описанный Каном (1962) , работает путем выбора вершин в том же порядке, что и конечная топологическая сортировка. Сначала найдите список «начальных узлов», у которых нет входящих ребер, и вставьте их в набор S; хотя бы один такой узел должен существовать в непустом ациклическом графе. Потом:

L ← Пустой список, который будет содержать отсортированные элементы S ← Набор всех узлов без входящего ребрав то время как  S  не пустой делать удалить узел п от S добавления п к L  для каждого узла м с ребром е от п до т  сделать удалить ребро е из графика , если  м не имеет других входящих ребер , то вставка м в Sесли  граф имеет ребро , то  вернуть ошибку (граф имеет , по меньшей мере , один цикл) остальное  возвращение  л  (топологический отсортирован порядок)

Если граф является DAG , решение будет содержаться в списке L (решение не обязательно уникальное). В противном случае в графе должен быть хотя бы один цикл, поэтому топологическая сортировка невозможна.

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

Поиск в глубину [ править ]

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

L ← Пустого список , который будет содержать отсортированные узлы в то время как существует узлы без постоянного знака делать выберите немаркированный узел п посещение ( п )Функция посещение (узел п ) , если  п имеет постоянный знак , то  возвращает ,  если  п имеет временную метку , то  остановка  (не ДАГ) отметить n временной отметкой для каждого узла м с ребром от п до т  сделать визит ( м ) удалить временную отметку с n отметка n с постоянной отметкой добавить n в заголовок L

Каждый узел п получает предваряется к списку вывода L только после рассмотрения всех других узлов , которые зависят от п (все потомки п в графе). В частности, когда алгоритм добавляет узел n , мы гарантируем, что все узлы, зависящие от n , уже находятся в выходном списке L: они были добавлены в L либо рекурсивным вызовом visit (), который завершился до вызова visit n , или вызовом visit (), который начался еще до вызова visit n . Поскольку каждое ребро и узел посещаются один раз, алгоритм работает за линейное время. Этот алгоритм, основанный на поиске в глубину, описан Корменом и др. (2001); кажется, что впервые он был описан в печати Тарьяном (1976) .

Параллельные алгоритмы [ править ]

На параллельной машине с произвольным доступом топологическое упорядочение может быть построено за время O (log ² n ) с использованием полиномиального числа процессоров, помещая задачу в класс сложности NC ² . ^[2] Один из способов сделать это - многократно возводить в квадрат матрицу смежности данного графа, логарифмически много раз, используя умножение матрицы мин-плюс с максимизацией вместо минимизации. Результирующая матрица описывает самые длинные пути на графике. Сортировка вершин по длинам их самых длинных входящих путей дает топологический порядок. ^[3]

Алгоритм параллельной топологической сортировки на машинах с распределенной памятью распараллеливает алгоритм Кана для DAG . ^[4] На высоком уровне алгоритм Кана многократно удаляет вершины степени 0 и добавляет их к топологической сортировке в том порядке, в котором они были удалены. Поскольку исходящие ребра удаленных вершин также удаляются, будет новый набор вершин степени 0, в котором процедура повторяется до тех пор, пока не останется ни одной вершины. Этот алгоритм выполняет итерации, где D представляет собой самый длинный путь в G . Каждую итерацию можно распараллелить, что является идеей следующего алгоритма.${\ Displaystyle G = (V, E)}$${\ displaystyle D + 1}$

Далее предполагается, что раздел графа хранится на p обрабатывающих элементах (PE), которые помечены . Каждый PE i инициализирует набор локальных вершин со степенью 0, где верхний индекс представляет текущую итерацию. Поскольку все вершины в локальных множествах имеют степень 0, т. Е. Они не являются смежными, они могут быть заданы в произвольном порядке для правильной топологической сортировки. Чтобы присвоить глобальный индекс каждой вершине, сумма префиксов рассчитывается по размерам . Таким образом, на каждом шаге к топологической сортировке добавляются вершины.${\ displaystyle 0, \ dots, p-1}$${\displaystyle Q_{i}^{1}}$${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$${\displaystyle \sum _{i=0}^{p-1}|Q_{i}|}$

На первом этапе PE j присваивает индексы локальным вершинам в . Эти вершины удаляются вместе с соответствующими исходящими ребрами. Для каждого исходящего ребра с конечной точкой v в другом PE сообщение отправляется PE l . После того, как все вершины удалены, отправленные сообщения отправляются в соответствующий PE. Каждое полученное сообщение обновляет степень локальной вершины v . Если степень падает до нуля, к нему прибавляется v . Затем начинается следующая итерация.${\displaystyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$${\displaystyle Q_{j}^{1}}$${\displaystyle Q_{j}^{1}}$${\displaystyle (u,v)}$${\displaystyle l,j\neq l}$${\displaystyle (u,v)}$${\displaystyle Q_{j}^{1}}$${\displaystyle (u,v)}$${\displaystyle Q_{j}^{2}}$

На шаге k PE j присваивает индексы , где - общее количество обработанных вершин после шага . Эта процедура повторяется до тех пор, пока не останется обработанных вершин . Ниже представлен высокоуровневый обзор этого алгоритма с использованием псевдокода с несколькими данными .${\displaystyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$${\displaystyle a_{k-1}}$${\displaystyle k-1}$${\displaystyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$

Обратите внимание, что сумма префиксов для локальных смещений может эффективно вычисляться параллельно.${\displaystyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$

p обрабатывающих элементов с идентификаторами от 0 до p -1 Вход: DAG, распределенный по PE, индекс PE Выход: топологическая сортировка G${\displaystyle G=(V,E)}$${\displaystyle j\in \{0,\dots ,p-1\}}$

функция traverseDAGDistributed δ входящая степень локальных вершин V  Q = { v ∈ V | δ [ v ] = 0}  // Все вершины со степенью 0 nrOfVerticesProcessed = 0 сделать  глобальную сборку префикса суммой по размеру Q  // получить смещения и общее количество вершин на этом шаге offset = nrOfVerticesProcessed + // j - индекс процессора для каждого u ∈ Q${\displaystyle \sum _{i=0}^{j-1}|Q_{i}|}$     localOrder [u] = index ++; Еогеасп  ( U, V ) ∈ E  сделать пост сообщения ( U, V ) к РЕ владеющей вершины v  nrOfVerticesProcessed + =${\displaystyle \sum _{i=0}^{p-1}|Q_{i}|}$ доставлять все сообщения соседям вершин в Q  получать сообщения для локальных вершин V удалить все вершины в Q Еогеасп сообщение ( U, V ) получен: если --δ [v] = 0 добавить v к Q,  а глобальный размер Q > 0 вернуть localOrder

Стоимость связи сильно зависит от данного раздела графа. Что касается времени выполнения, то в модели CRCW-PRAM, которая допускает выборку и декремент за постоянное время, работает этот алгоритм , где D снова является самым длинным путем в G, а Δ - максимальной степенью. ^[4]${\displaystyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$

Приложение для поиска кратчайшего пути [ править ]

Топологическое упорядочение также можно использовать для быстрого вычисления кратчайших путей через взвешенный ориентированный ациклический граф. Пусть V - список вершин такого графа в топологическом порядке. Затем следующий алгоритм вычисляет кратчайший путь от некоторой исходной вершины s до всех остальных вершин: ^[5]

На графе из n вершин и m ребер этот алгоритм занимает Θ ( n + m ) , т. Е. Линейное время. ^[5]

Уникальность [ править ]

Если топологическая сортировка обладает тем свойством, что все пары последовательных вершин в отсортированном порядке соединены ребрами, то эти ребра образуют направленный гамильтонов путь в DAG . Если гамильтонов путь существует, топологический порядок сортировки уникален; никакой другой порядок не учитывает края пути. И наоборот, если топологическая сортировка не образует гамильтонов путь, DAG будет иметь два или более допустимых топологического порядка, поскольку в этом случае всегда можно сформировать второй допустимый порядок, поменяв местами две последовательные вершины, которые не соединены ребром. друг другу. Следовательно, можно проверить за линейное время, существует ли уникальное упорядочение и существует ли гамильтонов путь, несмотря на NP-трудностьпроблемы гамильтонова пути для более общих ориентированных графов (т. е. циклических ориентированных графов). ^[6]

Отношение к частичным заказам [ править ]

Топологические упорядочивании также тесно связаны с понятием линейного расширения в виде частичного порядка в математике. В терминах высокого уровня существует взаимосвязь между ориентированными графами и частичными порядками. ^[7]

Частично упорядоченный набор - это просто набор объектов вместе с определением отношения неравенства «≤», удовлетворяющий аксиомам рефлексивности ( x  ≤  x ), антисимметрии (если x  ≤  y и y  ≤  x, то x  =  y ) и транзитивности. (если x  ≤  y и y  ≤  z , то x  ≤  z ). Общий порядок представляет собой частичный порядок , в котором, для каждых двух объектов х и у в наборе, либо х  ≤ y или y  ≤  x . Общие заказы известны в информатике как операторы сравнения, необходимые для выполнения алгоритмов сортировки сравнения . Для конечных наборов общие порядки могут быть идентифицированы с линейными последовательностями объектов, где отношение «≤» истинно всякий раз, когда первый объект предшествует второму объекту в порядке; алгоритм сортировки сравнения может использоваться для преобразования общего порядка в последовательность таким образом. Линейное расширение частичного порядка - это полный порядок, совместимый с ним, в том смысле, что если x  ≤  y в частичном порядке, то x  ≤  y также и в полном порядке.

Можно определить частичный порядок из любого DAG, позволив множеству объектов быть вершинами DAG и определив x  ≤  y как истинное для любых двух вершин x и y , если существует направленный путь от x к y ; то есть, когда у является достижимым от й . С этими определениями топологический порядок DAG - это то же самое, что и линейное расширение этого частичного порядка. И наоборот, любое частичное упорядочение можно определить как отношение достижимости в DAG. Один из способов сделать это - определить группу DAG, у которой есть вершина для каждого объекта в частично упорядоченном наборе и ребро.xy для каждой пары объектов, для которых x  ≤  y . Альтернативный способ сделать это - использовать транзитивную редукцию частичного упорядочения; как правило, это создает группы DAG с меньшим количеством ребер, но отношение достижимости в этих группах DAG остается тем же частичным порядком. Используя эти конструкции, можно использовать алгоритмы топологического упорядочения для поиска линейных расширений частичных порядков.

См. Также [ править ]

• tsort , Unix-программа для топологической сортировки
• Набор дуг обратной связи , набор ребер, удаление которых позволяет топологически отсортировать оставшийся подграф
• Алгоритм сильно связанных компонентов Тарьяна, алгоритм , который дает топологически отсортированный список сильно связных компонентов в графе.
• Предпотопологический порядок

Заметки [ править ]

Ссылки [ править ]

• Кук, Стивен А. (1985), «Таксономия проблем с быстрыми параллельными алгоритмами», Информация и управление , 64 (1–3): 2–22, DOI : 10.1016 / S0019-9958 (85) 80041-3.
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Раздел 22.4: Топологическая сортировка», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 549–552, ISBN 0-262-03293-7.
• Декель, Элиэзер; Нассими, Дэвид; Sahni, Sartaj (1981), "Параллельные матричные алгоритмы и график", SIAM журнал по вычислениям , 10 (4): 657-675, DOI : 10,1137 / 0210049 , МР  0635424.
• Ярнагин, М.П. (1960), Автоматические методы тестирования сетей PERT на непротиворечивость , Технический меморандум № K-24/60, Дальгрен, Вирджиния: Лаборатория вооружения ВМС США..
• Кан, Артур Б. (1962), "Топологическая сортировка крупных сетей", коммуникаций АСМ , 5 (11): 558-562, DOI : 10,1145 / 368996,369025 , S2CID  16728233.
• Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019), Последовательные и параллельные алгоритмы и структуры данных: The Basic Toolbox , Springer International Publishing, ISBN 978-3-030-25208-3.
• Спивак, Дэвид И. (2014), Теория категорий для наук , MIT Press.
• Тарьян, Роберт Е. (1976), "Край непересекающихся остовных деревьев и поиск в глубину", Acta Informatica , 6 (2): 171-185, DOI : 10.1007 / BF00268499 , S2CID  12044793.
• Верне, Освальдо; Маркензон, Лилиан (1997), "Гамильтоновы задачи для приводимых потоковых графов", Proc. 17 -я Международная конференция чилийской Computer Science Society (SCCC '97) (PDF) , стр 264-267,. Дои : 10,1109 / SCCC.1997.637099 , ЛВП : 11422/2585 , S2CID  206554481.

Дальнейшее чтение [ править ]

• Д. Кнут , Искусство компьютерного программирования , Том 1, раздел 2.2.3, в котором дается алгоритм топологической сортировки частичного упорядочения и краткая история.

Внешние ссылки [ править ]

• Словарь алгоритмов и структур данных NIST: топологическая сортировка
• Вайсштейн, Эрик В. , "TopologicalSort" , MathWorld