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

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

Примеры

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

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

Алгоритмы

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

Алгоритм Кана

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

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

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

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

Поиск в глубину

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

L ← Пустой список, который будет содержать отсортированные узлы , пока существуют узлы без постоянной отметки, выберите неотмеченный узел n visit( n )функция visit(node n ) если  n имеет постоянную метку , то  возврат,  если  n имеет временную метку , то  остановка  (граф имеет хотя бы один цикл) пометить n временной отметкой для каждого узла m с ребром от n до m  выполнить visit( m ) пометить n постоянной отметкой добавить n к началу L

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

Параллельные алгоритмы

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

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

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

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

На шаге $k$ PE $j$ назначает индексы , где — общее количество обработанных вершин после шага ⁠ ⁠ . Эта процедура повторяется до тех пор, пока не останется вершин для обработки, следовательно . Ниже приведен высокоуровневый обзор псевдокода с одной программой и несколькими данными этого алгоритма. ${\textstyle 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}$ $a_{k-1}$ $к-1$ ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$

Обратите внимание, что префиксную сумму для локальных смещений можно эффективно вычислять параллельно. ${\textstyle 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 Вход: G = (V, E) DAG, распределенный по PE, индекс PE j = 0, ..., p - 1 Выход: топологическая сортировка Gфункция traverseDAGDistributed δ входящая степень локальных вершин V   $Q = {v \in V | δ[v] = 0}$  // Все вершины с входящей степенью 0 nrOfVerticesProcessed = 0 выполнить  глобальную сборку префиксной суммы по размеру Q // получить смещения и общее количество вершин на этом шаге offset = nrOfVerticesProcessed + sum(Q _i , i = 0 to j - 1) // j - индекс процессора foreach u in Q localOrder[u] = индекс++; foreach (u,v) in E отправить сообщение ( u, v ) в PE, владеющий вершиной v nrOfVerticesProcessed += sum(|Q _i |, i = 0 to p - 1) доставить все сообщения соседям вершин в Q получать сообщения для локальных вершин V удалить все вершины в Q для каждого полученного сообщения ( u, v ): если --δ[v] = 0 добавить v к Q,  пока глобальный размер Q > 0 возврат локального заказа

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

Применение к нахождению кратчайшего пути

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

Пусть $d$ будет массивом той же длины, что и $V$ ; он будет содержать кратчайшие расстояния от $s$ . Установите $d [s] = 0$ , все остальные $d [u] = \infty$ .
Пусть $p$ будет массивом той же длины, что и $V$ , со всеми элементами, инициализированными значением nil . Каждый $p [u]$ будет содержать предшественника $u$ в кратчайшем пути от $s$ до $u$ .
Пройдемся по вершинам u, как указано в V , начиная с s :
- Для каждой вершины v, непосредственно следующей за u (т.е. существует ребро из u в v ):
  - Пусть $w$ — вес ребра от $u$ до $v$ .
  - Ослабить ребро: если d [ v ] > d [ u ] + w , установить
    - $д [в] \leftarrow д [у] + ш$ ,
    - $п [г] \leftarrow у$ .

Эквивалентно:

Пусть $d$ будет массивом той же длины, что и $V$ ; он будет содержать кратчайшие расстояния от $s$ . Установите $d [s] = 0$ , все остальные $d [u] = \infty$ .
Пусть $p$ будет массивом той же длины, что и $V$ , со всеми элементами, инициализированными значением nil . Каждый $p$ $[$ $u$ $]$ будет содержать предшественника $u$ в кратчайшем пути от $s$ до $u$ .
Пройдемся по вершинам u, как указано в V , начиная с s :
- Для каждой вершины v в u (т.е. существует ребро из v в u ):
  - Пусть $w$ — вес ребра от $v$ до $u$ .
  - Ослабить ребро: если d [ u ] > d [ v ] + w , установить
    - $д [у] \leftarrow д [в] + ш$ ,
    - $п [u] \leftarrow гл$ .

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

Уникальность

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

Отношение к частичным заказам

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

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

Отношение к оптимизации планирования

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

Смотрите также

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

Ссылки

^ Jarnagin, MP (1960), Автоматические машинные методы тестирования сетей PERT на согласованность , Технический меморандум № K-24/60, Дальгрен, Вирджиния: Лаборатория военно-морского оружия США
^ Кан, Артур Б. (1962), «Топологическая сортировка больших сетей», Сообщения ACM , 5 (11): 558–562, doi : 10.1145/368996.369025 , S2CID 16728233
^ abc Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), «Раздел 22.4: Топологическая сортировка», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 549–552, ISBN 0-262-03293-7
^ Тарьян, Роберт Э. (1976), «Окружающие деревья с непересекающимися рёбрами и поиск в глубину», Acta Informatica , 6 (2): 171–185, doi :10.1007/BF00268499, S2CID 12044793
^ Кук, Стивен А. (1985), «Таксономия проблем с быстрыми параллельными алгоритмами», Информация и управление , 64 (1–3): 2–22, doi : 10.1016/S0019-9958(85)80041-3
^ Декель, Элиезер; Насими, Дэвид; Сахни, Сартай (1981), «Параллельные алгоритмы матриц и графов», SIAM Journal on Computing , 10 (4): 657–675, doi :10.1137/0210049, MR 0635424
^ ab Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019), Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов, Springer International Publishing, ISBN 978-3-030-25208-3
^ Верне, Освальдо; Маркензон, Лилиан (1997), «Гамильтоновы задачи для приводимых потоковых графов» (PDF) , Труды: 17-я Международная конференция Чилийского общества компьютерных наук , стр. 264–267, doi : 10.1109/SCCC.1997.637099, hdl : 11422/2585 , ISBN 0-8186-8052-0, S2CID 206554481

Дальнейшее чтение

DE Knuth , Искусство программирования , том 1, раздел 2.2.3, в котором дается алгоритм топологической сортировки частичного порядка и краткая история.
Бертран Мейер , Touch of Class: Learning to Programming Good with Objects and Contracts , Springer , 2099, глава 15, Разработка и проектирование алгоритма: топологическая сортировка , с использованием современного языка программирования, для подробного педагогического представления топологической сортировки (с использованием варианта алгоритма Кана) с учетом проектирования структуры данных, проектирования API и вопросов разработки программного обеспечения.

Внешние ссылки

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