Directed acyclic graphs (DAGs)
Share
A directed acyclic graph, or DAG, is a set of vertices joined by one-way edges (arrows) in which you can never follow the arrows around and end up back where you started. Directed: every edge has a direction. Acyclic: there are no directed cycles.
That one restriction is what makes DAGs the shape of every "this has to happen before that" problem: build steps, data pipelines, course prerequisites, spreadsheet formulas, version history, and the computation graph a neural network framework records so it can run backpropagation.
Definition
A directed graph G = (V, E) is acyclic if there is no sequence of edges v1 → v2 → … → vk → v1 that returns to its start. Three equivalent ways of saying it:
- No directed cycles. The definition itself.
- Has a topological order. You can list the vertices in a line so that every edge points forwards, from an earlier vertex to a later one.
- Upper-triangular adjacency matrix. Number the vertices in a topological order and the adjacency matrix has zeros on and below the diagonal.
Every finite, non-empty DAG has at least one source (a vertex with no incoming edges) and at least one sink (no outgoing edges): start anywhere and follow arrows backwards (or forwards), and you must stop somewhere, because you can never revisit a vertex.
test and docs can run in either order, or in parallel.DAG vs tree
A DAG is not the same thing as a tree. In a rooted tree every vertex except the root has exactly one parent. In a DAG a vertex can have several: in the build above, package waits for both test and docs. This "diamond" (one vertex fanning out and the branches joining again) is the most common DAG shape that is not a tree. Every rooted tree, with its edges pointing away from the root, is a DAG; most DAGs are not trees.
Where DAGs show up
| System | Vertices | An edge u → v means |
|---|---|---|
| Build systems (Make, Bazel, CMake) | Targets and files | v depends on u, so build u first |
| Workflow schedulers (Apache Airflow, Dagster, Prefect) | Tasks | v runs after u succeeds |
| Git history | Commits | u is a parent of v (git stores the pointer from child to parent; a merge commit has two or more parents) |
| Neural network computation graphs (PyTorch autograd, TensorFlow, JAX) | Tensors and operations | v is computed from u |
| Spreadsheets | Cells | v's formula reads u; a cycle is the "circular reference" error |
| Course prerequisites | Courses | take u before v |
| Bayesian networks | Random variables | u is a direct cause (parent) of v |
Build systems and Airflow
A build tool reads the dependency graph and runs the steps in topological order, running independent steps in parallel. A dependency cycle (A needs B, B needs A) has no valid order, which is why build tools reject it with an error instead of guessing. Airflow made the word mainstream in data engineering: each pipeline is literally called a DAG. The Airflow documentation notes that the term comes from the mathematical concept but now means more than the bare data structure (schedules, retries, parameters), while the dependency structure underneath is still acyclic.
Git history
Each git commit stores the hashes of its parent commits, and its own hash is computed from its contents, parents included. To create a cycle, a commit would have to contain the hash of a commit that is created after it, which you cannot know in advance. So git history is a DAG by construction. A linear history is just a path; branches fan out; merge commits are the vertices with more than one parent. git log --graph draws it.
Neural network computation graphs
When a framework like PyTorch runs your forward pass, autograd records every operation. In PyTorch's own words, this gives "a directed acyclic graph whose leaves are the input tensors and roots are the output tensors". Backpropagation walks that graph in reverse topological order, applying the chain rule, so each gradient is computed only after every gradient that depends on it. A recurrent network looks like it has a loop, but the graph that is actually differentiated is the network unrolled through time, which is acyclic again.
Topological sort
A topological sort lists the vertices so that every edge goes from earlier to later. A graph has one if and only if it is a DAG. There are two standard algorithms, both linear time, O(V + E):
- Kahn's algorithm (1962). Repeatedly take a vertex with no remaining incoming edges, output it, and delete its outgoing edges. If vertices remain but none is free, the remainder contains a cycle.
- Depth-first search. Run DFS and record each vertex when you finish it; the reverse of that finishing order is a topological order. Meeting an edge back into a vertex that is still on the stack means a cycle.
The order is usually not unique. The build above has two valid orders, because test and docs can be swapped. Grouping the vertices into "generations" that can run at the same time gives the schedule a parallel build tool uses.
A DAG also makes some hard problems easy. The longest path in a general graph is NP-hard, but in a DAG you can find it in linear time by working through the vertices in topological order. In project planning that path is the critical path: the chain of tasks that sets the minimum finish time.
DAGs in Python with NetworkX
import networkx as nx
# A tiny build: compile, test, package, deploy
G = nx.DiGraph()
G.add_edges_from([
("fetch", "compile"),
("compile", "test"),
("compile", "docs"),
("test", "package"),
("docs", "package"),
("package", "deploy"),
])
print(nx.is_directed_acyclic_graph(G)) # True
print(list(nx.topological_sort(G)))
print([sorted(g) for g in nx.topological_generations(G)])
print(nx.dag_longest_path(G))
G.add_edge("deploy", "compile") # a back-edge
print(nx.is_directed_acyclic_graph(G)) # False
print(nx.find_cycle(G))
The output, in order: True; ['fetch', 'compile', 'test', 'docs', 'package', 'deploy']; [['fetch'], ['compile'], ['docs', 'test'], ['package'], ['deploy']]; ['fetch', 'compile', 'test', 'package', 'deploy']; then, after the back-edge, False and the cycle compile → test → package → deploy → compile. Tested with NetworkX 3.
FAQ
What does acyclic mean in a directed acyclic graph? It means there is no directed cycle: no way to follow the arrows from a vertex and arrive back at the same vertex.
Is a tree a DAG? A rooted tree with its edges pointing away from the root is a DAG. But a DAG is more general, because a vertex in a DAG can have more than one parent.
Can a DAG have more than one topological order? Yes, usually. The order is unique only when the DAG contains a path through every vertex (a Hamiltonian path).
Is git history a directed acyclic graph? Yes. Each commit records its parents' hashes and its own hash depends on them, so a commit can never be its own ancestor. Merge commits are the vertices with two or more parents.
Is a neural network a DAG? A feedforward network's computation graph is a DAG, and PyTorch's autograd records exactly that graph. A recurrent network has a loop in its diagram, but it is trained on the unrolled graph, which is acyclic.
How do I check whether a graph is a DAG in Python? Build a networkx.DiGraph and call nx.is_directed_acyclic_graph(G). If it returns False, nx.find_cycle(G) shows you a cycle.
Related: the Petersen graph explained and bipartite graphs explained. Buying for someone who builds pipelines? See our gifts for programmers guide. The hypercube graph explained is the undirected cube those directed edges came from.
The graph on a shirt
Two of the graphs in our Graphs collection become DAGs the moment you give their edges a direction. Point every edge of the cube on the Out of the Box hypercube tee from the corner with fewer 1s in its bit string to the one with more, and you get a DAG from 000 to 111. Number the vertices of the Fully Connected complete graph tee and point every edge from the lower number to the higher, and you get the DAG with the most edges possible: n(n − 1)/2. The rest of the line (Petersen, Erdős–Rényi, scale-free and small-world graphs) is in the Graphs collection. Buying for a mathematician? See our gifts for mathematicians guide.
Sources
- Directed acyclic graph, Wikipedia: en.wikipedia.org
- Topological sorting (Kahn's algorithm, DFS method), Wikipedia: en.wikipedia.org
- Topological sort, cp-algorithms: cp-algorithms.com
- NetworkX DAG algorithms: networkx.org
- Dags, Apache Airflow documentation: airflow.apache.org
- Autograd mechanics, PyTorch documentation: docs.pytorch.org
- Git Internals: Git Objects, Pro Git: git-scm.com
- A. B. Kahn, "Topological sorting of large networks", Communications of the ACM 5(11), 1962.