Rilevazione incrementale di dominatori nei DAG

Question

Supponiamo di disporre di un DAG con una sorgente. Vorrei trovare i nodi n in modo tale che qualsiasi percorso completo dalla sorgente venga eseguito tramite n (ad esempio, n domina tutti i sink). In altre parole: se abbiamo rimosso tutti i successori di n, tutti i percorsi termineranno in n. Il problema è che i nodi vengono contrassegnati in modo incrementale come cancellati nel DAG. Poiché i nodi vengono contrassegnati come eliminati, altri nodi possono iniziare a soddisfare la suddetta proprietà. Come posso rilevare in modo efficiente questo come succede?

Punti bonus se la struttura dati può farlo con più origini in un modo più efficiente rispetto all'esecuzione dell'algoritmo per una singola fonte separatamente su ciascuna delle fonti.

Answer 1

Ordinare topologicamente questo DAG per stabilire un ordine per i suoi nodi. Per ogni nodo, il suo valore sarebbe il numero di bordi in uscita da tutti i nodi precedenti meno il numero di fronti in entrata per tutti i nodi precedenti e il nodo corrente. Il valore per il nodo "Dominator" è sempre zero.

Dopo che un nodo è contrassegnato come "eliminato", inserire i suoi predecessori e successori nella coda di priorità. La priorità è determinata dall'ordinamento topologico. Aggiorna i valori per tutti i nodi, seguendo il nodo "eliminato" (aggiungi il numero di nodi in ingresso e sottrai il numero di nodi in uscita per questo nodo). Allo stesso tempo (nello stesso ordine) il valore di decremento per ciascun nodo tra il nodo predecessore nella coda di priorità e il nodo "cancellato" e il valore di incremento per ciascun nodo, a partire dal nodo successore nella coda di priorità. Interrompi quando il valore di qualche nodo è decrementato a zero. Questo è un nuovo nodo "dominatore". Se tutti i nodi "dominatori" sono necessari, continuare fino alla fine del grafico.

delete(delNode): 
    for each predecessor in delNode.predecessors: queue.add(predecessor) 
    for each successor in delNode.successors: queue.add(successor) 
    for each node in DAG: 
    if queue.top.priority == node.priority > delNode.priority: 
     ++accumulator 

    node.value += accumulator 
    if node.value == 0: dominatorDetected(node) 

    if node.priority == delNode.priority: 
     accumulator += (delNode.predecessors.size - delNode.successors.size) 
     node.value = -1 

    if queue.top.priority == node.priority: 
     queue.pop() 
     if node.priority < delNode.priority: 
     --accumulator 

    if queue.empty: stop 

per il caso di più fonti, è possibile utilizzare lo stesso algoritmo, ma mantenere una lista di "valori" per ogni nodo, un valore per ciascuna sorgente. La complessità dell'algoritmo è O(Nodes * Sources), lo stesso che per la ricerca indipendente su ciascuna delle fonti. Ma il programma può essere reso più efficiente se si utilizza la vettorizzazione. "valori" possono essere elaborati in parallelo con le istruzioni SIMD. I compilatori moderni possono fare la vettorizzazione automatica per ottenerlo.