What Is a Directed Acyclic Graph in CI? Modeling Job Order
A directed acyclic graph (DAG) models a pipeline as jobs (nodes) connected by dependencies (directed edges) that never form a cycle.
Under the hood, a CI scheduler does not see a list of jobs; it sees a graph. Each job is a node, each dependency is a directed edge pointing from a prerequisite to a dependent, and the graph has no cycles (nothing can depend on itself, directly or indirectly). This DAG is what lets the pipeline figure out what can run now and what must wait.
Why "directed" and "acyclic"
- Directed: edges have a direction (A must finish before B).
- Acyclic: no cycles, so dependencies cannot loop forever.
- Graph: jobs and their dependency edges together.
How the scheduler uses it
The scheduler runs any job whose prerequisites are all complete. As jobs finish, more become eligible. This naturally parallelizes independent branches of the graph while respecting every dependency.
A quick example
Build feeds both lint and test; test feeds deploy. The DAG runs build first, then lint and test in parallel, then deploy once test is done. Lint and deploy never have to wait on each other.
Why cycles are forbidden
If job A depended on B and B depended on A, neither could ever start. CI tools reject such cycles at validation time, because an acyclic graph is the only kind that can actually be scheduled to completion.
DAG shape and pipeline time
A wide, shallow DAG runs fast because many jobs go in parallel. A deep, narrow DAG runs slowly because each step waits for the last. The longest path through the DAG is the critical path that bounds total time.
Key takeaways
- A CI DAG models jobs as nodes and dependencies as directed, acyclic edges.
- The scheduler runs each job once all its prerequisites complete.
- A wider graph parallelizes more; the longest path bounds total time.