Cómo convertir el gráfico acíclico dirigido (DAG) en árbol

Question

He estado buscando ejemplos de C # para transformar un DAG en un árbol.

¿Alguien tiene ejemplos o indicadores en la dirección correcta?

Actualización de la aclaración

Tengo un gráfico que contiene una lista de módulos que mi aplicación debe cargar. Cada módulo tiene una lista de módulos de los que depende. Por ejemplo, aquí están mis módulos, A, B C, D y E

• A no tiene dependencias
• B depende de A, C y E
• C depende de A
• D depende de A
• E depende de C y A

Quiero resolver dependencias y generar un árbol que se vea así ...

--A

- + - B

----- + - C

--------- + - D

- + - E

Ordenamiento topológico

Gracias por la información, si realizo una clasificación topológica e invierto el resultado, tendré el siguiente orden

• A
• B
• C
• D
• E

Quiero mantener la estructura jerárquica para que mis módulos se carguen en el contexto correcto, por ejemplo ... el módulo E debe estar en el mismo contenedor que B

Gracias

Rohan

Answer 1

Hay una respuesta teórica en el gráfico y la respuesta del programador a esto. Supongo que puede manejar la parte de los programadores usted mismo. Para la respuesta teórica del gráfico:

• Un DAG es un conjunto de módulos donde nunca sucede que A necesita B, y al mismo tiempo, B (o uno de los módulos B necesita) necesita A, en módulos-habla: no dependencia circular. He visto que suceden dependencias circulares (busque ejemplos en los foros de Gentoo), así que ni siquiera puede estar 100% seguro de tener un DAG, pero supongamos que sí. 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 suceder en un DAG.
• Además, un árbol tiene exactamente un nodo raíz, pero un DAG puede tener múltiples 'raíz'. nodos (es decir, módulos de los que nada depende). Por ejemplo, un programa como el 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 " root " nodo, mientras que las bibliotecas, etc., dependen de ellos. (I.E. tanto Konqueror como Kmail dependen de Qtlib, pero nada depende de Konqueror, y nada depende de Kmail)

La respuesta teórica de Graph a su pregunta, como otros lo señalaron, es que un DAG no se puede convertir en un árbol, mientras que cada árbol es un DAG.

Sin embargo, (los programadores de alto nivel responden) si desea el árbol para las representaciones gráficas, solo le interesan las dependencias de un módulo específico, no lo que depende de ese módulo. Déjame dar 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 de arte ASCII, por la sencilla razón de que no se puede convertir en un árbol. Sin embargo, si desea mostrar de qué depende A, puede mostrar esto:

A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F

Como puede ver, obtiene entradas dobles en su árbol, en este caso, "solo". D pero si haces un " expandir todo " en el árbol Gentoo, te garantizo que tu árbol tendrá al menos 1000 veces la cantidad de nodos que hay 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 tienes un " gran " o " complejo " árbol, podría ser mejor expandir el árbol dinámicamente, no de antemano, de lo contrario, podría tener un proceso muy intensivo de memoria.

La desventaja del árbol de arriba es que si hace clic en abrir B, entonces D, verá que A y B dependen de D, pero no que C también dependa de D. Sin embargo, dependiendo de su situación, esto podría no serlo. importante en todo - si mantiene una lista de módulos cargados, al cargar C verá que ya ha cargado D, y no importa que no se haya cargado para C, sino para B. Está cargado, eso es todo. 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 puedes hacer con un árbol es lo que está en tu oración final: preservar el orden topológico, es decir, si B se carga en el mismo contenedor que C, nunca podrás cargar C en el mismo contenedor que bien. O puede que tengas que aguantarte poniendo todo en un contenedor (no es que entiendo perfectamente a qué te refieres con " cargar en el mismo contenedor ")

¡Buena suerte!

Answer 2

Un DAG y un árbol no son lo mismo matemáticamente. Por lo tanto, cualquier conversión introduce ambigüedad. Un árbol por definición no tiene ciclos, punto.

Answer 3

Lo que está buscando, para encontrar el orden para cargar sus módulos, es Tipo topológico de su DAG. Si los bordes van de un módulo a los módulos de los que depende (lo cual creo que es más probable), tendrá que cargar los módulos en el orden inverso del orden topológico porque aparecerá un módulo antes de todos los módulos. de lo que depende.

Si representa el DAG de tal manera que los bordes van desde los módulos dependientes a los módulos que dependen de ellos (puede obtener esto invirtiendo todos los bordes en el gráfico anterior), simplemente puede cargar los módulos en el orden del tipo topológico.

Answer 4

Depende mucho de cómo represente a su DAG. Por ejemplo, podría ser una matriz de adyacencia (A [i, j] = 1 si hay un borde desde el nodo i al nodo j, de lo contrario 0), o como un sistema de punteros, o como una matriz de nodos y una matriz de bordes ....

Además, no está claro qué transformación estás tratando de aplicar. Un DAG conectado es un árbol, así que me temo que necesita aclarar un poco su pregunta.

Answer 5

Solo puede hacerlo si todos los subárboles tienen un solo nodo raíz.