Directed Acyclic Graph
Ein Directed Acyclic Graph ist ein Netz aus Punkten und Pfeilen, in dem man niemals im Kreis laufen kann. Diese Struktur beschreibt Abhängigkeiten und Reihenfolgen und steckt in Bauplänen von Software, in Datenpipelines und in Blockchain-Systemen.
Stell dir einen Plan vor, in dem Aufgaben als Punkte eingezeichnet sind. Zwischen den Punkten laufen Pfeile: Ein Pfeil von A nach B bedeutet, dass A vor B kommen muss. Ein solches Netz aus Punkten und Pfeilen nennt man in der Informatik einen Graphen. Weil die Pfeile eine feste Richtung haben, ist er gerichtet. Und er ist azyklisch, wenn man von keinem Punkt aus über die Pfeile jemals wieder zu sich selbst zurückkommt. Genau diese Kombination heißt Directed Acyclic Graph, kurz DAG.
Warum Kreisfreiheit so viel wert ist
Ein Kreis in einem Abhängigkeitsplan ist eine Katastrophe. Wenn Aufgabe A auf B wartet, B auf C und C wieder auf A, wartet alles für immer. Solche Situationen heißen Deadlocks, also Blockaden, aus denen ein System nicht mehr herauskommt. Ein DAG schließt sie durch seine Bauart aus. Deshalb prüfen viele Programme zuerst, ob ihr Abhängigkeitsnetz wirklich kreisfrei ist.
Die Kreisfreiheit bringt noch einen zweiten Vorteil. In einem DAG lässt sich immer mindestens eine gültige Reihenfolge finden, in der man alle Punkte abarbeiten kann. Fachleute nennen das eine topologische Sortierung. Praktisch heißt das: Ein Computer kann selbst ausrechnen, womit er anfangen muss und was danach dran ist.
Außerdem sieht ein Rechner sofort, welche Aufgaben voneinander unabhängig sind. Solche Aufgaben kann er gleichzeitig auf mehreren Prozessorkernen erledigen. Ein großer Bauprozess, der nacheinander eine Stunde dauert, schrumpft so oft auf wenige Minuten. Diese automatische Parallelisierung ist einer der Hauptgründe für die Beliebtheit von DAGs.
Punkte, Pfeile und die Suche nach Zyklen
Formal besteht ein DAG aus Knoten und Kanten. Knoten sind die Punkte, also zum Beispiel Aufgaben, Dateien oder Rechenschritte. Kanten sind die Pfeile dazwischen und stehen für eine Abhängigkeit. Ein Knoten ohne eingehende Pfeile kann sofort starten. Ein Knoten mit drei eingehenden Pfeilen wartet, bis alle drei Vorgänger fertig sind.
Um zu prüfen, ob ein Graph wirklich azyklisch ist, geht ein Algorithmus ihn Schritt für Schritt durch. Eine verbreitete Methode entfernt wiederholt alle Knoten, die keine offenen Vorgänger mehr haben. Bleibt am Ende kein Knoten übrig, ist der Graph kreisfrei. Bleibt ein Rest übrig, steckt darin ein Zyklus, und das Programm meldet einen Fehler.
Ein häufiger Irrtum ist die Gleichsetzung von DAG und Baum. Ein Baum ist ein Spezialfall: Dort hat jeder Knoten höchstens einen Vorgänger. In einem DAG darf ein Knoten dagegen mehrere Vorgänger haben. Ein Bauteil kann also von zwei verschiedenen Vorstufen abhängen, ohne dass die Struktur ihre Kreisfreiheit verliert.
Von Datenpipelines bis zur Blockchain
Im Alltag der Softwareentwicklung begegnen DAGs vor allem in Werkzeugen für Datenpipelines. Ein Programm wie Apache Airflow beschreibt jeden Arbeitsablauf ausdrücklich als DAG. Daten werden geladen, bereinigt, ausgewertet und dann in einen Bericht geschrieben. Jeder Schritt ist ein Knoten, jede Abhängigkeit ein Pfeil.
Auch beim Training von KI-Modellen steckt ein DAG im Hintergrund. Die Rechenschritte eines neuronalen Netzes bilden einen Berechnungsgraphen. Frameworks wie PyTorch nutzen ihn, um automatisch auszurechnen, wie jeder Parameter das Ergebnis beeinflusst. Ohne diese Struktur wäre das Training großer Modelle praktisch nicht machbar.
In Finanz- und Tech-News taucht der Begriff außerdem bei Kryptowährungen auf. Manche Systeme wie IOTA oder Hedera speichern Transaktionen nicht in einer Kette aus Blöcken, sondern in einem DAG. Mehrere Transaktionen können sich dann gleichzeitig aufeinander beziehen, was theoretisch höhere Geschwindigkeit erlaubt. Wenn ein Artikel eine Technologie als DAG-basiert bezeichnet, ist meist genau das gemeint.