Ahí está la respuesta teórica del gráfico y la respuesta del programador a esto. Supongo que puede manejar la parte de los programadores usted mismo. Para la gráfica respuesta theorethical:
- Un DAG es un conjunto de módulos donde nunca ocurre que A necesita B, y al mismo tiempo, B (o una de las necesidades módulos B) necesita A, en Modules- hablar: no hay dependencia circular. He visto que ocurren dependencias circulares (busque en los foros de Gentoo ejemplos), por lo que ni siquiera puede estar 100% seguro de que tiene un DAG, pero supongamos que tiene. No es muy difícil verificar las dependencias circulares, por lo que te recomiendo que lo hagas en algún lugar de tu cargador de módulos.
- En un árbol, algo que nunca puede suceder es que A depende de B y C y que tanto B como C dependen de D (un diamante), pero esto puede ocurrir en un DAG.
- Además, un árbol tiene exactamente un nodo raíz, pero un DAG puede tener múltiples nodos "raíz" (es decir, módulos de los que nada depende). Por ejemplo, un programa como GIMP, el programa GIMP será el nodo raíz del conjunto de módulos, pero para GENTOO, casi cualquier programa con una GUI es un nodo "raíz", mientras que las bibliotecas, etc., son dependencias de ellos. (Es decir, tanto Konqueror y Kmail dependen de Qtlib, pero nada depende de Konqueror, y nada depende de Kmail)
El Gráfico theorethical respuesta a su pregunta, como otros señalaron, es que un DAG no se puede convertir a un árbol, mientras que cada árbol es un DAG.
Sin embargo, (los programadores de alto nivel responden) si quiere el árbol para las representaciones gráficas, solo está interesado en las dependencias de un módulo específico, no lo que depende de ese módulo. Déjenme darles un ejemplo:
A depends on B and C
B depends on D and E
C depends on D and F
no puedo mostrar esto como un árbol ASCII-art, por la sencilla razón de que esto no se puede convertir en un árbol. Sin embargo, si desea mostrar lo que A depende, puede mostrar esto:
A
+--B
| +--D
| +--E
+--C
+--D
+--F
Como se puede ver, se obtiene entradas dobles en su árbol - en este caso "sólo" D pero si lo hace un " expande todo "en el árbol de Gentoo, te garantizo que tu árbol tendrá al menos 1000 veces más nodos que módulos. (hay al menos 100 paquetes que dependen de Qt, por lo que todo lo que Qt depende estará presente al menos 100 veces en el árbol).
Si tiene un árbol "grande" o "complejo", podría ser mejor expandir el árbol dinámicamente, no de antemano, de lo contrario podría tener un proceso que requiera mucha memoria.
La desventaja del árbol de arriba es que si hace clic en abrir B, entonces D, ve que A y B dependen de D, pero no que también C depende de D. Sin embargo, dependiendo de su situación, esto podría no Sea importante en absoluto: si mantiene una lista de módulos cargados, al cargar C, verá que ya ha cargado D, y no importa que no haya sido cargado para C, sino para B. Está cargado, eso es todo Eso importa. Si mantiene dinámicamente lo que depende directamente de un determinado módulo, también puede manejar el problema opuesto (descarga).
Sin embargo, lo que no puede hacer con un árbol es lo que está en su última frase: conservar el orden topológico, es decir, si B se carga en el mismo contenedor que C, nunca cargará C en el mismo contenedor también. O puede que tenga que soportar poner todo en un contenedor (no es que entienda completamente lo que quiere decir con "cargar en el mismo contenedor")
¡Buena suerte!
cómo desea tratar con diamantes ... A -> B, A -> C, B & C -> D – ShuggyCoUk
Esa es una buena pregunta, veo un problema pero no sé cómo resolverlo, ¿qué haría? ¿tú lo haces? Mi experiencia con la teoría de grafos es muy limitada. –
O bien 1) elige el primero, 2) eliges los últimos 3) duplicas el nodo. lo que sea mejor depende por completo de la aplicación, 3 es el más fácil seguido de 1 seguido de 2 ... es difícil decir lo que quiere el árbol en función de la pregunta. las dependencias de diamante son una perra en general – ShuggyCoUk