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

Упорядочение узлов ориентированных ациклических графов

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

Примеры

Этот граф имеет множество допустимых топологических разновидностей, в том числе:

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

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

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

Алгоритмы

Обычные алгоритмы топологической сортировки имеют время работы, линейное по числу узлов плюс количество ребер, асимптотически: ${\displaystyle 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 постоянной отметкой добавьте n в заголовок L

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

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

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

Алгоритм параллельной топологической сортировки на машинах с распределенной памятью распараллеливает алгоритм Кана для DAG . ^[7] На высоком уровне алгоритм Кана многократно удаляет вершины степени 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}}$ ${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$

Выполнение параллельного алгоритма топологической сортировки на DAG с двумя обрабатывающими элементами.

На первом этапе 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}$ ${\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 присваивает индексы , где — общее количество обработанных вершин после шага . Эта процедура повторяется до тех пор, пока не останется вершин для обработки, следовательно . Ниже приведен высокоуровневый обзор псевдокода этого алгоритма для одной программы и нескольких данных . ${\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}$ ${\displaystyle a_{k-1}}$ ${\displaystyle k-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 ∈ V | δ[ v ] = 0} // Все вершины с входной степенью 0 nrOfVerticesProcessed = 0 выполнить  глобальную сумму префикса сборки по размеру Q // получить смещения и общее количество вершин на этом шаге offset = nrOfVerticesProcessed + sum(Q i , i = от 0 до j - 1) // j — индекс процессора foreach u в Q  localOrder[u] = индекс++; foreach (u,v) в E отправить сообщение ( u, v ) PE, владеющему вершиной v nrOfVerticesProcessed += sum(|Q i |, i = от 0 до p - 1) доставить все сообщения соседям вершин в Q  получать сообщения для локальных вершин V удалить все вершины в Q Получено сообщение foreach ( u, v ): if --δ[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 [ ты ] знак равно ∞ .
• Пусть p — массив той же длины, что и V , со всеми элементами, инициализированными значением nil . Каждый p [ u ] будет содержать предшественника u на кратчайшем пути от s до u .
• Перебираем вершины u , как указано в V , начиная с s :
  • Для каждой вершины v, следующей непосредственно за u (т. е. существует ребро от u до v ):
    • Пусть w — вес ребра от u до v .
    • Расслабьте край: если d [ v ] > d [ u ] + w , установите
      • d [ v ] ← d [ ты ] + ш ,
      • п [ v ] ← ты .

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

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

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

Связь с оптимизацией планирования

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

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

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

Рекомендации

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

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

• Д. Е. Кнут , Искусство компьютерного программирования , Том 1, раздел 2.2.3, в котором дается алгоритм топологической сортировки частичного порядка и краткая история.
• Бертран Мейер , Прикосновение к классу: научиться хорошо программировать с объектами и контрактами , Springer , 2099, глава 15, Разработка и разработка алгоритма: топологическая сортировка , с использованием современного языка программирования, для подробного педагогического представления топологической сортировки (с использованием варианта алгоритма Кана) с учетом вопросов проектирования структур данных, проектирования API и разработки программного обеспечения.

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

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