2009-04-06 15 views
11

Ho un DAG che memorizza la relazione tra determinati oggetti nella mia applicazione. Quando questa struttura viene aggiornata aggiungendo un nuovo vertice al di sotto di uno esistente (ovvero, creando implicitamente un nuovo spigolo nel nuovo vertice) e poi (in un secondo momento) un nuovo vantaggio da lì ad altri vertici, voglio assicurarmi che il grafico rimane un DAG, i. e. che il mio codice non crea cicli.Come garantire che un DAG rimanga aciclico dopo l'inserimento di un nodo?

Devo aggiungere un cycle detection a ciascuna operazione di inserimento e collegamento, oppure ci sono delle regole che posso seguire al momento dell'inserimento che garantiranno che non sto producendo cicli?

Un approccio che posso pensare è archiviare lo topological level di ciascun nodo e consentire solo nuovi bordi che puntano a livelli superiori (più lontano dai nodi di origine). Tuttavia, sembra che questo mi priverà di molta della flessibilità che speravo di ottenere usando un DAG invece di un insieme di alberi ordinari.

risposta

6

È inoltre possibile memorizzare i collegamenti inversi e verificare che il nodo terminale del bordo aggiunto non compaia in nessuno dei nodi padre del nodo di origine. Questo sarebbe più veloce di un rilevamento a ciclo completo. Essenzialmente questo sarebbe un algoritmo di percorso più breve sui collegamenti inversi, che per un DAG dovrebbe essere un'operazione lineare.

come dice @Markus, però, se non si sta creando collegamenti sia a e dal il nuovo nodo di nodi esistenti, non dovrebbe essere in grado di creare un ciclo con l'introduzione di un nuovo nodo al grafico.

+0

Questa sembra l'opzione più pragmatica, ma dovrò verificare che cosa ciò accadrà alle mie esigenze di spazio e se sarà importante. –

+0

Dubito dell'efficienza di questo in casi generali (immagina un grafico a cinque livelli in cui la maggior parte dei nodi di ogni livello punta alla maggior parte dei nodi nel prossimo). L'idea del puntatore al contrario potrebbe funzionare in alcuni casi, ma l'ordinamento parziale dovrebbe essere molto più veloce in generale. – MarkusQ

+0

@MarkusQ - Ho capito che voleva evitare l'ordine parziale, se possibile. – tvanfosson

2

Ciò che si può fare è mantenere ordinati i nodi in un ordinamento topologico (cercare "ordinamento topologico"). Quando aggiungi un arco da un nodo di ordine inferiore a quello di ordine superiore, sai che nessun ciclo è stato creato. Nel caso opposto, è necessario aggiornare in modo incrementale l'ordinamento topologico e allo stesso tempo il rilevamento del ciclo di esecuzione.

+1

Se si ordina topologicamente il grafico e l'ordinamento funziona, significa che non c'è alcun ciclo, giusto? –

+0

Vero; se si mantiene l'ordine come un albero, si ottiene O (log N) complessità temporale per inserto di bordo. – jpalecek

4

Quando tale struttura viene aggiornato con l'aggiunta di un nuovo vertice e poi un nuovo bordo da lì per altri vertici

Se tutti i nuovi bordi sono dal il nuovo vertice non si potrà mai creare cicli.

Se si sta anche andando a essere l'aggiunta di bordi - il nuovo vertice da nodi più anziani, le opzioni dipendono dalla forma atteso del grafico. Si riducono a variazioni nell'ordinamento parziale, ma ci sono hack che offrono prestazioni migliori per alberi, foreste, maglie a diamante, ecc. Cosa sai della forma complessiva del grafico prevista?

+0

Grazie per avermelo segnalato, ho chiarito la mia domanda di conseguenza. Per quanto riguarda la forma, non lo so ancora. Gran parte della forma dipenderà da come le persone useranno l'applicazione. Mi aspetto modelli, ma non posso ancora dire quali saranno. –

+0

Al momento sto esaminando l'ordinamento parziale, ma non riesco a capire come mi aiuti. Certo, c'è un ordine nel mio grafico, e posso ordinarlo, ma come vanno i cicli di prevenzione? È questa la stessa strada della classificazione topologica che antti.huima suggerisce? –

+0

Inoltre, per quanto riguarda la forma che mi aspetto, è probabilmente sicuro dire che saranno alberi, ma condividono molti rami (stavo cercando di capire come mantenere sincronizzati più alberi quando mi è venuta l'idea di usare un singolo DAG invece) –

3

In this article, esiste un algoritmo online per il mantenimento dell'ordine topologico (pagina 4).

Problemi correlati