Comment convertir un graphe acyclique dirigé (DAG) en arbre

Question

Je recherchais des exemples en C # pour transformer un DAG en un arbre.

Quelqu'un at-il des exemples ou des indications dans la bonne direction?

Mise à jour de la clarification

J'ai un graphique contenant une liste de modules que mon application doit charger. Chaque module a une liste de modules dont il dépend. Par exemple voici mes modules, A, B C, D et E

• A n'a pas de dépendances
• B dépend de A, C et E
• C dépend de 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

Tri topologique

Merci pour l’information, si j’effectue un tri topologique et que j’inverse la sortie, j’aurai l’ordre suivant

• A
• B
• C
• D
• E

Je souhaite conserver la structure hiérarchique de sorte que mes modules soient chargés dans le contexte approprié, par exemple ... le module E doit se trouver dans le même conteneur que B

Merci

Rohan

Answer 1

Il y a la réponse théorique du graphe et celle du programmeur. Je suppose que vous pouvez gérer vous-même les programmeurs. Pour la réponse théorique du graphique:

• Un groupe de disponibilité de base de données est un ensemble de modules dans lequel il n'est jamais nécessaire que A ait besoin de B, et en même temps, B (ou l'un des modules dont B a besoin) a besoin de A, en termes de modules: pas de dépendance circulaire. J'ai vu des dépendances circulaires se produire (recherchez des exemples dans les forums Gentoo), de sorte que vous ne pouvez même pas être sûr à 100% que vous avez un DAG, mais supposons que vous en avez un. Il n’est pas très difficile de vérifier les dépendances circulaires, je vous recommande donc de le faire quelque part dans votre chargeur de modules.
• Dans un arbre, ce qui ne peut jamais arriver est que A dépend de B et C et que B et C dépendent tous deux de D (un diamant), mais cela peut arriver dans un DAG.
• De plus, un arbre a exactement un nœud racine, mais un DAG peut avoir plusieurs "racine". nœuds (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 de modules, mais pour GENTOO, presque tous les programmes dotés d'une interface graphique sont des "racines". noeud, alors que les bibliothèques, etc. en dépendent. (I.E. Konqueror et Kmail dépendent tous deux de Qtlib, mais rien ne dépend de Konqueror et rien ne dépend de Kmail)

La réponse théorique de Graph à votre question, comme d'autres l'ont souligné, est qu'un DAG ne peut pas être converti en un arbre, alors que chaque arbre est un DAG.

Cependant, (les programmeurs de haut niveau répondent) si vous voulez l’arborescence pour les représentations graphiques, vous ne vous intéressez qu'aux dépendances d’un module spécifique, et non à ce qui dépend de ce module. Laissez-moi vous 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 montrer cela sous forme d'arborescence ASCII, pour la simple raison que cela ne peut pas être converti en arborescence. Cependant, si vous voulez montrer de quoi dépend A, vous pouvez montrer ceci:

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

Comme vous le voyez, vous obtenez des entrées en double dans votre arborescence. Dans ce cas, "uniquement". D mais si vous faites un "Développer tout" sur l’arbre Gentoo, je vous garantis que votre arbre aura au moins 1000 fois plus de nœuds qu’il ya 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 "gros" " ou "complexe" Il est peut-être préférable d’élargir l’arborescence de manière dynamique, pas à l’avance, sinon vous pourriez avoir un processus gourmand en mémoire.

L’inconvénient de l’arborescence ci-dessus est que si vous cliquez sur Ouvrir B, puis D, vous voyez que A et B dépendent de D, mais pas que C dépend également de D. Toutefois, selon votre situation, il se peut que cela ne soit pas le cas. important du tout - si vous maintenez une liste de modules chargés, lors du chargement de C, vous voyez que vous avez déjà chargé D, et peu importe qu'il n'ait pas été chargé pour C, mais pour B. Il est chargé, c'est tout. questions. Si vous gérez de manière dynamique 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, c’est ce qui se trouve dans votre dernière phrase: conservez l’ordre topologique, c’est-à-dire que si B est chargé dans le même conteneur que C, vous ne pourrez jamais charger C dans le même conteneur. bien. Ou alors vous devrez peut-être tout mettre dans un conteneur (ce n'est pas que je comprenne parfaitement ce que vous entendez par "chargement dans le même conteneur").

Bonne chance!

Answer 2

Un DAG et un arbre ne sont pas mathématiquement identiques. Ainsi, toute conversion introduit une ambiguïté. Un arbre, par définition, n’a pas de cycle, point.

Answer 3

Vous recherchez le afin de connaître l'ordre dans lequel vous souhaitez charger vos modules. Tri topologique de votre DAG. Si les arêtes vont d'un module aux modules dont elle dépend (ce qui, à mon avis, est le plus probable), vous devrez charger les modules dans l'ordre inverse du tri topologique, car un module apparaîtra avant tous les modules. cela dépend.

Si vous représentez le DAG de telle sorte que les arêtes passent des modules dépendants aux modules qui en dépendent (vous pouvez obtenir cela en inversant toutes les arêtes du graphique ci-dessus), vous pouvez simplement charger les modules dans l'ordre. du type topologique.

Answer 4

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 existe une arête du noeud i au noeud j, sinon 0), ou d’un système de pointeurs, ou d’un tableau de noeuds et bords ....

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

Answer 5

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