Qual è il vantaggio di essere in grado di mappare le dipendenze di un sistema come un DAG (grafo aciclico diretto)?

Question

Se dovessi organizzare una raccolta delle dipendenze degli oggetti in un DAG, in quali situazioni sarebbe che essere più desiderabile di un altro struttura di dati come ad esempio un BDD (diagramma di decisione binario)?

Answer 1

Il DAG ha un paio di caratteristiche che sono l'ideale per le dipendenze analizzare.

In primo luogo, si può facilmente identificare i componenti 'livello base' del sistema. Quelli sono i nodi del DAG senza bordi di andare in loro. Conoscere i livelli relativi di sistema significa che si conosce l'impatto di refactoring. (Tutto valle della catena.)

In secondo luogo, se si può produrre un DAG si sa che il sistema non ha strani interdipendenze. Cicli nel grafo delle dipendenze significherebbe che si dispone di due componenti che si basano su l'un l'altro - una ricetta per strani bug ed errori di compilazione. In Microsoft abbiamo utilizzato uno strumento chiamato asmmeta per risolvere questo problema.

Answer 2

io non sono molto ben informato diagrammi di decisione binaria, ma wikipedia sembra affermare che essi sono fondamentalmente dirette, aciclico, grafici. Conosco un po 'di DAG. Se si riesce a rappresentare il problema come un DAG è possibile garantire non avete nessun cicli (come Chris Smith accennato in precedenza).

Un altro attributo di un albero di decisione binario che possono (o non possono) essere rilevante qui è che sono binari. Tuttavia, non sono sicuro di come si vorrebbe modellare il vostro problema a un diagramma decisione binario. Sembra che BDDS avere zero, uno o due scelte a ogni nodo. Sto avendo un momento difficile vedere come avrei mappare le dipendenze di questo. dipendenze di mappatura in un grafico che rendono molto più senso per me.

Soprattutto, penso che dipende solo da quello algoritmi che si desidera eseguire sul vostro rappresentazione. Se non siete sicuri di avere un DAG, è possibile eseguire un ciclo di rilevamento algoritmo di dirvi se si è o non. Se si vuole trovare percorsi più brevi, è possibile eseguire di Dijkstra su di esso. Penso che questo in realtà dipende da cosa si vuole fare, e so che le cose si possono fare con un grafico generale, che coinvolgono soprattutto dimostrando che è un DAG. Una volta che hai un DAG, la maggior parte delle cose che vorrei stabilire sono state stabilite. Questo è solo me però.

-Brian J. Stinar -