Comment convertir le graphique acyclique dirigé (DAG) en arbre

Question

J'ai cherché des exemples C# pour transformer un DAG en arbre.

Est-ce que quelqu'un a des exemples ou des pointeurs dans la bonne direction?

Précision de mise à jour

J'ai un graphique qui contient une liste de modules que ma demande est nécessaire de charger. Chaque module a une liste de modules dont il dépend. Par exemple ici sont mes modules, A, BC, D et E

• A n'a pas de dépendances
• B dépend de A, C et E
• C dépend A
• D dépend de A
• E dépend de C et a

Je veux résoudre les dépendances et générer un arbre qui ressemble à ceci ...

-A

- + - B

----- + - C

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

- + - E

Trier topologiques

Merci pour l'information, si je joue une sorte topologiques et inverser la sortie i auront l'ordre suivant

• A
• B
• C
• D
• E

Je veux maintenir la structure hiérarchique pour que mes modules soient chargés dans le bon contexte, par exemple ... le module E devrait être dans le même conteneur que B

Merci

Rohan

Answer 1

Voici la réponse théorique du graphique et la réponse du programmeur. Je suppose que vous pouvez gérer la partie programmeurs vous-même. Pour le graphique theorethical réponse:

• Un DAG est un ensemble de modules où il ne se produit jamais que A besoin B, et en même temps, B (ou l'un des modules besoins B) a besoin A, Modules- speak: pas de dépendance circulaire. J'ai vu des dépendances circulaires (recherchez des exemples sur les forums Gentoo), donc vous ne pouvez même pas être sûr à 100% que vous avez un DAG, mais supposons que vous l'ayez fait. Il n'est pas très difficile de vérifier les dépendances circulaires, donc je vous recommande de le faire quelque part dans votre chargeur de module.
• Dans un arbre, quelque chose qui ne peut jamais arriver est que A dépend de B et C et que B et C dépendent de D (un diamant), mais cela peut arriver dans un DAG.
• En outre, un arbre a exactement un nœud racine, mais un DAG peut avoir plusieurs nœuds "racine" (c'est-à-dire des modules dont rien ne dépend). Par exemple un programme comme GIMP, le programme GIMP sera le nœud racine de l'ensemble des modules, mais pour GENTOO, presque n'importe quel programme avec une GUI est un nœud "racine", alors que les bibliothèques etc. en dépendent. (IE et Konqueror à la fois Kmail dépendent Qtlib, mais rien ne dépend de Konqueror, et rien ne dépend de Kmail)

Le graphique theorethical répondre à votre question, comme d'autres l'ont souligné, est qu'un DAG ne peut pas être converti à un arbre, alors que chaque arbre est un DAG.

Cependant, (les programmeurs de haut niveau répondent) si vous voulez l'arbre pour les représentations graphiques, vous êtes seulement intéressé par les dépendances d'un module spécifique, pas ce qui dépend de ce module. Permettez-moi de donner un exemple:

A depends on B and C 
B depends on D and E 
C depends on D and F 

Je ne peux pas le montrer comme un arbre art ASCII, pour la simple raison que cela ne peut être converti en un arbre. Cependant, si vous voulez montrer ce que A dépend, vous pouvez afficher ceci:

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

Comme vous le voyez, vous obtenez des entrées doubles dans votre arbre - dans ce cas, « seulement » D mais si vous faites un " expand tout "sur l'arbre Gentoo, je vous garantis que votre arbre aura au moins 1000 fois plus de nœuds que de modules. (il y a au moins 100 paquets qui dépendent de Qt, donc tout dépend de Qt sera présent au moins 100 fois dans l'arbre).

Si vous avez un arbre "grand" ou "complexe", il est préférable de développer l'arborescence de manière dynamique, pas à l'avance, sinon vous risquez d'avoir un processus très gourmand en mémoire.L'inconvénient de l'arbre ci-dessus est que si vous cliquez sur ouvrir B, alors D, vous voyez que A et B dépendent de D, mais pas que C dépend aussi de D. Cependant, selon votre situation, cela peut ne pas être important du tout - si vous maintenez une liste de modules chargés, en chargeant C vous voyez que vous avez déjà chargé D, et ce n'est pas grave ce n'était pas chargé pour C, mais pour B. Il est chargé, c'est tout c'est important. Si vous gérez dynamiquement ce qui dépend directement d'un certain module, vous pouvez également gérer le problème inverse (déchargement). Cependant, ce que vous ne pouvez pas faire avec un arbre est ce qui est dans votre dernière phrase: préserver l'ordre topologique, c'est-à-dire si B est chargé dans le même conteneur que C, vous ne pourrez jamais charger C dans le même conteneur ainsi que. Ou vous pourriez être mis en place avec tout mettre dans un conteneur (pas que je comprends parfaitement ce que vous entendez par "chargement dans le même conteneur")

Bonne chance!

Answer 2

Vous ne pouvez le faire que si tous les sous-arbres ont un seul nœud racine.

Answer 3

Cela dépend beaucoup de la façon dont vous représentez votre DAG. Par exemple, il pourrait s'agir d'une matrice d'adjacence (A [i, j] = 1 s'il y a un bord du nœud i au nœud j, sinon 0), ou comme un système de pointeurs, ou comme un tableau de nœuds et un tableau de bords ....

En outre, la transformation que vous essayez d'appliquer n'est pas claire.Un DAG connecté est un arbre, donc je crains que vous ayez besoin de clarifier votre question un peu.

Answer 4

Un DAG et un arbre ne sont pas mathématiquement la même chose. Ainsi, toute conversion introduit une ambiguïté. Un arbre par définition n'a pas de cycles, période.

Answer 5

Ce que vous cherchez, afin de trouver la commande pour charger vos modules, est le Topological sort de votre DAG. Si les bords vont d'un module aux modules dont il dépend (ce qui me semble le plus probable), vous devrez charger les modules dans l'ordre inverse du tri topologique car un module apparaîtra -avant-tous les modules dont cela dépend. Si vous représentez le DAG de sorte que les bords passent des modules dépendants aux modules qui en dépendent (vous pouvez obtenir ceci en inversant tous les bords dans le graphique ci-dessus), vous pouvez simplement charger les modules dans le ordre du tri topologique.