Sortowanie topologiczne - Topological sorting

W informatyce , A topologiczna sortowania lub topologiczna zamawiania z skierowanej wykresu jest liniowy Kolejność jego wierzchołków , że dla każdej krawędzi skierowanej UV z wierzchołkiem litery U do wierzchołka V , U jest przed V w kolejności. Na przykład wierzchołki grafu mogą reprezentować zadania do wykonania, a krawędzie mogą reprezentować ograniczenia, że ​​jedno zadanie musi być wykonane przed innym; w tej aplikacji uporządkowanie topologiczne jest tylko prawidłową sekwencją zadań. Dokładniej, sortowanie topologiczne to przechodzenie przez graf, w którym każdy węzeł v jest odwiedzany dopiero po odwiedzeniu wszystkich jego zależności . Porządkowanie topologiczne jest możliwe wtedy i tylko wtedy, gdy graf nie ma cykli skierowanych , to znaczy, jeśli jest skierowanym grafem acyklicznym (DAG). Każdy DAG ma co najmniej jedno uporządkowanie topologiczne, a znane są algorytmy do konstruowania uporządkowania topologicznego dowolnego DAG w czasie liniowym . Sortowanie topologiczne ma wiele zastosowań, zwłaszcza w problemach rankingowych, takich jak zestaw sprzężenia zwrotnego . Sortowanie topologiczne jest możliwe nawet wtedy, gdy DAG ma odłączone komponenty .

Przykłady

Kanoniczne zastosowanie sortowania topologicznego polega na planowaniu sekwencji zadań lub zadań w oparciu o ich zależności . Zadania są reprezentowane przez wierzchołki i występuje krawędź od x do y, jeśli zadanie x musi zostać zakończone przed rozpoczęciem zadania y (na przykład podczas prania ubrań pralka musi zakończyć, zanim włożymy ubrania do suszarki) . Następnie sortowanie topologiczne podaje kolejność wykonywania zadań. Ściśle powiązane zastosowanie algorytmów sortowania topologicznego zostało po raz pierwszy zbadane na początku lat sześćdziesiątych w kontekście techniki PERT do planowania w zarządzaniu projektami . W tej aplikacji wierzchołki wykresu reprezentują kamienie milowe projektu, a krawędzie reprezentują zadania, które muszą zostać wykonane między jednym kamieniem milowym a drugim. Sortowanie topologiczne stanowi podstawę algorytmów czasu liniowego do znajdowania ścieżki krytycznej projektu, sekwencji kamieni milowych i zadań, które kontrolują długość ogólnego harmonogramu projektu.

W informatyce zastosowania tego typu pojawiają się w szeregowaniu instrukcji , porządkowaniu oceny komórek formuły podczas przeliczania wartości formuł w arkuszach kalkulacyjnych , syntezie logicznej , określaniu kolejności zadań kompilacji do wykonania w plikach makefile , serializacji danych i rozwiązywaniu zależności symboli w linkerach . Służy również do decydowania, w jakiej kolejności ładować tabele z kluczami obcymi w bazach danych.

Wykres pokazany po lewej ma wiele prawidłowych sortowań topologicznych, w tym: 5, 7, 3, 11, 8, 2, 9, 10 (wizualnie od góry do dołu, od lewej do prawej) 3, 5, 7, 8, 11, 2, 9, 10 (najpierw najmniejszy dostępny wierzchołek) 5, 7, 3, 8, 11, 10, 9, 2 (najmniej krawędzi najpierw) 7, 5, 11, 3, 10, 8, 9, 2 (najpierw o największym dostępnym wierzchołku) 5, 7, 11, 2, 3, 8, 9, 10 (próba od góry do dołu, od lewej do prawej) 3, 7, 8, 5, 11, 10, 2, 9 (dowolne)

Algorytmy

Zwykłe algorytmy sortowania topologicznego mają czas działania liniowy w liczbie węzłów plus liczba krawędzi, asymptotycznie, ${\ Displaystyle O (\ po lewej | {V} \ po prawej | + \ po lewej | {E} \ po prawej |).}$

Algorytm Kahna

Jeden z tych algorytmów, po raz pierwszy opisany przez Kahna (1962) , działa poprzez wybieranie wierzchołków w tej samej kolejności, co ostateczne sortowanie topologiczne. Najpierw znajdź listę "węzłów początkowych", które nie mają krawędzi przychodzących i wstaw je do zbioru S; co najmniej jeden taki węzeł musi istnieć w niepustym grafie acyklicznym. Następnie:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

Jeśli wykres jest DAG , rozwiązanie będzie zawarte na liście L (rozwiązanie niekoniecznie jest unikalne). W przeciwnym razie graf musi mieć co najmniej jeden cykl i dlatego sortowanie topologiczne jest niemożliwe.

Odzwierciedlając nieunikalność wynikowego rodzaju, struktura S może być po prostu zestawem, kolejką lub stosem. W zależności od kolejności usuwania węzłów n ze zbioru S tworzone jest inne rozwiązanie. Odmiana algorytmu Kahna, który leksykograficznie przełamuje więzi, stanowi kluczowy składnik algorytmu Coffmana-Grahama do równoległego planowania i rysowania wykresów warstwowych .

Wyszukiwanie w głąb

Alternatywny algorytm sortowania topologicznego opiera się na przeszukiwaniu w głąb . Algorytm przechodzi w pętlę przez każdy węzeł grafu w dowolnej kolejności, inicjując wyszukiwanie w głąb, które kończy się, gdy trafi na dowolny węzeł, który był już odwiedzany od początku sortowania topologicznego lub węzeł nie ma krawędzi wychodzących (tj. węzeł liścia):

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

Każdy węzeł n jest dodawany do listy wyjściowej L dopiero po uwzględnieniu wszystkich innych węzłów, które zależą od n (wszystkich potomków n na grafie). W szczególności, gdy algorytm dodaje węzeł n , mamy gwarancję, że wszystkie węzły zależne od n są już na liście wyjściowej L: zostały dodane do L albo przez rekurencyjne wywołanie visit() , które zakończyło się przed wywołaniem visit n , lub przez wywołanie visit(), które rozpoczęło się jeszcze przed wywołaniem visit n . Ponieważ każda krawędź i węzeł są odwiedzane raz, algorytm działa w czasie liniowym. Ten algorytm oparty na wyszukiwaniu w głąb jest opisany przez Cormena i in. (2001) ; wydaje się, że został po raz pierwszy opisany w druku przez Tarjana w 1976 roku.

Algorytmy równoległe

Na równoległej maszynie o swobodnym dostępie , uporządkowanie topologiczne może być skonstruowane w czasie O (log ² n ) przy użyciu wielomianowej liczby procesorów, umieszczając problem w klasie złożoności NC ² . Jedną z metod jest wielokrotne podnoszenie do kwadratu macierzy sąsiedztwa danego grafu, logarytmicznie wiele razy, przy użyciu mnożenia macierzy min-plus z maksymalizacją zamiast minimalizacji. Otrzymana macierz opisuje najdłuższe odległości ścieżek na wykresie. Sortowanie wierzchołków według długości ich najdłuższych ścieżek przychodzących daje porządek topologiczny.

Algorytm równoległego sortowania topologicznego na maszynach z pamięcią rozproszoną paralelizuje algorytm Kahna dla DAG . Na wysokim poziomie algorytm Kahna wielokrotnie usuwa wierzchołki stopnia wewnętrznego 0 i dodaje je do sortowania topologicznego w kolejności, w jakiej zostały usunięte. Ponieważ wychodzące krawędzie usuniętych wierzchołków są również usuwane, pojawi się nowy zestaw wierzchołków stopnia wewnętrznego 0, w którym procedura jest powtarzana, aż nie zostaną żadne wierzchołki. Ten algorytm wykonuje iteracje, gdzie D jest najdłuższą ścieżką w G . Każda iteracja może być zrównoleglona, ​​co jest ideą następującego algorytmu. ${\ Displaystyle G = (V, E)}$${\ Displaystyle D+1}$

W dalszej części zakłada się, że partycja grafu jest przechowywana na p elementów przetwarzających (PE), które są oznaczone etykietą . Każdy PE i inicjalizuje zbiór lokalnych wierzchołków o stopniu wewnętrznym 0, gdzie górny indeks reprezentuje bieżącą iterację. Ponieważ wszystkie wierzchołki w zbiorach lokalnych mają stopień 0, tj. nie sąsiadują ze sobą, można je podać w dowolnej kolejności, aby zapewnić prawidłowe sortowanie topologiczne. Aby przypisać indeks globalny do każdego wierzchołka, obliczana jest suma prefiksów dla rozmiarów . Tak więc na każdym kroku do sortowania topologicznego dodawane są wierzchołki. ${\displaystyle 0,\kropki,p-1}$${\ Displaystyle Q_ {i} ^ {1}}$${\ Displaystyle Q_ {0}^ {1}, \ kropki, Q_ {p-1} ^ {1}}$${\ Displaystyle Q_ {0}^ {1}, \ kropki, Q_ {p-1} ^ {1}}$${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$

Wykonanie równoległego algorytmu sortowania topologicznego na DAG z dwoma elementami przetwarzającymi.

W pierwszym kroku PE j przypisuje indeksy do lokalnych wierzchołków w . Te wierzchołki są usuwane wraz z odpowiadającymi im krawędziami wychodzącymi. Dla każdej krawędzi wychodzącej z punktem końcowym v w innym PE wiadomość jest wysyłana do PE 1 . Po usunięciu wszystkich wierzchołków , opublikowane wiadomości są wysyłane do odpowiedniego PE. Każdy odebrany komunikat aktualizuje stopień wierzchołka lokalnego v . Jeśli stopień spadnie do zera, v dodaje się do . Następnie rozpoczyna się kolejna iteracja. ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i }^{1}|\prawo)-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}}$

W kroku k PE j przypisuje indeksy , gdzie jest całkowitą ilością przetworzonych wierzchołków po kroku . Ta procedura jest powtarzana do momentu, gdy nie ma już wierzchołków do przetworzenia, stąd . Poniżej znajduje się omówienie tego algorytmu na wysokim poziomie, pojedynczego programu, wielu danych pseudokodu. ${\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}$

Zauważ, że suma przedrostków dla lokalnych odsunięć może być efektywnie obliczana równolegle. ${\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 processing elements with IDs from 0 to p-1
Input: G = (V, E) DAG, distributed to PEs, PE index j = 0, ..., p - 1
Output: topological sorting of G

function traverseDAGDistributed
    δ incoming degree of local vertices V
    Q = {v ∈ V | δ[v] = 0}                     // All vertices with indegree 0
    nrOfVerticesProcessed = 0

    do                 
        global build prefix sum over size of Q     // get offsets and total amount of vertices in this step
        offset = nrOfVerticesProcessed + sum(Qi, i = 0 to j - 1)          // j is the processor index
        foreach u in Q                                       
            localOrder[u] = index++;
            foreach (u,v) in E do post message (u, v) to PE owning vertex v
        nrOfVerticesProcessed += sum(|Qi|, i = 0 to p - 1)
        deliver all messages to neighbors of vertices in Q  
        receive messages for local vertices V
        remove all vertices in Q
        foreach message (u, v) received:
            if --δ[v] = 0
                add v to Q
    while global size of Q > 0

    return localOrder

Koszt komunikacji w dużym stopniu zależy od danego podziału grafu. Jeśli chodzi o środowisko wykonawcze, w modelu CRCW-PRAM, który umożliwia pobieranie i dekrementację w stałym czasie, ten algorytm działa w , gdzie D jest ponownie najdłuższą ścieżką w G, a Δ maksymalnym stopniem. ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$

Aplikacja do wyszukiwania najkrótszej ścieżki

Porządkowanie topologiczne może być również wykorzystywane do szybkiego obliczania najkrótszych ścieżek na ważonym, skierowanym grafie acyklicznym. Niech V będzie listą wierzchołków takiego grafu w porządku topologicznym. Następnie algorytm oblicza następujący najkrótsza ścieżka z niektórych źródło wierzchołek s do wszystkich pozostałych wierzchołków:

Równoważnie:

Na wykresie złożonym z n wierzchołków i m krawędzi algorytm ten zajmuje Θ( n + m ) , czyli liniowy , czas.

Wyjątkowość

Jeżeli sortowanie topologiczne ma tę właściwość, że wszystkie pary kolejnych wierzchołków w posortowanej kolejności są połączone krawędziami, to krawędzie te tworzą w DAG ukierunkowaną ścieżkę hamiltonowską . Jeśli istnieje ścieżka hamiltonowska, porządek sortowania topologicznego jest unikalny; żaden inny porządek nie respektuje krawędzi ścieżki. I odwrotnie, jeśli sortowanie topologiczne nie tworzy ścieżki hamiltonowskiej, DAG będzie miał dwa lub więcej prawidłowych uporządkowań topologicznych, ponieważ w tym przypadku zawsze możliwe jest utworzenie drugiego prawidłowego uporządkowania poprzez zamianę dwóch kolejnych wierzchołków, które nie są połączone krawędzią do siebie. Dlatego możliwe jest testowanie w czasie liniowym, czy istnieje jednoznaczne uporządkowanie i czy istnieje ścieżka hamiltonowska, pomimo NP-twardości problemu ścieżki hamiltonowskiej dla bardziej ogólnych grafów skierowanych (tj. grafów skierowanych cyklicznie).

Stosunek do zamówień częściowych

Topologiczne uporządkowania są również ściśle związane z pojęciem liniowego rozszerzenia o częściowym porządku w matematyce. Zbiór częściowo uporządkowany to po prostu zbiór obiektów wraz z definicją relacji nierówności „≤”, spełniającą aksjomaty refleksyjności ( x  ≤  x ), antysymetrii (jeśli x  ≤  y i y  ≤  x to x  =  y ) i przechodniości (jeśli x  ≤  y i y  ≤  z , to x  ≤  z ). Całkowity celu częściowy kolejność, w jakiej na każde dwa obiekty x i y w zestawie, albo x  ≤  Y lub Y  ≤  x . Całkowite zamówienia są znane w informatyce jako operatory porównania potrzebne do wykonania algorytmów sortowania porównawczego . W przypadku zbiorów skończonych rzędy całkowite mogą być identyfikowane z liniowymi ciągami obiektów, gdzie relacja „≤” jest prawdziwa zawsze, gdy pierwszy obiekt poprzedza drugi obiekt w kolejności; algorytm sortowania porównawczego może być użyty do przekształcenia w ten sposób całkowitego zamówienia w sekwencję. Liniowe rozszerzenie porządku częściowego jest porządkiem całkowitym, który jest z nim zgodny, w tym sensie, że jeśli x  ≤  y w porządku częściowym, to x  ≤  y również w porządku całkowitym.

Można zdefiniować częściowe uporządkowanie z dowolnego DAG, pozwalając zbiorowi obiektów być wierzchołkami DAG i definiując x  ≤  y jako prawdziwe, dla dowolnych dwóch wierzchołków x i y , gdy istnieje skierowana ścieżka od x do y ; to znaczy, gdy y jest osiągalny z x . Przy tych definicjach topologiczny porządek DAG jest tym samym, co liniowe rozszerzenie tego częściowego porządku. I odwrotnie, każde uporządkowanie częściowe można zdefiniować jako relację osiągalności w DAG. Jednym ze sposobów na zrobienie tego jest zdefiniowanie DAG, który ma wierzchołek dla każdego obiektu w częściowo uporządkowanym zestawie i krawędź xy dla każdej pary obiektów, dla których x  ≤  y . Alternatywnym sposobem wykonania tego jest użycie przechodniej redukcji uporządkowania częściowego; ogólnie daje to DAG z mniejszą liczbą krawędzi, ale relacja osiągalności w tych DAG-ach jest nadal taka sama częściowa kolejność. Korzystając z tych konstrukcji, można wykorzystać algorytmy porządkowania topologicznego do znalezienia liniowych rozszerzeń porządków cząstkowych.

Zobacz też

• tsort , uniksowy program do sortowania topologicznego
• Feedback arc set , zbiór krawędzi, których usunięcie umożliwia topologiczne sortowanie pozostałego podgrafu
• Algorytm silnie połączonych komponentów Tarjana , algorytm , który daje posortowaną topologicznie listę silnie połączonych komponentów na grafie
• Porządek pretopologiczny

Bibliografia

Dalsza lektura

• DE Knuth , The Art of Computer Programming , Tom 1, rozdział 2.2.3, który podaje algorytm sortowania topologicznego częściowego uporządkowania i krótką historię.

Linki zewnętrzne

• NIST Słownik algorytmów i struktur danych: sortowanie topologiczne
• Weisstein, Eric W. , „Sortowanie topologiczne” , MathWorld