DAG - Algoritmo per garantire un'unica sorgente e un singolo sink

Question

Devo garantire che un grafico nella nostra applicazione sia un DAG con una fonte univoca e un sink univoco.

In particolare, devo garantire che per un determinato nodo di avvio e nodo finale (entrambi noti all'inizio) che ogni nodo del grafico si trovi su un percorso dal nodo iniziale al nodo finale.

Ho già un'implementazione dell'algoritmo di Tarjan che utilizzo per identificare i cicli e un algoritmo di ordinamento topologico che è possibile eseguire una volta che l'algoritmo di Tarjan segnala che il grafico è un DAG.

Qual è il modo più efficiente per assicurarsi che il grafico soddisfi questo criterio?

Answer 1

Se il grafico è rappresentato da una matrice di adiacenza, il nodo x è un nodo di origine se la x colonna della matrice è 0 ed è un nodo di sink se la riga x della matrice è 0. È possibile eseguire due passaggi rapidi sulla matrice per contare il numero di righe e colonne che sono 0 per determinare quante sorgenti e sink esistono e cosa sono. Questo richiede tempo O (n) ed è probabilmente il modo più veloce per verificare questo.

Se il grafico è rappresentato da un elenco di adiacenze, è possibile trovare tutti i nodi sink nel tempo O (n) controllando se un nodo non ha bordi in uscita. Puoi trovare tutti i sink mantenendo per ogni nodo un valore booleano che indica se ha dei bordi in entrata, che inizialmente è falso. È quindi possibile scorrere tutti i bordi dell'elenco nel tempo O (n + m) contrassegnando tutti i nodi con i bordi in entrata. I nodi che non erano contrassegnati come aventi bordi in entrata sono quindi fonti. Questo processo richiede tempo O (m + n) e ha un sovraccarico tale che è probabilmente uno degli approcci più rapidi.

Spero che questo aiuti!

Answer 2

Una semplice ricerca di ampiezza o profondità dovrebbe soddisfare questo. Innanzitutto puoi mantenere un insieme di nodi che comprendono nodi sink che hai visto. In secondo luogo, puoi mantenere un set di nodi che hai scoperto usando BFS/DFS. Quindi il grafico verrà connesso se c'è un singolo componente connesso. Supponendo che si sta utilizzando un qualche tipo di rappresentazione di adiacenza lista di stile per il grafico, l'algoritmo sarebbe simile a questa:

create an empty queue 
create an empty set to store seen vertices 
create an empty set for sink nodes 

add source node to queue 

while queue is not empty 
    get next vertex from queue, add vertex to seen vertices 
    if num of adjacent nodes == 0 
     add sink nodes to sink node set 
    else 
     for each node in adjacent nodes 
     if node is not in seen vertices 
      add node to queue 

return size of sink nodes == 1 && size of seen vertices == total number in graph 

Questa sarà lineare nel numero di vertici e spigoli nel grafico.

Si noti che finché si conosce un vertice sorgente da cui partire, ciò assicurerà anche la proprietà di una singola origine: qualsiasi altro vertice che è un'origine non verrà rilevato da BFS/DFS, e quindi il la dimensione dei vertici visti non sarà il numero totale nel grafico.

Answer 3

Se il proprio algoritmo prende come input un DAG, che è collegato debolmente, si assuma che ci sia solo un nodo s il cui grado in-è zero e solo un nodo t il cui out-degree sia zero, mentre tutti gli altri nodi abbiano un positivo in-degree e out-degree, quindi s può raggiungere tutti gli altri nodi e tutti gli altri nodi possono raggiungere t. Per contraddizione, supponiamo che esista un nodo v che s non possa raggiungere. Poiché nessun nodo può raggiungere s, vale a dire che v non può raggiungere anche s. Come tale, v e s sono disconnessi, il che contraddice l'assunto. D'altra parte, se il DAG non è collegato debolmente, sicuramente non soddisfa i requisiti che desideri. In sintesi, è possibile prima calcolare il componente debolmente connesso del DAG semplicemente usando BFS/DFS, nel frattempo ricordando il numero di nodi il cui grado di in-degree o out è zero. La complessità di questo algoritmo è O (| E |).

Answer 4

Innanzitutto, eseguire un DFS sul grafico, partendo dal nodo di origine, che, come dici, è noto in anticipo. Se incontri un bordo posteriore [1], allora hai un ciclo e puoi uscire con un errore.Durante questa traversata puoi identificare se ci sono nodi, non raggiungibili dalla sorgente [2] e prendere l'azione appropriata.

Una volta determinato il grafico è un DAG, è possibile garantire che ogni nodo giace su un percorso dalla sorgente al lavandino da un altro DFS, partendo dalla fonte, come segue:

bool have_path(source, sink) { 
    if source == sink { 
     source.flag = true 
     return true 
    } 

    // traverse all successor nodes of `source` 
    for dst in succ(source) { 
     if not dst.flag and not have_path(dst, sink) 
      return false // exit as soon as we find a node with no path to `sink` 
    } 
    source.flag = true; 
    return true 
} 

L' la procedura have_path imposta un booleano flag in ciascun nodo, per il quale esiste un percorso da quel nodo al sink. Nello stesso tempo la procedura attraversa solo i nodi raggiungibili dalla sorgente e attraversa tutti i nodi raggiungibili dalla sorgente. Se la procedura restituisce true, allora tutti i nodi, raggiungibili dalla sorgente, giacciono su un percorso verso il sink. I nodi non raggiungibili erano già gestiti nella prima fase.

---

[1] un bordo, che collega un nodo con un numero maggiore DFS a un nodo con un numero DFS minore, che non è già completamente trasformato, cioè è ancora sul DFS impilare

[2 ] per esempio non avrebbero un numero DFS assegnato