Come posso trovare tutti i percorsi attraverso un set di nodi dati in un DAG?

Question

Ho un elenco di elementi (nodi blu di seguito) che sono classificati dagli utenti della mia applicazione. Le categorie stesse possono essere raggruppate e categorizzate da sole.

La struttura risultante può essere rappresentata come Directed Acyclic Graph (DAG) dove gli elementi sono lavandini nella parte inferiore della topologia del grafico e le categorie principali sono fonti. Nota che mentre alcune categorie potrebbero essere ben definite, molte saranno definite dall'utente e potrebbero essere molto disordinate.

Esempio:

_{(fonte: theuprightape.net )}

Su quella struttura, voglio eseguire le seguenti operazioni:

• trova tutti gli elementi (sink) sotto un nodo particolare (tutti gli elementi in Europa)
• trova tutti i percorsi (se presenti) che attraversano tutta una serie di n nodi (tutti gli elementi inviati tramite SMTP da example.com)
• trova tutti i nodi che si trovano al di sotto di tutti i nodi (intersezione: cibi marroni goyish)

Il primo sembra abbastanza semplice: inizia dal nodo, segui tutti i possibili percorsi verso il basso e raccogli gli oggetti lì. Tuttavia, esiste un approccio più rapido? Ricordare i nodi che ho già attraversato probabilmente aiuta a evitare inutili ripetizioni, ma ci sono più ottimizzazioni?

Come posso procedere con il secondo? Sembra che il primo passo sarebbe quello di determinare l'altezza di ciascun nodo nell'insieme, in modo da determinare da quale uno (i) iniziare e quindi trovare tutti i percorsi al di sotto di quello che include il resto dell'insieme. Ma è questo l'approccio migliore (o anche un buon)?

Gli algoritmi di attraversamento grafico elencati su Wikipedia sembrano tutti preoccuparsi di trovare un particolare nodo o il percorso più breve o comunque più efficace tra due nodi. Penso che entrambi non sia quello che voglio o non sono riuscito a vedere come questo si applica al mio problema? Dove altro dovrei leggere?

Answer 1

Mi sembra che sia essenzialmente la stessa operazione per tutte e 3 le domande. Stai sempre chiedendo "Trova tutti i X sotto i nodi Y, dove X è di tipo Z". Tutto ciò che serve è un meccanismo generico per "individuare tutti i nodi sotto il nodo", (risolve Q3) e quindi è possibile filtrare i risultati per "nodetype = sink" (risolve Q1). Per Q2, hai il punto iniziale (il tuo set di nodi) e il tuo punto finale (qualsiasi sink sotto il punto iniziale), quindi il tuo set di soluzioni è costituito da tutti i percorsi dal nodo iniziale specificato al sink. Quindi suggerirei che quello che fondamentalmente hai a è un albero e che gli algoritmi di base per attraversare gli alberi sarebbero la strada da percorrere.

Answer 2

Nonostante il fatto che il tuo grafico sia aciclico, le operazioni che citi mi ricordano aspetti simili dell'analisi del diagramma di flusso di controllo. Esiste un ricco set di algoritmi basati su dominance che potrebbero essere applicabili. Ad esempio, la tua terza operazione mi ricorda le frontiere del dominio del calcolo; Credo che l'algoritmo funzionerebbe direttamente se introduci temporaneamente " voce " e "esci" i nodi. Il nodo di entrata collega l'insieme di nodi "quotato" e i nodi di uscita collegano i lavandini.

Vedi anche gli algoritmi di base di Robert Tarjan

.