Directed Acyclic Graph (DAG)

A Directed Acyclic Graph (DAG) is a directed graph containing no directed cycles.

Core Properties

• Directed: Edges have a specific orientation, defining a one-way relationship between vertices.
• Acyclic: There are no paths that allow a traversal to start and end at the same vertex.
• Topological Ordering: Every DAG allows for a linear ordering of vertices such that for every directed edge $[[concepts/package-manager|uv]]$, vertex $u$ comes before $v$ in the ordering.

Key Applications

• Build Systems: Managing task dependencies in tools like Make or Bazel.
• Data Pipelines: Orchestrating complex workflows (e.g., Apache Airflow).
• Git Version Control:
  • Utilizes a DAG to represent commits, Branches, and project history.
  • Commits serve as nodes, while parent pointers function as directed edges.
  • This structure ensures a traceable, non-circular lineage of changes and enables efficient merging.
  • Reference: 2026 04 27 Gits Underlying Data Structures Commits Branches and DAG

Source Notes

• 2026-04-14: [[lab-notes/2026-04-14-Optimizing-AI-Costs-and-Privacy-with-Local-Open-Source-Models-and-Hybr|“But OpenClaw is expensive…“]]