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

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

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

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

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

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

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

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

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

L  ← Пустой список, содержащий отсортированные элементы. 
  S  ← Набор всех узлов без входящего ребра 

  пока   S   не  пусто,  сделайте 
      удалить узел  n  из  S 
      добавьте  n  к  L 
     для каждого  узла  m  с ребром  e  от  n  до  m   do 
          удалить ребро  e  из графа 
          если   у m  нет других входящих ребер  , то 
              вставьте  m  в  S 

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

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

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

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

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

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

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

      отметить  n  временной отметкой 

      для каждого  узла  m  с ребром от  n  до  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. $G=(V,E)$ . ^[7]На высоком уровне алгоритм Кана многократно удаляет вершины степени 0 и добавляет их к топологической сортировке в том порядке, в котором они были удалены. Поскольку исходящие ребра удаленных вершин также удаляются, появится новый набор вершин входящей степени 0, где процедура повторяется до тех пор, пока не останется ни одной вершины. Этот алгоритм выполняет $D+1$ итераций, где $D$ — самый длинный путь $G.$ в Каждую итерацию можно распараллелить, в этом и заключается идея следующего алгоритма.

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

На первом этапе PE $j$ присваивает индексы ${\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)$ с конечной точкой $v$ в другом PE $l,j\neq l$ , сообщение $(u,v)$ отправлено в PE $l$ . Ведь вершины в $Q_{j}^{1}$ удаляются, опубликованные сообщения отправляются на соответствующий PE. Каждое сообщение $(u,v)$ получены обновления степени локальной вершины $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}$ общее количество обработанных вершин после шага $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 \in 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  ): 
              если  --δ[v] = 0 
                  добавьте  v  к  Q 
     , пока  глобальный размер  Q  > 0 

      вернуть  локальный заказ

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

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

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

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

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

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

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

^ Ярнагин, член парламента (1960), Автоматические методы тестирования сетей PERT на согласованность , Технический меморандум № K-24/60, Дальгрен, Вирджиния: Лаборатория вооружения ВМС США.
^ Кан, Артур Б. (1962), «Топологическая сортировка больших сетей», Communications of the ACM , 5 (11): 558–562, doi : 10.1145/368996.369025 , S2CID 16728233
^ Перейти обратно: ^а ^б ^с Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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), «Таксономия проблем с быстрыми параллельными алгоритмами», Information and Control , 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
^ Перейти обратно: ^а ^б Сандерс, Питер; Мельхорн, Курт; Дитцфельбингер, Мартин; Дементьев, Роман (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

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

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

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

[Jarnagin-1] Ярнагин, член парламента (1960), Автоматические методы тестирования сетей PERT на согласованность , Технический меморандум № K-24/60, Дальгрен, Вирджиния: Лаборатория вооружения ВМС США.

[Kahn-2] Кан, Артур Б. (1962), «Топологическая сортировка больших сетей», Communications of the ACM , 5 (11): 558–562, doi : 10.1145/368996.369025 , S2CID 16728233

[CLRS-3] Перейти обратно: ^а ^б ^с Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Раздел 22.4: Топологическая сортировка», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 549–552, ISBN 0-262-03293-7

[Tarjan-4] Тарьян, Роберт Э. (1976), «Непересекающиеся по краям связующие деревья и поиск в глубину», Acta Informatica , 6 (2): 171–185, doi : 10.1007/BF00268499 , S2CID 12044793

[Cook-5] Кук, Стивен А. (1985), «Таксономия проблем с быстрыми параллельными алгоритмами», Information and Control , 64 (1–3): 2–22, doi : 10.1016/S0019-9958(85)80041-3

[DNS-6] Декель, Элиэзер; Насими, Дэвид; Сахни, Сартадж (1981), «Параллельные матричные и графовые алгоритмы», SIAM Journal on Computing , 10 (4): 657–675, doi : 10.1137/0210049 , MR 0635424

[SMDD-7] Перейти обратно: ^а ^б Сандерс, Питер; Мельхорн, Курт; Дитцфельбингер, Мартин; Дементьев, Роман (2019), Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов , Springer International Publishing, ISBN 978-3-030-25208-3

[VM-8] Верне, Освальдо; Маркензон, Лилиан (1997), «Гамильтоновы проблемы для приводимых потокографов» (PDF) , Материалы: 17-я Международная конференция Чилийского общества информатики , стр. 264–267, doi : 10.1109/SCCC.1997.637099 , hdl : 11422/2585 , ISBN 0-8186-8052-0 , S2CID 206554481

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т Это Структуры данных и алгоритмы
Data structures	Array Associative array Binary search tree Fenwick tree Graph Hash table Heap Linked list Queue Segment tree Stack String Tree Trie
Algorithms	Backtracking Binary search Breadth-first search Brute-force search Depth-first search Divide and conquer Dynamic programming Graph traversal Fold Greedy Hash function Minimax Online Randomized Recursion Root-finding Sorting Streaming Sweep line String-searching Topological sorting
List of data structures List of algorithms

v т Это Алгоритмы сортировки
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort
Impractical sorts	Stooge sort Slowsort Bogosort