Wie konvertiert gerichteten azyklischen Graphen (DAG) zu Baum

StackOverflow https://stackoverflow.com/questions/624778

Frage

Ich habe für C # Beispiele suche eine DAG in einen Baum zu verwandeln.

Hat jemand ein Beispiel oder Hinweise in der richtigen Richtung hat?

Klarstellung aktualisieren

Ich habe eine grafische Darstellung, die eine Liste von Modulen enthält, die meine Anwendung erforderlich ist, zu laden. Jedes Modul verfügt über eine Liste von Modulen es hängt davon ab. Zum Beispiel hier sind meine Module, A, B C, D und E

  • A hat keine Abhängigkeiten
  • B ist abhängig von A, C und E
  • C hängt von A
  • D hängt von A
  • E hängt von C und A

Ich will Abhängigkeiten auflösen und einen Baum zu erzeugen, die so aussieht ...

- A

- + - B

----- + - C

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

- + - E

Topologische ordnen

Vielen Dank für die Informationen, wenn ich eine topologische Sortierung und umgekehrt die Ausgabe durchführen i wird die folgende Reihenfolge haben

  • A
  • B
  • C
  • D
  • E

Ich mag die hierarchische Struktur halten, so dass meine Module in den richtigen Kontext geladen werden, zum Beispiel ... Modul E in demselben Behälter wie B sein sollte

Danke

Rohan

War es hilfreich?

Lösung

Es gibt die graphentheoretische Antwort und die Antwort der Programmierer auf diese. Ich nehme an, Sie behandeln können die Programmierer selbst trennen. Für die grafische Darstellung theorethical Antwort:

  • Ein DAG ist ein Satz von Modulen, wo es passiert nie, dass A B benötigt, und zugleich, B (oder eines der Module B Bedürfnisse) benötigt A, in Module-sprechen: keine zirkuläre Abhängigkeit. Ich habe zirkuläre Abhängigkeiten passieren gesehen (die Gentoo-Foren für Beispiele suchen), so dass Sie nicht einmal zu 100% sicher, dass Sie eine DAG, aber nehmen wir an, Sie haben. Es ist es nicht sehr schwer, eine Prüfung auf zirkuläre Abhängigkeiten zu tun, so würde ich empfehlen, die Sie in Ihren Modul-Lader so irgendwo tun.
  • In einem Baum, etwas, das nie passieren kann, ist, dass A auf B und C abhängt und dass beide B und C ist abhängig von D (ein Diamant), aber dies in einem DAG passieren kann.
  • Auch hat ein Baum genau einen Wurzelknoten, sondern ein DAG kann mehr „root“ Knoten (das heißt Module, die nichts hängt von) hat. Zum Beispiel kann ein Programm wie GIMP, wird das GIMP-Programm der Wurzelknoten des Satzes von Modulen sein, aber für GENTOO, fast jedes Programm mit einem GUI ist ein „root“ Knoten, während die Bibliotheken usw. Abhängigkeiten von ihnen sind. (Das heißt sowohl Konqueror und KMail hängen von Qtlib, aber nichts hängt von Konqueror, und nichts ist abhängig von KMail)

Der Graph theorethical auf Ihre Frage beantworten, wie andere darauf hingewiesen, dass ein DAG kann nicht auf einen Baum umgewandelt werden, während jeder Baum ein DAG ist.

Allerdings (High-Level-Programmierer beantworten), wenn Sie den Baum für grafische Darstellungen wollen, sind Sie in den Abhängigkeiten eines speziellen Moduls nur daran interessiert, nicht das, was an diesem Modul ist abhängig. Lassen Sie mich ein Beispiel geben: 

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

Das kann ich nicht zeigen, als ASCII-Kunst-Baum, aus dem einfachen Grunde, dass dies nicht in einen Baum umgewandelt werden. Allerdings, wenn Sie wollen zeigen, was A hängt davon ab, können Sie dies zeigen: 

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

Wie Sie sehen, erhalten Sie doppelte Einträge in Ihrem Baum - in diesem Fall „nur“ D aber wenn Sie eine „alle erweitern“ auf dem Gentoo Baum tun, garantiere ich Ihnen, dass Ihr Baum mindestens 1000-mal die Menge hat da es von Knoten sind Module. (Es gibt mindestens 100 Pakete, die auf Qt abhängig, also alles Qt ist abhängig von mindestens 100 mal im Baum vorhanden sein).

Wenn Sie einen „großen“ oder „komplex“ Baum haben, könnte es am besten sein, den Baum dynamisch zu erweitern, nicht im Voraus, sonst könnte man einen sehr speicherintensiven Prozess hat.

Der Nachteil des Baumes über das ist, wenn Sie offen B klicken, dann D, sehen Sie, dass A und B auf D ab, aber nicht, dass auch abhängig C auf D. jedoch je nach Ihrer Situation, könnte dies nicht sein wichtig überhaupt - wenn Sie eine Liste der geladenen Module halten, beim Laden C Sie sehen, dass Sie D bereits geladen haben, und es spielt keine Rolle, es nicht für C geladen wurde, aber für B. es wird geladen, das ist alles, was Angelegenheiten. Wenn Sie dynamisch halten, was an einem bestimmten Modul direkt abhängig ist, können Sie das entgegengesetzte Problem (Entladen) als auch handhaben.

Doch was kann man nicht mit einem Baum tun, was in Ihrem letzten Satz heißt: bewahren topologische Ordnung, dh wenn B im selben Behälter wie C geladen wird, werden Sie nie C in demselben Behälter zu laden, erhalten als Gut. Oder Sie könnten mit Putting alles in einem Behälter haben setzen (nicht, dass ich voll und ganz verstehen, was du meinst mit „Laden in den gleichen Behälter“)

Viel Glück!

Andere Tipps

Ein DAG und ein Baum ist nicht die gleiche Sache mathematisch. Somit führt jede Umwandlungs Mehrdeutigkeit. Ein Baum definitions hat keine Zyklen, period.

Was Sie suchen, um die zu finden, um Ihre Module in zu laden, ist die topologische Sortierung Ihrer DAG. Wenn die Kanten von einem Modul an die Module gehen sie davon abhängt, (was ich denke, die meisten wahrscheinlich ist), werden Sie die Module in der umgekehrten Reihenfolge der topologischen Art laden müssen, weil ein Modul -before- alle Module angezeigt davon abhängt, welche es.

Wenn Sie die DAG, so dass die Kanten von dem hängt von Modulen zu den Modulen gehen repräsentieren, die von ihnen abhängig ist (Sie können dies erhalten, indem alle Kanten in der graphischen Darstellung Umkehren oben), können Sie die Module in der Reihenfolge laden Sie einfach die topologischen Art.

Es hängt viel ab, wie Sie Ihre DAG vertreten. Zum Beispiel könnte es sich um eine Adjazenzmatrix (A [i, j] = 1, wenn eine Kante von dem Knoten gibt es i Knoten j, sonst 0), oder als ein System von Zeigern oder als eine Anordnung von Knoten und einer Anordnung von Kanten ....

Ferner ist es nicht klar, welche Transformation Sie anwenden versuchen. Eine angeschlossene DAG ist ein Baum, so muss ich fürchte, Sie Ihre Frage ein wenig klären.

Sie können nur tun, wenn alle Teilbäume haben einen einzigen Wurzelknoten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top