Topologisk sortering - Topological sorting

I informatikk er en topologisk sortering eller topologisk ordning av en rettet graf en lineær rekkefølge av dens hjørner slik at for hver rettet kant uv fra toppunkt u til toppunkt v , kommer u før v i rekkefølgen. For eksempel kan hjørnene i grafen representere oppgaver som skal utføres, og kantene kan representere begrensninger for at en oppgave må utføres før en annen; i denne applikasjonen er en topologisk rekkefølge bare en gyldig sekvens for oppgavene. Nettopp en topologisk sortering er en grafoverføring der hver node v blir besøkt først etter at alle dens avhengigheter er besøkt . En topologisk rekkefølge er mulig hvis og bare hvis grafen ikke har noen rettede sykluser , det vil si hvis det er en rettet asyklisk graf (DAG). Enhver DAG har minst en topologisk ordning, og algoritmer er kjent for å konstruere en topologisk rekkefølge av en hvilken som helst DAG i lineær tid . Topologisk sortering har mange bruksområder, spesielt i rangeringsproblemer, for eksempel tilbakemelding på lysbue . Topologisk sortering er mulig selv når DAG har frakoblet komponenter .

Eksempler

Den kanoniske anvendelsen av topologisk sortering er i planlegging av en rekke jobber eller oppgaver basert på deres avhengigheter . Jobbene er representert med hjørner, og det er en kant fra x til y hvis jobb x må fullføres før jobb y kan startes (for eksempel når du vasker klær, må vaskemaskinen bli ferdig før vi legger klærne i tørketrommelen) . Deretter gir en topologisk sortering en rekkefølge for å utføre jobbene. En nært beslektet anvendelse av topologiske sorteringsalgoritmer ble først studert på begynnelsen av 1960 -tallet i sammenheng med PERT -teknikken for planlegging i prosjektledelse . I denne applikasjonen representerer hjørnene i en graf milepælene i et prosjekt, og kantene representerer oppgaver som må utføres mellom en milepæl og en annen. Topologisk sortering danner grunnlaget for lineære tidsalgoritmer for å finne prosjektets kritiske vei , en rekke milepæler og oppgaver som styrer lengden på den overordnede prosjektplanen.

I datateknikk, anvendelser av denne type oppstår i instruksjon planlegging , bestilling av formel celle evaluering når ny beregning formelen verdier i regneark , logikk syntese , bestemme rekkefølgen på kompileringsvalg oppgaver å utføre i Make-filer , data serialisering , og løse symbolavhengigheter i linkere . Den brukes også til å bestemme i hvilken rekkefølge tabeller med utenlandske nøkler skal lastes inn i databaser.

Grafen til venstre har mange gyldige topologiske typer, inkludert:

5, 7, 3, 11, 8, 2, 9, 10 (visuell topp til bunn, venstre mot høyre)
3, 5, 7, 8, 11, 2, 9, 10 (minste tilgjengelige toppunkt først)
5, 7, 3, 8, 11, 10, 9, 2 (færrest kanter først)
7, 5, 11, 3, 10, 8, 9, 2 (størst nummerert tilgjengelig toppunkt først)
5, 7, 11, 2, 3, 8, 9, 10 (forsøk fra topp til bunn, fra venstre til høyre)
3, 7, 8, 5, 11, 10, 2, 9 (vilkårlig)

Algoritmer

De vanlige algoritmene for topologisk sortering har lineær kjøretid i antall noder pluss antall kanter, asymptotisk, ${\ displaystyle O (\ venstre | {V} \ høyre |+\ venstre | {E} \ høyre |).}$

Kahns algoritme

En av disse algoritmene, først beskrevet av Kahn (1962) , fungerer ved å velge hjørner i samme rekkefølge som den endelige topologiske sorten. Finn først en liste over "startnoder" som ikke har innkommende kanter, og sett dem inn i et sett S; minst en slik node må finnes i en ikke-tom asyklisk graf. Deretter:

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)

Hvis grafen er en DAG , vil en løsning finnes i listen L (løsningen er ikke nødvendigvis unik). Ellers må grafen ha minst en syklus, og derfor er en topologisk sortering umulig.

Struktur S kan gjenspeile ikke-unikheten til den resulterende sorten, og kan ganske enkelt være et sett eller en kø eller en stabel. Avhengig av rekkefølgen noder n blir fjernet fra sett S, opprettes en annen løsning. En variant av Kahns algoritme som bryter bånd leksikografisk, danner en nøkkelkomponent i Coffman - Graham -algoritmen for parallell planlegging og lagvis graftegning .

Dybde-første søk

En alternativ algoritme for topologisk sortering er basert på dybde-første søk . Algoritmen går gjennom hver node i grafen, i en vilkårlig rekkefølge, og starter et dybde-første søk som avsluttes når den treffer en node som allerede har blitt besøkt siden begynnelsen av den topologiske sorteringen, eller hvis noden ikke har noen utgående kanter (dvs. bladnode):

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

Hver node n blir ført til utgangslisten L bare etter å ha vurdert alle andre noder som er avhengige av n (alle etterkommere av n i grafen). Nærmere bestemt, når algoritmen legger til node n , er vi garantert at alle noder som er avhengige av n allerede er i utgangslisten L: de ble lagt til L enten av den rekursive samtalen om å besøke () som ble avsluttet før samtalen for å besøke n , eller ved en samtale om å besøke () som startet allerede før samtalen om å besøke n . Siden hver kant og node er besøkt en gang, kjører algoritmen i lineær tid. Denne dybde-først-søk-baserte algoritmen er den som er beskrevet av Cormen et al. (2001) ; det ser ut til å ha blitt beskrevet på trykk av Tarjan i 1976.

Parallelle algoritmer

På en parallell maskin for tilfeldig tilgang kan en topologisk ordning konstrueres i O (log ² n ) tid ved å bruke et polynomisk antall prosessorer, noe som setter problemet inn i kompleksitetsklassen NC ² . En metode for å gjøre dette er å gjentatte ganger kvadrere adjasensmatrisen til den gitte grafen, logaritmisk mange ganger, ved å bruke min-pluss matrisemultiplikasjon med maksimalisering i stedet for minimering. Den resulterende matrisen beskriver de lengste baneavstandene i grafen. Sortering av hjørnene etter lengden på de lengste innkommende banene gir en topologisk rekkefølge.

En algoritme for parallell topologisk sortering på distribuerte minnemaskiner parallelliserer algoritmen til Kahn for en DAG . På et høyt nivå fjerner algoritmen til Kahn gjentatte ganger toppunktene 0 og legger dem til den topologiske sorteringen i den rekkefølgen de ble fjernet. Siden de utgående kantene på de fjernede hjørnene også er fjernet, vil det være et nytt sett med hjørner på indeks 0, der prosedyren gjentas til det ikke er noen hjørner igjen. Denne algoritmen utfører iterasjoner, hvor $D$ er den lengste banen i $G$ . Hver iterasjon kan parallelliseres, som er ideen med følgende algoritme. ${\ displaystyle G = (V, E)}$ ${\ displaystyle D+1}$

I det følgende antas det at grafpartisjonen er lagret på $p$ behandlingselementer (PE) som er merket . Hver PE $i$ initialiserer et sett med lokale hjørner med indeks 0, der den øvre indeksen representerer den gjeldende iterasjonen. Siden alle hjørner i de lokale settene har indeks 0, dvs. at de ikke er tilstøtende, kan de gis i vilkårlig rekkefølge for en gyldig topologisk sortering. For å tildele en global indeks til hvert toppunkt, beregnes en prefiks sum over størrelsene på . Så hvert trinn er det lagt hjørner til den topologiske sorteringen. ${\ 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} |}$

Utførelse av den parallelle topologiske sorteringsalgoritmen på en DAG med to behandlingselementer.

I det første trinnet tildeler PE $j$ indeksene til de lokale hjørnene i . Disse hjørnene i blir fjernet, sammen med tilhørende utgående kanter. For hver utgående kant med endepunkt $v$ i en annen PE , blir meldingen lagt ut til PE $l$ . Etter at alle hjørner i er fjernet, sendes de postede meldingene til deres tilsvarende PE. Hver mottatt melding oppdaterer indegret til det lokale toppunktet $v$ . Hvis indeksen faller til null, legges $v$ til . Deretter starter den neste iterasjonen. ${\ textstyle \ sum _ {i = 0}^{j-1} | Q_ {i}^{1} |, \ dots, \ left (\ sum _ {i = 0}^{j} | Q_ {i }^{1} | \ høyre) -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}}$

I trinn $k$ tildeler PE $j$ indeksene , hvor er den totale mengden behandlede hjørner etter trinn . Denne prosedyren gjentas til det ikke er noen hjørner igjen å behandle, derfor . Nedenfor er en oversikt over denne algoritmen på et høyt nivå, enkelt program, pseudokode for flere data . ${\ textstyle a_ {k-1}+\ sum _ {i = 0}^{j-1} | Q_ {i}^{k} |, \ dots, a_ {k-1}+\ venstre (\ sum _ {i = 0}^{j} | Q_ {i}^{k} | \ høyre) -1}$ ${\ displaystyle a_ {k-1}}$ ${\ displaystyle k-1}$ ${\ textstyle \ sum _ {i = 0}^{p-1} | Q_ {i}^{D+1} | = 0}$

Vær oppmerksom på at prefiksummen for de lokale forskyvningene effektivt kan beregnes parallelt. ${\ textstyle a_ {k-1}+\ sum _ {i = 0}^{j-1} | Q_ {i}^{k} |, \ dots, a_ {k-1}+\ venstre (\ sum _ {i = 0}^{j} | Q_ {i}^{k} | \ høyre) -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 \in 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(Q_i, 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(|Q_i|, 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

Kommunikasjonskostnaden avhenger sterkt av den gitte grafpartisjonen. Når det gjelder kjøretid, på en CRCW-PRAM- modell som tillater henting og reduksjon i konstant tid, kjører denne algoritmen inn , der $D$ igjen er den lengste banen i $G$ og $Δ$ maksimal grad. ${\ textstyle {\ mathcal {O}} \ left ({\ frac {m+n} {p}}+D (\ Delta+\ log n) \ right)}$

Søknad til korteste stifunn

Den topologiske rekkefølgen kan også brukes til raskt å beregne korteste stier gjennom en vektet, rettet asyklisk graf. La $V$ være listen over hjørner i en slik graf, i topologisk rekkefølge. Da den følgende algoritme beregner den korteste veien fra en kilde toppunktet $s$ til alle andre hjørnene:

La $d$ være en matrise av samme lengde som $V$ ; dette vil holde de korteste avstandene fra $s$ . Sett $d [s] = 0$ , alle andre $d [u] = \infty$ .
La $p$ være en matrise av samme lengde som $V$ , med alle elementene initialisert til null . Hver $p [u]$ vil holde forgjengeren til $u$ på den korteste veien fra $s$ til $u$ .
Sløyfe over hjørnene u som bestilt i V , fra s :
- For hvert toppunkt v direkte etter u (dvs. det finnes en kant fra u til v ):
  - La $w$ være vekten av kanten fra $u$ til $v$ .
  - Slapp av kanten: hvis d [ v ]> d [ u ] + w , sett
    - $d [v] \leftarrow d [u] + w$ ,
    - $p [v] \leftarrow u$ .

Tilsvarende:

La $d$ være en matrise av samme lengde som $V$ ; dette vil holde de korteste avstandene fra $s$ . Sett $d [s] = 0$ , alle andre $d [u] = \infty$ .
La $p$ være en matrise av samme lengde som $V$ , med alle elementene initialisert til null . Hver $p [u]$ vil holde forgjengeren til $u$ på den korteste veien fra $s$ til $u$ .
Sløyfe over hjørnene u som bestilt i V , fra s :
- For hvert toppunkt v til u (dvs. det finnes en kant fra v til u ):
  - La $w$ være vekten av kanten fra $v$ til $u$ .
  - Slapp av kanten: hvis d [ u ]> d [ v ] + w , sett
    - $d [u] \leftarrow d [v] + w$ ,
    - $p [u] \leftarrow v$ .

På en graf med $n$ hjørner og $m$ kanter tar denne algoritmen $Θ (n + m)$ , dvs. lineær , tid.

Unikhet

Hvis en topologisk sortering har egenskapen til at alle par påfølgende hjørner i den sorterte rekkefølgen er forbundet med kanter, danner disse kantene en rettet hamiltonske bane i DAG . Hvis det finnes en Hamiltonian -bane, er den topologiske sorteringsrekkefølgen unik; ingen annen orden respekterer kantene på banen. Omvendt, hvis en topologisk sortering ikke danner en Hamiltonian -bane, vil DAG ha to eller flere gyldige topologiske bestillinger, for i dette tilfellet er det alltid mulig å danne en andre gyldig bestilling ved å bytte to påfølgende hjørner som ikke er forbundet med en kant til hverandre. Derfor er det mulig å teste i lineær tid om det finnes en unik rekkefølge, og om det finnes en Hamiltonian-bane, til tross for NP-hardheten til det Hamiltoniske baneproblemet for mer generelt dirigerte grafer (dvs. syklisk dirigerte grafer).

Forhold til delordre

Topologiske ordener er også nært knyttet til begrepet lineær forlengelse av en delvis orden i matematikk. Et delvis ordnet sett er bare et sett med objekter sammen med en definisjon av "≤" ulikhetsforholdet, som tilfredsstiller aksiomene for refleksivitet ( x ≤ x ), antisymmetri (hvis x ≤ y og y ≤ x så x = y ) og transitivitet (hvis x ≤ y og y ≤ z , så x ≤ z ). En total rekkefølge er en delvis rekkefølge der, for hver to objekter x og y i settet, enten x ≤ y eller y ≤ x . Totale ordrer er kjent innen informatikk som sammenligningsoperatørene som trengs for å utføre sammenligningssorteringsalgoritmer . For endelige sett kan totale ordrer identifiseres med lineære sekvenser av objekter, der "≤" -forholdet er sant når det første objektet går foran det andre objektet i rekkefølgen; en sammenligningssorteringsalgoritme kan brukes til å konvertere en total ordre til en sekvens på denne måten. En lineær forlengelse av en delrekkefølge er en total orden som er kompatibel med den, i den forstand at hvis x ≤ y i delordenen, så x ≤ y i den totale rekkefølgen også.

Man kan definere en delvis rekkefølge fra en hvilken som helst DAG ved å la settet med objekter være hjørnene til DAG, og definere x ≤ y for å være sant, for alle to hjørner x og y , når det finnes en rettet vei fra x til y ; det vil si når y er tilgjengelig fra x . Med disse definisjonene er en topologisk ordning av DAG det samme som en lineær forlengelse av denne delordenen. Motsatt kan enhver delvis bestilling defineres som tilgjengelighetsforholdet i en DAG. En måte å gjøre dette på er å definere en DAG som har et toppunkt for hvert objekt i det delvis ordnede settet, og en kant xy for hvert objektpar som x ≤ y . En alternativ måte å gjøre dette på er å bruke den transitive reduksjonen av den delvise ordningen; generelt produserer dette DAGs med færre kanter, men tilgjengelighetsforholdet i disse DAGene er fortsatt den samme delordenen. Ved å bruke disse konstruksjonene kan man bruke topologiske ordningsalgoritmer for å finne lineære utvidelser av delordener.

Se også

tsort , et Unix -program for topologisk sortering
Tilbakemeldingsbuesett , et sett med kanter hvis fjerning gjør at den gjenværende undergrafen kan sorteres topologisk
Tarjans sterkt tilkoblede komponentalgoritme , en algoritme som gir den topologisk sorterte listen over sterkt tilkoblede komponenter i en graf
Pre-topologisk rekkefølge

Referanser

Videre lesning

DE Knuth , The Art of Computer Programming , bind 1, avsnitt 2.2.3, som gir en algoritme for topologisk sortering av en delvis ordning, og en kort historie.

Languages

In other projects