¿Cuál es la ventaja de ser capaz de asignar las dependencias de un sistema como un DAG (gráfico acíclico dirigido)?

Question

Si tuviera que organizar una colección de objetos dependencias en un DAG, en qué situaciones que ser más deseable que otra estructura de datos tales como el TDC (diagrama de decisión binario)?

Answer 1

El DAG tiene un par de propiedades que son ideales para el análisis de dependencias.

En primer lugar, se puede identificar fácilmente los componentes de nivel básico '' de su sistema. Esos son los nodos de la DAG sin bordes de entrar en ellos. Conocer las capas relativas de su sistema significa que se conoce el impacto de refactorizaciones. (Todo abajo de la cadena.)

En segundo lugar, si se puede producir un DAG que saber que el sistema no tiene interdependencias extraños. Ciclos en el grafo de dependencias significaría que tiene dos componentes que dependen el uno del otro - una receta para los insectos extraños y errores de generación. En Microsoft hemos utilizado una herramienta llamada asmmeta para evitar este problema.

Answer 2

No soy muy conocedor de diagramas de decisión binarios, pero parece wikipedia estado que se dirigen fundamentalmente, acíclico, gráficos. Yo sé un poco acerca de los DAG. Si puede representar a su problema como un DAG puede asegurarse de que usted no tiene ningún ciclos (como Chris Smith mencionó anteriormente).

Otro atributo de un árbol de decisión binaria que puede (o no) ser relevante aquí es que son binarios. Sin embargo, no estoy seguro de cómo le gustaría modelar el problema a un diagrama de decisión binaria. Parece que BDDs tienen cero, uno o dos opciones en cada nodo. Estoy teniendo un tiempo difícil ver cómo iba a asignar a este dependencias. dependencias de mapeo en un gráfico hacen mucho más sentido para mí.

Principalmente, creo que sólo depende de lo que los algoritmos que desea ejecutar en su representación. Si no está seguro que tiene un DAG, puede ejecutar un ciclo detección algoritmo para decirle si es o no. Si usted quiere encontrar caminos más cortos, puede ejecutar Dijkstra en él. Creo que esto realmente depende de lo que quiere hacer, y sé lo que puede hacer con un gráfico en general, que involucran principalmente a demostrar que es un DAG. Una vez que tenga un DAG, la mayoría de las cosas que me gustaría establecer han sido establecidas. Eso es sólo mí, sin embargo.

-Brian J. Stinar -