directed acyclic graph
A directed graph with no cycles, so following edges can never bring you back to where you started.
In more detail
Build systems, course prerequisites, spreadsheet formulas and task pipelines are all DAGs of dependencies. Every DAG has at least one topological order, and only DAGs do.
Example
Dynamic programming subproblems also form a DAG.Related terms
- topological sort — An ordering of a directed graph's vertices in which every edge points from an earlier vertex to a later one.
- Kahn's algorithm — A topological sort that repeatedly removes a vertex with no remaining incoming edges and lowers the in-degree of its neighbours.
- cycle detection — Finding whether a graph contains a cycle; in a directed graph, DFS with three colours finds one by spotting an edge back to a vertex still in progress.
- build system — A tool that works out which parts of a software project must be rebuilt, and in what order, from a graph of dependencies.
- needs — The job key that makes a job wait until the jobs it names have finished successfully.
- job (GitHub Actions) — A named group of steps in a workflow that runs on one runner of its own.
- task graph — A map of which build tasks depend on which others, used to decide what must run first and what can run at the same time.
- circular dependency — Two or more pieces of code or data that depend on each other in a loop, so none can be built or resolved first.
Taught in
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- One Commit, Four Argo Projects — Certified Argo Project Associate (CAPA) Exam Prep
- How The Exam Works: Weights, Pacing And A Plan — Certified Argo Project Associate (CAPA) Exam Prep
- What Argo Workflows Runs: Controller, Server And One Pod A Step — Certified Argo Project Associate (CAPA) Exam Prep
- Template Types: Nine Ways To Do A Step — Certified Argo Project Associate (CAPA) Exam Prep
- WorkflowTemplates, ClusterWorkflowTemplates And templateRef — Certified Argo Project Associate (CAPA) Exam Prep
- DAGs: depends, Results And Who Decides The Phase — Certified Argo Project Associate (CAPA) Exam Prep
- Retries, Exit Handlers, Conditions And Deadlines — Certified Argo Project Associate (CAPA) Exam Prep
- Final Mock, Review And A Trap Sprint — Certified Argo Project Associate (CAPA) Exam Prep
- Workflows, Jobs, Steps, and Actions — Continuous Integration & Continuous Delivery Pipelines
- Monorepo Architecture: Workspaces & Turborepo — Production Full-Stack Engineering
- Unified Build Pipelines: Caching & Dependency Graphs — Production Full-Stack Engineering
- Stages Versus Needs: Building The Pipeline As A Graph — GitLab Certified CI/CD Associate Exam Prep
- Debugging Pipelines: The Graph, The Errors, The Logs — GitLab Certified CI/CD Associate Exam Prep
References
- NIST Dictionary of Algorithms and Data Structures: directed acyclic graph
- GitHub Docs: Using jobs in a workflow
- Turborepo: Package and task graphs