DAG Terminology

A DAG (Directed Acyclic Graph) is a network of points called nodes connected by one-way arrows called edges, where you can never follow the arrows and return to your starting point—there are no circular loops. Think of it like a family tree: a parent points to a child, but no one can be their own grandparent. This structure makes DAGs perfect for representing situations where order matters, such as task prerequisites in a project or cause-and-effect chains in science. Nodes represent the items or events, edges show the relationships or dependencies, and because there are no cycles, there's always at least one valid way to line everything up from start to finish. Try this: When planning your next project, sketch which tasks depend on others—you're drawing a DAG.

DAG terminology provides a precise language for talking about structures where things point to other things without creating loops. Nodes (also called vertices) are the fundamental building blocks—they can represent tasks, variables, events, or any entity of interest. Edges (or arcs) are the directed connections between nodes, always pointing from a source to a target. When you can follow edges from one node to another, you've found a path, and the source node is called an ancestor while the target is a descendant.

The power of DAG terminology comes from its ability to capture precedence and causality. In project management, a task A that must complete before task B begins is represented as an edge from A to B. In causal inference, an arrow from X to Y indicates that X influences Y. The no-cycles rule is crucial: it means there's always at least one valid topological ordering—a way to arrange all nodes in a line so that every edge points forward. This is why build systems, data pipelines, and schedulers rely on DAGs: they guarantee that dependencies can be resolved without getting stuck in circular dependencies.

DAG terminology extends to several specialized concepts. A source node has no incoming edges (nothing points to it), making it a natural starting point. A sink node has no outgoing edges (nothing points away from it), marking an endpoint. The transitive closure of a DAG adds all indirect connections as direct edges—if A points to B and B points to C, the closure adds an edge from A to C. The transitive reduction does the opposite, removing redundant edges to keep only the essential relationships. Together, these terms give you a complete vocabulary for analyzing and manipulating dependency structures across computer science, data engineering, causal reasoning, and beyond.

DAG terminology originates from graph theory in discrete mathematics and has been formalized in computer science literature. Bang-Jensen and Gutin (2008) provide comprehensive definitions for directed graphs, distinguishing between vertices (nodes) and arcs (directed edges), and establish the formal properties of reachability, ancestors, and descendants in DAG structures [1]. Cormen et al. (2022) in the canonical algorithms textbook define topological ordering as a linear arrangement of vertices such that every directed edge points from an earlier vertex to a later one, and prove that a graph is acyclic if and only if a topological ordering exists [2].

Key terminology findings:

• Pearl (2009): Formalizes causal DAGs where nodes represent random variables and edges represent direct causal influences, establishing ancestor/descendant relationships as the foundation for causal inference algorithms [3].
• Bang-Jensen & Gutin (2008): Define the transitive closure of a DAG as the graph containing an edge from u to v whenever v is reachable from u, and the transitive reduction as the minimal subgraph preserving all reachability relationships [1].
• Cormen et al. (2022): Show that topological sorting of DAGs runs in linear time, making DAG-based scheduling and dependency resolution computationally efficient [2].

DAGs provide the mathematical foundation for representing partial orders—relations that are reflexive, antisymmetric, and transitive. Every finite partially ordered set corresponds to a DAG, and the reachability relation of a DAG defines a partial order on its vertices.

DAG terminology has limitations in domains where cycles are fundamental features rather than problems to avoid. In feedback systems, recurrent neural networks, and many biological processes, circular relationships are essential. DAG-based causal models also assume static relationships and may struggle with time-varying or bidirectional causation. The terminology can become ambiguous when applied to probabilistic graphical models where edges represent correlation rather than direct causation. Additionally, topological ordering is not unique—most DAGs have multiple valid orderings, which can lead to confusion about which ordering is "correct" for a given application.