Ordinamento topologico - Topological sorting

In informatica , un ordinamento topologico o un ordinamento topologico di un grafo orientato è un ordinamento lineare dei suoi vertici tale che per ogni arco diretto uv dal vertice u al vertice v , u viene prima di v nell'ordinamento. Ad esempio, i vertici del grafico possono rappresentare compiti da eseguire e gli archi possono rappresentare vincoli che un compito deve essere eseguito prima di un altro; in questa applicazione, un ordinamento topologico è solo una sequenza valida per le attività. Precisamente, un ordinamento topologico è un attraversamento di grafi in cui ogni nodo v viene visitato solo dopo che sono state visitate tutte le sue dipendenze . Un ordinamento topologico è possibile se e solo se il grafo non ha cicli diretti , cioè se è un grafo aciclico orientato (DAG). Qualsiasi DAG ha almeno un ordinamento topologico e sono noti algoritmi per costruire un ordinamento topologico di qualsiasi DAG in tempo lineare . L'ordinamento topologico ha molte applicazioni, specialmente nei problemi di classificazione come l' impostazione dell'arco di feedback . L'ordinamento topologico è possibile anche quando il DAG ha dei componenti scollegati .

Esempi

L'applicazione canonica dell'ordinamento topologico consiste nella pianificazione di una sequenza di lavori o attività in base alle loro dipendenze . I lavori sono rappresentati da vertici e c'è un bordo da x a y se il lavoro x deve essere completato prima che il lavoro y possa essere avviato (ad esempio, quando si lavano i vestiti, la lavatrice deve finire prima di mettere i vestiti nell'asciugatrice) . Quindi, un ordinamento topologico fornisce un ordine in cui eseguire i lavori. Un'applicazione strettamente correlata degli algoritmi di ordinamento topologico è stata studiata per la prima volta nei primi anni '60 nel contesto della tecnica PERT per la pianificazione nella gestione dei progetti . In questa applicazione, i vertici di un grafico rappresentano le pietre miliari di un progetto e i bordi rappresentano le attività che devono essere eseguite tra una pietra miliare e l'altra. L'ordinamento topologico costituisce la base degli algoritmi a tempo lineare per trovare il percorso critico del progetto, una sequenza di pietre miliari e attività che controlla la lunghezza della pianificazione complessiva del progetto.

In informatica, applicazioni di questo tipo sorgono nella pianificazione delle istruzioni , nell'ordinamento della valutazione delle celle delle formule durante il ricalcolo dei valori delle formule nei fogli di calcolo , nella sintesi logica , nella determinazione dell'ordine delle attività di compilazione da eseguire nei makefile , nella serializzazione dei dati e nella risoluzione delle dipendenze dei simboli nei linker . Viene anche utilizzato per decidere in quale ordine caricare le tabelle con chiavi esterne nei database.

Grafico aciclico orientato 2.svg
Il grafico mostrato a sinistra ha molti ordinamenti topologici validi, tra cui:
  • 5, 7, 3, 11, 8, 2, 9, 10 (visuale dall'alto in basso, da sinistra a destra)
  • 3, 5, 7, 8, 11, 2, 9, 10 (prima il vertice disponibile con il numero più piccolo)
  • 5, 7, 3, 8, 11, 10, 9, 2 (prima il minor numero di bordi)
  • 7, 5, 11, 3, 10, 8, 9, 2 (prima il vertice disponibile con il numero maggiore)
  • 5, 7, 11, 2, 3, 8, 9, 10 (tentativo dall'alto verso il basso, da sinistra a destra)
  • 3, 7, 8, 5, 11, 10, 2, 9 (arbitrario)

Algoritmi

I soliti algoritmi per l'ordinamento topologico hanno tempo di esecuzione lineare nel numero di nodi più il numero di archi, asintoticamente,

Algoritmo di Kahn

Uno di questi algoritmi, descritto per la prima volta da Kahn (1962) , funziona scegliendo i vertici nello stesso ordine dell'eventuale ordinamento topologico. Per prima cosa, trova una lista di "nodi iniziali" che non hanno archi entranti e inseriscili in un insieme S; almeno uno di questi nodi deve esistere in un grafo aciclico non vuoto. Quindi:

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)

Se il grafico è un DAG , una soluzione sarà contenuta nell'elenco L (la soluzione non è necessariamente unica). In caso contrario, il grafo deve avere almeno un ciclo e quindi un ordinamento topologico è impossibile.

Riflettendo la non unicità dell'ordinamento risultante, la struttura S può essere semplicemente un insieme o una coda o uno stack. A seconda dell'ordine in cui i nodi n vengono rimossi dall'insieme S, viene creata una soluzione diversa. Una variazione dell'algoritmo di Kahn che rompe i legami lessicograficamente costituisce un componente chiave dell'algoritmo di Coffman-Graham per la pianificazione parallela e il disegno di grafici a strati .

Ricerca in profondità

Un algoritmo alternativo per l'ordinamento topologico si basa sulla ricerca in profondità . L'algoritmo scorre ogni nodo del grafo, in un ordine arbitrario, avviando una ricerca in profondità che termina quando colpisce un nodo che è già stato visitato dall'inizio dell'ordinamento topologico o il nodo non ha bordi in uscita (cioè un nodo foglia):

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

Ogni nodo n viene anteposto alla lista di output L solo dopo aver considerato tutti gli altri nodi che dipendono da n (tutti i discendenti di n nel grafo). Nello specifico, quando l'algoritmo aggiunge il nodo n , abbiamo la garanzia che tutti i nodi che dipendono da n sono già nella lista di output L: sono stati aggiunti a L o dalla chiamata ricorsiva a visit() che è terminata prima della chiamata a visitare n , o da una chiamata a visit() iniziata anche prima della chiamata a visitare n . Poiché ogni arco e nodo viene visitato una volta, l'algoritmo viene eseguito in tempo lineare. Questo algoritmo basato sulla ricerca in profondità è quello descritto da Cormen et al. (2001) ; sembra che sia stato descritto per la prima volta a stampa da Tarjan nel 1976.

Algoritmi paralleli

Su una macchina parallela ad accesso casuale , un ordinamento topologico può essere costruito in tempo O (log 2 n ) utilizzando un numero polinomiale di processori, ponendo il problema nella classe di complessità NC 2 . Un metodo per farlo consiste nel quadrare ripetutamente la matrice di adiacenza del grafico dato, logaritmicamente molte volte, usando la moltiplicazione della matrice min-plus con la massimizzazione al posto della minimizzazione. La matrice risultante descrive le distanze del percorso più lunghe nel grafico. L'ordinamento dei vertici in base alla lunghezza dei loro percorsi in entrata più lunghi produce un ordinamento topologico.

Un algoritmo per l'ordinamento topologico parallelo su macchine a memoria distribuita parallelizza l'algoritmo di Kahn per un DAG . Ad alto livello, l'algoritmo di Kahn rimuove ripetutamente i vertici di grado 0 e li aggiunge all'ordinamento topologico nell'ordine in cui sono stati rimossi. Poiché vengono rimossi anche i bordi in uscita dei vertici rimossi, ci sarà un nuovo insieme di vertici di grado 0, in cui la procedura viene ripetuta finché non rimangono più vertici. Questo algoritmo esegue iterazioni, dove D è il percorso più lungo in G . Ogni iterazione può essere parallelizzata, che è l'idea del seguente algoritmo.

Nel seguito si assume che la partizione del grafo sia memorizzata su p elementi di elaborazione (PE) che sono etichettati . Ogni PE i inizializza un insieme di vertici locali con grado 0, dove l'indice superiore rappresenta l'iterazione corrente. Poiché tutti i vertici negli insiemi locali hanno grado 0, cioè non sono adiacenti, possono essere dati in un ordine arbitrario per un ordinamento topologico valido. Per assegnare un indice globale a ciascun vertice, viene calcolata una somma di prefissi sulle dimensioni di . Quindi ad ogni passaggio vengono aggiunti vertici all'ordinamento topologico.

Esecuzione dell'algoritmo di ordinamento topologico parallelo su un DAG con due elementi di elaborazione.

Nella prima fase, PE j assegna gli indici ai vertici locali in . Questi vertici interni vengono rimossi, insieme ai corrispondenti bordi in uscita. Per ogni fronte in uscita con endpoint v in un altro PE , il messaggio viene inviato a PE l . Dopo che tutti i vertici in sono stati rimossi, i messaggi inviati vengono inviati al loro PE corrispondente. Ogni messaggio ricevuto aggiorna il grado del vertice locale v . Se il grado scende a zero, v viene aggiunto a . Quindi inizia l'iterazione successiva.

Nella fase k , PE j assegna gli indici , dove è la quantità totale di vertici elaborati dopo la fase . Questa procedura si ripete finché non rimangono più vertici da elaborare, quindi . Di seguito è riportata una panoramica di pseudo codice di alto livello, singolo programma, dati multipli di questo algoritmo.

Si noti che la somma dei prefissi per gli offset locali può essere calcolata in modo efficiente in parallelo.

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 = {vV | δ[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

Il costo della comunicazione dipende fortemente dalla partizione del grafico data. Da per runtime, su un CRCW-PRAM modello che permette recuperare e-decremento nel tempo costante, questo algoritmo viene eseguito in , dove D è nuovamente il percorso più lungo in G e Δ il massimo grado.

Applicazione per trovare il percorso più breve

L'ordinamento topologico può anche essere usato per calcolare rapidamente cammini minimi attraverso una ponderata grafo orientato aciclico. Sia V l'elenco dei vertici in tale grafo, in ordine topologico. Quindi il seguente algoritmo calcola il percorso più breve da alcuni vertici sorgente s a tutti gli altri vertici:

  • Sia d un array della stessa lunghezza di V ; questo manterrà le distanze del percorso più breve da s . Poni d [ s ] = 0 , tutti gli altri d [ u ] = ∞ .
  • Sia p un array della stessa lunghezza di V , con tutti gli elementi inizializzati a nil . Ogni p [ u ] manterrà il predecessore di u nel percorso più breve da s a u .
  • Loop sui vertici u come ordinato in V , a partire da s :
    • Per ogni vertice v che segue direttamente u (cioè esiste un arco da u a v ):
      • Sia w il peso del bordo da u a v .
      • Rilassa il bordo: se d [ v ] > d [ u ] + w , set
        • d [ v ] ← d [ u ] + w ,
        • p [ v ] ← u .

Equivalentemente:

  • Sia d un array della stessa lunghezza di V ; questo manterrà le distanze del percorso più breve da s . Poni d [ s ] = 0 , tutti gli altri d [ u ] = ∞ .
  • Sia p un array della stessa lunghezza di V , con tutti gli elementi inizializzati a nil . Ogni p [ u ] manterrà il predecessore di u nel percorso più breve da s a u .
  • Loop sui vertici u come ordinato in V , a partire da s :
    • Per ogni vertice v in u (cioè esiste un arco da v a u ):
      • Sia w il peso del bordo da v a u .
      • Rilassa il bordo: se d [ u ] > d [ v ] + w , set
        • d [ u ] ← d [ v ] + w ,
        • p [ u ] ← v .

Su un grafo di n vertici e m bordi, questo algoritmo impiega Θ( n + m ) , cioè lineare , tempo.

Unicità

Se un ordinamento topologico ha la proprietà che tutte le coppie di vertici consecutivi nell'ordine ordinato sono collegate da archi, allora questi archi formano un cammino hamiltoniano diretto nel DAG . Se esiste un cammino hamiltoniano, l'ordinamento topologico è unico; nessun altro ordine rispetta i bordi del percorso. Viceversa, se un ordinamento topologico non forma un cammino hamiltoniano, il DAG avrà due o più ordinamenti topologici validi, poiché in questo caso è sempre possibile formare un secondo ordinamento valido scambiando due vertici consecutivi che non sono collegati da un arco l'uno all'altro. Pertanto, è possibile verificare in tempo lineare se esiste un unico ordinamento e se esiste un cammino hamiltoniano, nonostante la durezza NP del problema del cammino hamiltoniano per grafi orientati più generali (cioè grafi orientati ciclici).

Relazione con ordini parziali

Gli ordinamenti topologici sono anche strettamente correlati al concetto di estensione lineare di un ordine parziale in matematica. Un insieme parzialmente ordinato è solo un insieme di oggetti insieme a una definizione della relazione di disuguaglianza "≤", che soddisfa gli assiomi di riflessività ( x  ≤  x ), antisimmetria (se x  ≤  y e y  ≤  x allora x  =  y ) e transitività (se x  ≤  y e y  ≤  z , allora x  ≤  z ). Un ordine totale è un ordine parziale in cui, per ogni due oggetti x e y nel set, sia x  ≤  y o y  ≤  x . Gli ordini totali sono familiari in informatica come operatori di confronto necessari per eseguire algoritmi di ordinamento per confronto . Per gli insiemi finiti, gli ordini totali possono essere identificati con sequenze lineari di oggetti, dove la relazione "≤" è vera ogni volta che il primo oggetto precede il secondo oggetto nell'ordine; un algoritmo di ordinamento per confronto può essere utilizzato per convertire un ordine totale in una sequenza in questo modo. Un'estensione lineare di un ordine parziale è un ordine totale compatibile con esso, nel senso che, se x  ≤  y nell'ordine parziale, allora x  ≤  y anche nell'ordine totale.

Si può definire un ordinamento parziale da qualsiasi DAG lasciando che l'insieme degli oggetti siano i vertici del DAG e definendo x  ≤  y come vero, per due vertici x e y qualsiasi , ogni volta che esiste un cammino diretto da x a y ; cioè, ogni volta che y è raggiungibile da x . Con queste definizioni, un ordinamento topologico del DAG è la stessa cosa di un'estensione lineare di questo ordine parziale. Al contrario, qualsiasi ordinamento parziale può essere definito come la relazione di raggiungibilità in un DAG. Un modo per farlo è definire un DAG che abbia un vertice per ogni oggetto nell'insieme parzialmente ordinato e un arco xy per ogni coppia di oggetti per cui x  ≤  y . Un modo alternativo per farlo è utilizzare la riduzione transitiva dell'ordinamento parziale; in generale, questo produce DAG con meno bordi, ma la relazione di raggiungibilità in questi DAG è ancora lo stesso ordine parziale. Usando queste costruzioni, si possono usare algoritmi di ordinamento topologico per trovare estensioni lineari di ordini parziali.

Guarda anche

Riferimenti

Ulteriori letture

link esterno