Kann mir jemand in einfachen Worten erklären, was ein gerichteter azyklischer Graph ist?

Kann mir jemand in einfachen Worten erklären, was ein gerichteter azyklischer Graph ist? Ich habe auf Wikipedia geschaut, aber es lässt mich nicht wirklich sehen, wie es in der Programmierung verwendet wird.

Punkte mit Linien, die auf andere Punkte zeigen

graph = Struktur bestehend aus Knoten, die durch Kanten miteinander verbunden sind

gerichtet = die Verbindungen zwischen den Knoten (Kanten) haben eine Richtung: A -> B ist nicht dasselbe wie B -> A.

acyclic = "unrund" = Wenn Sie den Knoten folgen, indem Sie den Kanten folgen, werden Sie nie zum zweiten Mal auf denselben Knoten stoßen.

Ein gutes Beispiel für einen gerichteten azyklischen Graphen ist ein Baum. Beachten Sie jedoch, dass nicht alle gerichteten azyklischen Graphen Bäume sind.

Ich sehe viele Antworten, die die Bedeutung von DAG (Directed Acyclic Graph) angeben, aber keine Antworten auf seine Anwendungen. Hier ist eine sehr einfache -

Voraussetzungsdiagramm - Während eines Ingenieurkurses steht jeder Student vor der Aufgabe, Fächer auszuwählen, die Anforderungen wie Voraussetzungen entsprechen. Jetzt ist klar, dass Sie keinen Kurs über künstliche Intelligenz [B] ohne einen erforderlichen Kurs über Algorithmen [A] belegen können. Daher hängt B von A ab oder besser gesagt, A hat eine Kante, die auf B gerichtet ist. Um also Knoten B zu erreichen, müssen Sie Knoten A besuchen. Es wird bald klar sein, dass nach dem Hinzufügen aller Themen mit seinen Voraussetzungen zu einem Diagramm Es wird sich herausstellen, dass es sich um einen gerichteten azyklischen Graphen handelt.

Wenn es einen Zyklus gäbe, würden Sie niemals einen Kurs absolvieren: p

Ein Softwaresystem an der Universität, mit dem sich Studenten für Kurse anmelden können, kann Fächer als Knoten modellieren, um sicherzustellen, dass der Student einen erforderlichen Kurs belegt hat, bevor er sich für den aktuellen Kurs anmeldet.

Mein Professor gab diese Analogie und sie hat mir am besten geholfen, die DAG zu verstehen, anstatt ein kompliziertes Konzept zu verwenden!

Ein weiteres Echtzeitbeispiel -> Echtzeitbeispiel, wie DAGs im Versionssystem verwendet werden können

Beispielanwendungen eines gerichteten azyklischen Graphen in der Programmierung umfassen mehr oder weniger alles, was Konnektivität und Kausalität darstellt.

Angenommen, Sie haben eine Berechnungspipeline, die zur Laufzeit konfiguriert werden kann. Nehmen wir als ein Beispiel an, dass die Berechnungen A, B, C, D, E, F und G voneinander abhängen: A hängt von C ab, C hängt von E und F ab, B hängt von D und E ab und D hängt von ab F. Dies kann als DAG dargestellt werden. Sobald Sie die DAG im Speicher haben, können Sie Algorithmen schreiben an:

• Stellen Sie sicher, dass die Berechnungen in der richtigen Reihenfolge ausgewertet werden ( topologische Sortierung ).
• Wenn Berechnungen parallel durchgeführt werden können, aber jede Berechnung eine maximale Ausführungszeit hat, können Sie die maximale Ausführungszeit des gesamten Satzes berechnen

unter vielen anderen Dingen.

Außerhalb des Bereichs der Anwendungsprogrammierung verwendet jedes anständige automatisierte Build-Tool (make, ant, scons usw.) DAGs, um die ordnungsgemäße Build-Reihenfolge der Komponenten eines Programms sicherzustellen.

In mehreren Antworten wurden Beispiele für die Verwendung von Diagrammen (z. B. Netzwerkmodellierung) angegeben, und Sie haben gefragt, was dies mit der Programmierung zu tun hat.

Die Antwort auf diese Unterfrage ist, dass sie nicht viel mit Programmierung zu tun hat. Es hat mit Problemlösung zu tun.

So wie verknüpfte Listen Datenstrukturen sind, die für bestimmte Problemklassen verwendet werden, sind Diagramme zur Darstellung bestimmter Beziehungen nützlich. Verknüpfte Listen, Bäume, Diagramme und andere abstrakte Strukturen haben nur eine Verbindung zur Programmierung, indem Sie sie in Code implementieren können. Sie existieren auf einer höheren Abstraktionsebene. Es geht nicht um Programmierung, sondern um die Anwendung von Datenstrukturen bei der Lösung von Problemen.

Directed Acyclic Graphs (DAG) haben die folgenden Eigenschaften, die sie von anderen Graphen unterscheiden:

1. Ihre Kanten zeigen die Richtung.
2. Sie haben keine Zyklen.

Nun, ich kann mir momentan eine Verwendung vorstellen - DAG (bekannt als Wait-For-Graphs - weitere technische Details ) ist praktisch, um Deadlocks zu erkennen, da sie die Abhängigkeiten zwischen einer Reihe von Prozessen und Ressourcen veranschaulichen (beide sind Knoten in der DAG). . Ein Deadlock würde auftreten, wenn ein Zyklus erkannt wird.

Ich gehe davon aus, dass Sie die grundlegende Graphenterminologie bereits kennen. Andernfalls sollten Sie mit dem Artikel über die Graphentheorie beginnen .

Directed bezieht sich auf die Tatsache, dass die Kanten (Verbindungen) Richtungen haben. Im Diagramm sind diese Richtungen durch die Pfeile dargestellt. Das Gegenteil ist ein ungerichteter Graph, dessen Kanten keine Richtungen angeben.

Azyklisch bedeutet, dass Sie, wenn Sie von einem beliebigen Knoten X ausgehen und alle möglichen Kanten durchlaufen, nicht zu X zurückkehren können, ohne auf eine bereits verwendete Kante zurückzukehren.

Mehrere Anwendungen:

• Tabellenkalkulationen; Dies wird im DAG- Artikel erläutert .
• Revisionskontrolle : Wenn Sie sich das Diagramm auf dieser Seite ansehen, werden Sie feststellen, dass die Entwicklung des revisionsgesteuerten Codes gerichtet (in diesem Diagramm "runter") und azyklisch (es geht nie wieder "rauf") ist. .
• Stammbaum: Er ist gerichtet (Sie sind das Kind Ihrer Eltern, nicht umgekehrt) und azyklisch (Ihre Vorfahren können niemals Ihr Nachkomme sein).

Bei der Programmierung werden Diagramme aller Art verwendet, um verschiedene reale Beziehungen zu modellieren. Beispielsweise wird ein soziales Netzwerk häufig durch ein Diagramm dargestellt (in diesem Fall zyklisch). Ebenso Netzwerktopologien, Stammbäume, Flugrouten, ...

Eine DAG ist ein Diagramm, in dem alles in die gleiche Richtung fließt und kein Knoten auf sich selbst verweisen kann.

Denken Sie an Ahnenbäume; Sie sind eigentlich DAGs.

Alle DAGs haben

• Knoten (Orte zum Speichern von Daten)
• Gerichtete Kanten (die in dieselbe Richtung zeigen)
• Ein Ahnenknoten (ein Knoten ohne Eltern)
• Blätter (Knoten, die keine Kinder haben)

DAGs unterscheiden sich von Bäumen. In einer baumartigen Struktur muss zwischen jeweils zwei Knoten ein eindeutiger Pfad vorhanden sein. In DAGs kann ein Knoten zwei übergeordnete Knoten haben.

Hier ist ein guter Artikel über DAGs . Ich hoffe das hilft.

Aus der Perspektive eines Quellcodes oder sogar eines TAC-Codes (Three Address) können Sie das Problem auf dieser Seite ganz einfach visualisieren ...

http://cgm.cs.mcgill.ca/~hagha/topic30/topic30.html#Exptree

Wenn Sie zum Abschnitt mit dem Ausdrucksbaum gehen und dann ein wenig nach unten blättern, werden die "topologische Sortierung" des Baums und der Algorithmus zur Bewertung des Ausdrucks angezeigt.

In diesem Fall können Sie die DAG zum Auswerten von Ausdrücken verwenden. Dies ist praktisch, da die Auswertung normalerweise interpretiert wird und die Verwendung eines solchen DAG-Auswerters einfache Interpretatoren im Prinzip schneller macht, da sie nicht auf einen Stapel verschoben und verschoben werden und auch eliminiert werden gebräuchliche Unterausdrücke.

Der grundlegende Algorithmus zur Berechnung der DAG in nicht altägyptischem (dh Englisch) ist folgender:

1) Machen Sie Ihr DAG-Objekt so

Sie benötigen eine Live-Liste und diese Liste enthält alle aktuellen Live-DAG-Knoten und DAG-Unterausdrücke. Ein DAG-Unterausdruck ist ein DAG-Knoten, oder Sie können ihn auch als internen Knoten bezeichnen. Was ich unter Live-DAG-Knoten verstehe, ist, dass wenn Sie einer Variablen X zuweisen, diese live wird. Ein allgemeiner Unterausdruck, der dann X verwendet, verwendet diese Instanz. Wenn X erneut zugewiesen wird, wird ein NEUER DAG-NODE erstellt und zur Live-Liste hinzugefügt, und das alte X wird entfernt, sodass der nächste Unterausdruck, der X verwendet, auf die neue Instanz verweist und somit nicht mit diesen Unterausdrücken in Konflikt steht Verwenden Sie lediglich denselben Variablennamen.

Sobald Sie einer Variablen X zugewiesen haben, werden zufällig alle DAG-Unterausdrucksknoten, die zum Zeitpunkt der Zuweisung aktiv sind, nicht mehr aktiv, da die neue Zuweisung die Bedeutung von Unterausdrücken unter Verwendung des alten Werts ungültig macht.

class Dag {
  TList LiveList;
  DagNode Root;
}

// In your DagNode you need a way to refer to the original things that
// the DAG is computed from. In this case I just assume an integer index
// into the list of variables and also an integer index for the opertor for
// Nodes that refer to operators. Obviously you can create sub-classes for
// different kinds of Dag Nodes.
class DagNode {
  int Variable;
  int Operator;// You can also use a class
  DagNode Left;
  DagNode Right;
  DagNodeList Parents;
}

Sie gehen also in Ihrem eigenen Code durch Ihren Baum, z. B. in einem Ausdrucksbaum im Quellcode. Rufen Sie beispielsweise die vorhandenen Knoten XNodes auf.

Für jeden XNode müssen Sie also entscheiden, wie er zur DAG hinzugefügt werden soll, und es besteht die Möglichkeit, dass er sich bereits in der DAG befindet.

Dies ist ein sehr einfacher Pseudocode. Nicht zum Zusammenstellen gedacht.

DagNode XNode::GetDagNode(Dag dag) {
  if (XNode.IsAssignment) {
    // The assignment is a special case. A common sub expression is not
    // formed by the assignment since it creates a new value.

    // Evaluate the right hand side like normal
    XNode.RightXNode.GetDagNode();  


    // And now take the variable being assigned to out of the current live list
    dag.RemoveDagNodeForVariable(XNode.VariableBeingAssigned);

    // Also remove all DAG sub expressions using the variable - since the new value
    // makes them redundant
    dag.RemoveDagExpressionsUsingVariable(XNode.VariableBeingAssigned);

    // Then make a new variable in the live list in the dag, so that references to
    // the variable later on will see the new dag node instead.
    dag.AddDagNodeForVariable(XNode.VariableBeingAssigned);

  }
  else if (XNode.IsVariable) {
    // A variable node has no child nodes, so you can just proces it directly
    DagNode n = dag.GetDagNodeForVariable(XNode.Variable));
    if (n) XNode.DagNode = n;
    else {
      XNode.DagNode = dag.CreateDagNodeForVariable(XNode.Variable);
    }
    return XNode.DagNode;
  }
  else if (XNode.IsOperator) {
    DagNode leftDagNode = XNode.LeftXNode.GetDagNode(dag);
    DagNode rightDagNode = XNode.RightXNode.GetDagNode(dag);


    // Here you can observe how supplying the operator id and both operands that it
    // looks in the Dags live list to check if this expression is already there. If
    // it is then it returns it and that is how a common sub-expression is formed.
    // This is called an internal node.
    XNode.DagNode = 
      dag.GetOrCreateDagNodeForOperator(XNode.Operator,leftDagNode,RightDagNode) );

    return XNode.DagNode;
  }
}

Das ist also eine Sichtweise. Ein einfacher Spaziergang durch den Baum und das Hinzufügen und Verweisen auf die Dag-Knoten. Die Wurzel des Dags ist der DagNode, den die Wurzel des Baums beispielsweise zurückgibt.

Offensichtlich kann die Beispielprozedur in kleinere Teile zerlegt oder als Unterklassen mit virtuellen Funktionen erstellt werden.

Zum Sortieren des Dag gehen Sie jeden DagNode von links nach rechts durch. Mit anderen Worten, folgen Sie der linken Kante von DagNodes und dann der rechten Seitenkante. Die Nummern werden umgekehrt vergeben. Mit anderen Worten, wenn Sie einen DagNode ohne untergeordnete Elemente erreichen, weisen Sie diesem Knoten die aktuelle Sortiernummer zu und erhöhen Sie die Sortiernummer, damit die Nummern beim Abwickeln der Rekursion in aufsteigender Reihenfolge zugewiesen werden.

In diesem Beispiel werden nur Bäume mit Knoten behandelt, die null oder zwei untergeordnete Elemente haben. Offensichtlich haben einige Bäume Knoten mit mehr als zwei untergeordneten Elementen, sodass die Logik immer noch dieselbe ist. Anstatt links und rechts zu berechnen, rechnen Sie von links nach rechts usw.

// Most basic DAG topological ordering example.
void DagNode::OrderDAG(int* counter) {
  if (this->AlreadyCounted) return;

  // Count from left to right
  for x = 0 to this->Children.Count-1
    this->Children[x].OrderDag(counter)

  // And finally number the DAG Node here after all
  // the children have been numbered
  this->DAGOrder = *counter;

  // Increment the counter so the caller gets a higher number
  *counter = *counter + 1;

  // Mark as processed so will count again
  this->AlreadyCounted = TRUE;
}

Wenn Sie wissen, welche Bäume programmiert werden, sind die DAGs in der Programmierung ähnlich, ermöglichen es einem Knoten jedoch, mehr als ein übergeordnetes Element zu haben. Dies kann nützlich sein, wenn Sie einen Knoten unter mehr als nur einem übergeordneten Element zusammenfassen möchten, aber nicht das Problem eines verknoteten Durcheinanders eines allgemeinen Graphen mit Zyklen haben möchten. Sie können weiterhin problemlos in einer DAG navigieren, es gibt jedoch mehrere Möglichkeiten, um zum Stammverzeichnis zurückzukehren (da es mehr als ein übergeordnetes Element geben kann). Eine einzelne DAG kann im Allgemeinen mehrere Wurzeln haben, in der Praxis ist es jedoch möglicherweise besser, nur an einer Wurzel wie einem Baum festzuhalten. Wenn Sie die Einzel- oder Mehrfachvererbung in OOP verstehen, kennen Sie Tree vs. DAG. Ich antwortete , das schon hier .

Der Name sagt Ihnen das meiste, was Sie über seine Definition wissen müssen: Es ist ein Diagramm, in dem jede Kante nur in eine Richtung fließt und wenn Sie eine Kante hinunterkriechen, wird Ihr Pfad Sie niemals zu dem Scheitelpunkt zurückbringen, den Sie gerade verlassen haben.

Ich kann nicht mit allen Verwendungszwecken sprechen (Wikipedia hilft dort), aber für mich sind DAGs äußerst nützlich, um Abhängigkeiten zwischen Ressourcen zu bestimmen. Meine Spiel-Engine repräsentiert beispielsweise alle geladenen Ressourcen (Materialien, Texturen, Shader, Klartext, analysierte JSON usw.) als eine einzige DAG. Beispiel:

Ein Material sind N GL-Programme, die jeweils zwei Shader benötigen, und jeder Shader benötigt eine Klartext-Shader-Quelle. Durch die Darstellung dieser Ressourcen als DAG kann ich das Diagramm leicht nach vorhandenen Ressourcen abfragen, um doppelte Ladevorgänge zu vermeiden. Angenommen, Sie möchten, dass mehrere Materialien Vertex-Shader mit demselben Quellcode verwenden. Es ist verschwenderisch, die Quelle neu zu laden und die Shader für jede Verwendung neu zu kompilieren, wenn Sie nur eine neue Kante für die vorhandene Ressource erstellen können. Auf diese Weise können Sie das Diagramm auch verwenden, um festzustellen, ob etwas von einer Ressource abhängt, und wenn nicht, löschen Sie es und geben Sie seinen Speicher frei. Dies geschieht tatsächlich ziemlich automatisch.

DAGs sind nützlich, um Datenverarbeitungs-Pipelines auszudrücken. Die azyklische Natur bedeutet, dass Sie sicher kontextbezogenen Verarbeitungscode schreiben können, der Zeigern entlang der Kanten eines Scheitelpunkts folgen kann, ohne jemals wieder auf denselben Scheitelpunkt zu stoßen. Visuelle Programmiersprachen wie VVVV , Max MSP oder die knotenbasierten Schnittstellen von Autodesk Maya basieren alle auf DAGs.

Ein gerichteter azyklischer Graph ist nützlich, wenn Sie ... einen gerichteten azyklischen Graphen darstellen möchten! Das kanonische Beispiel ist ein Stammbaum oder eine Genealogie.