What is a directed acyclic graph (DAG)?

A directed acyclic graph (DAG) is a type of graph in which nodes are linked by one-way connections that do not form any cycles. DAGs are used to illustrate dependencies and causal relationships.

Like all graphs, DAGs can be helpful for visualizing relationships between nodes representing data, tasks or events. However, DAGs are useful in depicting systems where events happen in a specific order, such as a schedule of tasks that must be completed to achieve a goal.

DAGs are also important for creating causal diagrams: DAGs can represent systems where some nodes impact other nodes, but the causal effects don’t work in the opposite direction. A basic example of such one-way relationships can be found in family trees as DAGs map successive generations of parents and children.

The application of DAGs is common in computer science, with developers and engineers using DAGS for data pipelines and data processing, neural network architecture, robotics and more.

To better understand what a directed acyclic graph is, let’s break down its components:

Nodes: Nodes, also known as vertices, represent entities, objects or variables on a graph. They are typically depicted as dots or circles.

Edges: Edges represent connections between entities. They are depicted as lines.

Directed edges: Directed edges represent connections that might be traversed in only 1 direction. Arrows on such edges indicate their direction.

Directed graphs: Graphs made up entirely of directed edges are directed graphs or digraphs. In contrast, graphs without directed edges are undirected graphs.

Colliders: Colliders are nodes that have 2 directed edges pointing at them.

Paths: Paths are a sequence of edges connecting 1 given node to another. Paths consisting entirely of directed edges are known as directed paths. Directed paths that indicate causal relationships are called causal paths.

Tree: In computer science, a tree is a directed acyclic graph in which every node has only 1 directed edge pointing to it, save for the starting node (the “root” node). While edges extend from the root node, no edges point to the root node.

In addition to understanding the parts of a DAG, it’s also important to recognize 1 component that it lacks: a cycle. The “acyclic” in directed acyclic graph refers to the absence of cycles or closed loops in these graphs. In other words, when starting at 1 node in a DAG and traversing subsequent nodes and edges, it’s impossible to return to the starting node.

In graph theory (the study of graphs), several concepts or processes are often applied when working with directed acyclic graphs. They include:

• Topological sort
• Transitive closure
• Transitive reduction

A topological sort, also known as a topological ordering, is a way of organizing the nodes of a DAG in a linear fashion so that the nodes that point to other nodes appear first and successors don't appear before their predecessors. Topological sort algorithms can produce such sequences based on DAGs.¹

In complicated graphs, it can be challenging to recognize which nodes can be “reachable” by directed paths from other nodes. In transitive closure, such indirect links between nodes are identified and diagrammed.

For example, if a graph has a directed edge linking node A and node B and another directed edge linking node B and node C, that would indicate that A and C are linked indirectly. A transitive closure would result in a new directed edge connecting A to C—now the shortest path between these two nodes—in addition to the original directed edges between A and B and B and C. As with topological sorting, algorithms can be used for transitive closure calculations.

Transitive reduction can be considered the opposite of transitive closure. In the context of a directed graph, the transitive reduction of the graph has the same number of nodes as the original graph and the pairs of nodes that are reachable are the same. However, the number of edges in the transitive reduction of the graph are minimized.

Consider, for example, an original graph that includes a directed edge linking node A to node C, and a sequence of directed edges linking node A to node B and node B to node C. A transitive reduction of that graph would exclude the edge between A and C while maintaining the edges between the larger set of variables: A and B and B and C.

In other words, the longest path between A and C in the original graph is included in the new graph, while the path with just 1 edge is eliminated. 

Directed acyclic graphs figure prominently in computer science through a host of use cases:

• Data processing
• Neural networks
• Causal inference in machine learning
• Robotics
• Compiler design
• Blockchain

DAGs help data engineers define data structures and achieve optimization in data flows. Data orchestration platforms such as Apache Airflow, for example, use DAGs (defined in Python scripts) to define data processing tasks and specify their order of execution in data pipelines and workflows.

In cases when multiple DAGs depend on each other, orchestration tools can create dependency graphs to clarify those relationships.² Data observability platforms can be used in conjunction with data orchestration platforms to identify and address data pipeline issues.

The acceleration of the adoption of generative artificial intelligence applications, which rely on data access, has amplified the importance of data pipelines and DAGs in the modern technology landscape.

A neural network is a machine learning program that decides in a manner similar to the human brain by using processes that mimic the way biological neurons work together to make observations and arrive at conclusions. DAGs are used to map neural networks and can be especially helpful in the visualization of deep neural networks with multiple layers.

DAGs can play a role in efforts to “teach” AI models to recognize causal relationships through causal inference. Causal inference is a paradigm for determining causal effects and often employs DAGs. For example, DAGs can help detect “confounders,” which are variables that distort or obscure real causation. AI enhanced with causal inference is emerging as a tool in epidemiology in particular, with the potential to aid researchers in their investigations of disease determinants.³

Researchers have proposed using a DAG- and large language model-based structural planning method to improve the performance of dual-arm robots. In the proposed framework, an LLM generates a DAG that represents complex tasks as subtasks, with edges indicating the dependencies among them. In the framework, this information is used to help determine motion planning and coordination between the 2 arms for task execution.⁴

DAGs are used to optimize the design of compilers, which are programs that convert programming languages (source code) into instructions for computers (machine code). For instance, a DAG can help identify common subexpressions that can be eliminated to improve efficiency.

A blockchain based on a DAG demonstrates better performance than conventional blockchains, according to researchers. A DAG-based blockchain can allow the parallel processing of transactions, thereby increasing the rate of transactions processed in a certain period and enabling more flexibility and scalability. Such improvements can have applications in areas such as supply chain management and access controls for Internet-of-Things networks.^{5, 6}