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.
Questa sembra l'opzione più pragmatica, ma dovrò verificare che cosa ciò accadrà alle mie esigenze di spazio e se sarà importante. –
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
@MarkusQ - Ho capito che voleva evitare l'ordine parziale, se possibile. – tvanfosson