Abhängigkeitsgraph

Abhängigkeitsgraph ist ein gerichteter Graph, der Abhängigkeiten zwischen Entitäten abbildet. Die Knoten repräsentieren Komponenten, Aufgaben oder Objekte, und eine Kante von A nach B bedeutet typischerweise, dass A von B abhängt. Diese Struktur dient dazu, Abhängigkeiten sichtbar zu machen und deren Reihenfolge oder Verfügbarkeit zu klären.

In vielen Anwendungsfällen wird der Graph als azyklisch vorausgesetzt, er ist dann ein DAG (Directed Acyclic Graph). Zyklen deuten auf zirkuläre Abhängigkeiten hin, die problematisch sein können, weil sie eine klare Ausführungsreihenfolge verhindern. Solche Zyklen müssen oft durch Umbau der Architektur, das Aufbrechen von Modulen oder Versionsauflösungen behoben werden.

Darstellung und Verarbeitung erfolgen meist mit Adjazenzliste oder Adjazenzmatrix. Aus der transitive Hüllmenge lassen sich zusätzliche Abhängigkeiten ableiten. Zur Bestellung oder Planung wird häufig eine topologische Sortierung eingesetzt, die eine zulässige Reihenfolge liefert, in der die Abhängigkeiten erfüllt sind. Verfahren wie Kahn-Algorithmus oder DFS-basierte Sortierung sind gängige Methoden; bei vorhandenen Zyklen melden sie eine Fehlerquelle.

Anwendungsgebiete reichen von Build-Systemen und Paketverwaltungen über Task- oder Workflow-Planung bis hin zu Datenverarbeitungspipelines. Auch in der Sprachverarbeitung finden sich Abhängigkeitsgraphen, zum Beispiel zur Darstellung syntaktischer Abhängigkeiten zwischen Wörtern. Ein praktisches Beispiel ist ein Softwareprojekt, in dem A von B und C abhängt, während B von D abhängt; der Graph zeigt die notwendige Reihenfolge für Kompilierung oder Installation.