c# - grafico - grafo

Cómo convertir un gráfico acíclico dirigido(DAG) a un á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 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, BC, 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í ...

--UN

- + - B

----- + - C

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

- + - E

Clasificación topológica

Gracias por la información, si realizo un tipo Topológico e invierto la salida tendré el siguiente orden

• UN
• segundo
• do
• re
• mi

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

Depende mucho de cómo representas tu DAG. Por ejemplo, podría ser una matriz de adyacencia (A [i, j] = 1 si hay un borde del nodo i al nodo j, más 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 2

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

Si representa el DAG de 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), puede simplemente cargar los módulos en el orden de los topológicos ordenar.

Answer 3

Solo puede hacer eso si todos los subárboles tienen un único nodo raíz.

Answer 4

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 5

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 el gráfico, respuesta teórica:

• Un DAG es un conjunto de módulos en el que nunca sucede que A necesita B, y al mismo tiempo, B (o uno de los módulos B necesita) necesita A, en módulos: 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 suceder 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. (IE 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 señalaron otros, 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 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 simple razón de que esto no se puede convertir en un árbol. Sin embargo, si quiere mostrar de qué depende A, puede mostrar esto:

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

Como ve, obtiene entradas dobles en su árbol, en este caso "solo" D, pero si hace un "expandir todo" en el árbol de Gentoo, le garantizo que su árbol tendrá al menos 1000 veces la cantidad de nodos como 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 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 que también C depende de D. Sin embargo, dependiendo de su situación, esto podría no ser importante en absoluto - si mantiene una lista de módulos cargados, al cargar C ve que ya ha cargado D, y no importa que no se haya cargado para C, sino para B. Se carga, eso es todo lo que 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 frase final: preservar el orden topológico, es decir, si B se carga en el mismo contenedor que C, nunca podrá cargar C en el mismo contenedor. O puede que tenga que poner todo en un contenedor (no es que entienda completamente lo que quiere decir con "cargar en el mismo contenedor")

¡Buena suerte!