DAGstructuren

DAGstructuren, afgekort DAGs, zijn Directed Acyclic Graphs: grafen met richtinggevende randen en zonder cycli. Ze bestaan uit knopen en gerichte randen die afhankelijkheden of datastromen aangeven. Door afwezigheid van cycli is een topologische volgorde van knopen mogelijk.

Knooppunten kunnen meerdere inkomende en uitgaande verbindingen hebben. Bronnen (indegree 0) en eindknopen (outdegree 0) komen voor. Een DAG beschrijft een partiële orde en is ideaal voor het modelleren van afhankelijkheden en dataflow.

DAGs worden meestal opgesomd met lijsten of matrices. Een topologische sortering (bijv. via Kahn of DFS) levert een geldige uitvoeringsvolgorde op. De kosten voor basisoperaties zijn doorgaans O(n+m) voor een graf met n knopen en m randen.

Toepassingen: DAGs worden veel gebruikt in workflow- en datapijplijnen (zoals Apache Airflow en Luigi) om taakafhankelijkheden te modelleren. Build-systemen bepalen de volgorde van compilatie. In informatica en databankbeheer kunnen DAGs helpen bij planning en dataflow. Bayesian networks vormen een speciale soort DAG met probabilistische interpretatie, waarin knopen kansvariabelen voorstellen en randen afhankelijkheden aangeven.

Voorbeeld: een eenvoudige DAG met knopen A, B, C en D en randen A→B, A→C, B→D, C→D illustreert dat D pas kan starten nadat B en C voltooid zijn.

Beperkingen: DAGs vereenvoudigen afhankelijkheden maar kunnen complex worden in grote systemen. Detectie van cycli is essentieel bij het opzetten en onderhouden van modellen. Topologische volgorde biedt vaak een duidelijke uitvoering of evaluatievolgorde.