Comment convertir le Graphe Dirigé Acyclique (DAG) de l'Arbre

J'ai été à la recherche pour le C# exemples de transformer un DAG dans un Arbre.

Quelqu'un aurait-il un des exemples ou des pointeurs dans la bonne direction?

Clarification de mise à Jour

J'ai un graphique qui contient la liste des modules que ma demande est nécessaire pour charger. Chaque module dispose d'une liste de modules dont il dépend. Pour exemple voici mes modules, A, B, C, D et E

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

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

--Un

--+--B

-----+--C

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

--+--E

Tri Topologique

Merci pour l'information, si j'effectue un tri Topologique et d'inverser la sortie, j'aurai l'ordre suivant

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

Grâce

Rohan

comment voulez-vous traiter avec des diamants...- > B -> C, B & C -> D
C'est une bonne question, je vois un problème, mais ne sais pas comment le résoudre, que feriez-vous? Mon experiance avec la théorie des graphes est très limitée.
Vous avez le choix entre 1) sélectionnez le premier, 2) choisir les 3 derniers) dupliquer le nœud. selon ce qui est le meilleur est entièrement fonction de l'application, 3, le plus facile est suivi par 1 suivi de 2... il est difficile de dire ce que vous voulez l'arbre sur la base de la question. diamant dépendances sont une chienne en général
ShuggyCoUk, avez-vous un exemple de code ou connaissez des semblables? Je pense que mon graphe a un diamant de dépendance...- > B -> F, B -> E, B -> C, E -> D, C -> D
Les deux BFS et DFS générer un arbre à partir d'un DAG. Ils vous permettent de repérer les diamants (ils doivent le faire pour éviter la traversée des nœuds plus d'une fois), de la naïve utilisation de l'un et l'autre simplement seulement inclure un nœud lorsqu'il est vu pour la première fois.

OriginalL'auteur Rohan West | 2009-03-09

c#data-structures directed-acyclic-graphs tree

20

Il y a le graphique de réponse théorique et le programmeur de la réponse à cette question. Je suppose que vous pouvez gérer les programmeurs partie de vous-même. Pour le graphique theorethical réponse:
- Un groupe est un ensemble de modules où il n'arrive jamais que les besoins B, et dans le même temps, B (ou l'un des modules B besoins) besoins, dans des modules-parler: pas de dépendance circulaire. J'ai vu des dépendances circulaires arriver (chercher sur les forums Gentoo par exemple), de sorte que vous ne pouvez même pas être sûr à 100% que vous avez un DAG, mais supposons que vous avez. Il n'est pas très difficile de faire une vérification sur les dépendances circulaires, donc je vous recommande de le faire donc quelque part dans votre chargeur de module.
- Dans un arbre, quelque chose qui ne peut arriver, c'est que A dépend de B et de C, et que B et C dépendent de D (un diamant), mais cela peut arriver dans un DAG.
- Aussi, un arbre a exactement un nœud racine, mais un DAG peut avoir plusieurs "racine" nœuds (c'est à dire les modules que rien ne dépend). Par exemple, un programme comme le GIMP, the GIMP programme sera le nœud racine de l'ensemble de modules, mais pour GENTOO, presque n'importe quel programme avec une interface graphique utilisateur est "root" nœud, tandis que les bibliothèques etc sont des dépendances. (I. E. les deux Konqueror et Kmail dépendent Qtlib, mais rien ne dépend de Konqueror, et rien ne dépend de Kmail)
Le Graphique theorethical réponse à votre question, comme d'autres l'ont souligné, c'est qu'un DAG peut pas être converti à un arbre, tandis que chaque arbre est un DAG.

Cependant, (de haut niveau programmeurs réponse) si vous voulez l'arbre de représentations graphiques, vous êtes seulement intéressés dans les dépendances d'un module spécifique, non pas ce qui est en fonction 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 montrer ce que l'ASCII-art de l'arbre, pour la simple raison que cela ne peut pas être converti dans un arbre.
Toutefois, si vous voulez montrer ce que l'Un dépend, vous pouvez afficher cette:
```
A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F
```
Comme vous le voyez, vous obtenez des entrées en double dans votre arbre, dans ce cas "seulement" D, mais si vous faites une "afficher tout" sur l'arbre Gentoo, je vous garantie que votre arbre aura au moins 1000 fois le montant de nœuds qu'il existe des modules. (il y a au moins 100 paquets qui dépendent de l'intervalle Qt, donc tout Qt dépend de la volonté d'être présent au moins 100 fois dans l'arbre).

Si vous avez un "grand" ou "complexe" de l'arbre, Il pourrait être préférable de développer l'arborescence de façon dynamique, et non à l'avance, sinon vous risquez d'avoir un très gourmandes en mémoire du processus.

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 aussi C dépend de D. Toutefois, selon votre situation, cela peut ne pas être important à tous si vous conservez une liste des modules chargés, sur le chargement de C, vous voyez que vous avez chargé D déjà, et il n'a pas d'importance, il n'était pas chargé pour le C, mais pour B. Il est chargé, que tout ce qui compte. Si vous dynamiquement maintenir ce qui dépend directement d'un certain module, vous pouvez 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 n'aurez jamais à charger C dans le même conteneur. Ou vous pourriez avoir à se mettre en place avec le fait de tout mettre dans un récipient (non pas que je comprends tout à fait ce que tu veux dire avec "chargement dans le même conteneur")

Bonne chance!

Cette réponse m'a aidé à réfléchir à un tout autre problème, je travaille sur 😉
Un DAG avec un seul root peut être convertibles à un arbre si les nœuds ont un contenu, mais pas d'identité (si plusieurs nœuds partagent un nœud enfant, les références à ce nœud seraient remplacées par des références à des copies distinctes de celle-ci).

OriginalL'auteur
4

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

Ni un DAG (d'où le Acyclique une partie du nom). Disponibilité de base de données permet de diamants et de même topologies où deux directions divergentes re-convergent. (Mais en aucun cas, pouvez-vous revenir à un parent). Un arbre n'a pas de nœuds avec plus d'un parent.
Exactement: UN DAG n'a pas de dirigée cycles. Un arbre n'a pas de cycles.

OriginalL'auteur dsimcha
2

Ce que vous cherchez, afin de trouver l'ordre de chargement des modules, est la Tri topologique de votre GROUPE. Si les bords de passer d'un module pour les modules dont il dépend (qui je pense est le plus probable), vous devrez charger les modules dans l'ordre inverse du tri topologique, car un module s'affiche avant tous les modules dont il dépend.

Si vous représentez le groupe tels que les bords aller de l'dépendait des modules les modules qui dépendent d'eux (vous pouvez l'obtenir en inversant toutes les arêtes dans le graphe ci-dessus), vous pouvez simplement charger les modules dans l'ordre du tri topologique.

J'ai mis à jour la description concernant le Tri Topologique, merci

OriginalL'auteur arnsholt
1

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

De plus, il n'est pas clair quelle transformation vous êtes en essayant de les appliquer. Connexion d'un DAG est un arbre, alors je crains que vous avez besoin de clarifier votre question un peu.

Pour être un pédant: Tout graphe connexe sans cycles est un arbre.
Je vois votre pédantisme et de s'élever: l'ensemble de tous les connectés dirigé acyclique de graphes, c'est un bon sous-ensemble de l'ensemble de toutes connecté graphes acycliques, par conséquent, de votre déclaration ("Tout connecté graphe sans cycles est un arbre") a officiellement implique la mine ("connexion d'Un DAG est un arbre").
Ne devrait-elle pas être "Tout dirigé connecté graphe sans cycles CONTIENT un arbre". Si A dépend de B et C; B dépend de D et de C dépend D, vous n'avez pas un arbre, vous avez un graphique qui contient deux arbres.

OriginalL'auteur MarkusQ
0

Vous ne pouvez le faire que si toutes les sous-arborescences avoir un seul nœud racine.

Vous pouvez toujours commencer avec un faux nœud racine.

OriginalL'auteur Mitch Wheat

Vous devez vous connecter pour publier un commentaire.