# Directed Acyclic Graphs (DAG) A Directed Acyclic Graph (DAG) is a graph data structure where edges have a direction and no cycles exist. This means you can never start at a node and follow the edges back to the same node. DAGs are fundamental in computer science and appear everywhere: from version control systems to task scheduling, dependency management, and data processing pipelines. ## Key Properties - **Directed**: Each edge has a source and destination node - **Acyclic**: No path exists that starts and ends at the same node - **Topological ordering**: Nodes can always be arranged in a linear order where all edges point forward - **Multiple paths**: Unlike trees, a node can have multiple parents ## Common Applications ### Version Control Git uses DAGs to track commits. Each commit points to its parent(s), enabling branching and merging without cycles. ### Task Scheduling Dependencies between tasks form a DAG. [[Beads]] and [[Beads Viewer]] use DAGs to visualize task dependencies and find critical paths. ### Build Systems Tools like Make, Bazel, and Gradle model build dependencies as DAGs to determine compilation order and parallelize work. ### Data Pipelines Apache Airflow and similar tools represent workflows as DAGs, ensuring tasks execute in the correct order. ### Blockchain Some cryptocurrencies (IOTA, Hedera) use DAG structures instead of linear chains for transaction ordering. ## Graph Metrics When analyzing DAGs, useful metrics include: - **Critical path**: Longest path determining minimum completion time - **Topological sort**: Valid execution order respecting dependencies - **PageRank**: Importance based on incoming connections - **Betweenness centrality**: Nodes that bridge different parts of the graph ## References - https://en.wikipedia.org/wiki/Directed_acyclic_graph ## Related - [[Beads]] - [[Beads Viewer]] - [[Git]] - [[Graph Theory]] - [[LangChain]] - [[LangGraph]]