DAG: Directed Acyclic graphs in computer sciences
A Directed Acyclic Graph, or DAG, is a kind of graph used to represents relationships between elements of a system.
What are DAGs?
A Directed Acyclic Graph, or DAG, is a kind of graph used to represents relationships between elements of a system.
It is directed, which means that the relationship between elements are represented by directed edges (it has a direction).
It is also acyclic, that is to say there are no cycles or loop in the graph. No path will start from a node and go back to this node.
I personally have used DAGs for years without knowing that there was an appropriate term for them.
Why are there useful?
They are often used to represent hierarchical structures. In computer sciences there are three usages that I want to talk about.
Dependency management
When you use a package manager, your dependencies may themselves require other elements. The package manager will build a DAG to determine all required dependencies and install them.
If my project declare a dependency to react, it will also need all packages listed in react own package.json
IT humor
Analyse data flow
DAG can be used to model the flow of data in the different part/processing step of a system. It helps identify the core components as well as the unused one.
If the DAG is associated with duration measure it can also help identify the bottlenecks and help take actions to resolve them.
Scheduled task execution
A DAG can be used to represent dependencies between tasks. It enable :
- to automatically execute one or many processes as soon as all the requirements are met,
- to execute multiple tasks in parallel.
Example of a task dependency definition I use for tests, the DAG allows to represent the links between tasks.
And in case a task fail, we can use the DAG to retry this single task with the same parameters to help fix it.
A platform that use DAG to “programmatically author, schedule and monitor workflows” is Apache Airflow. A very useful tool that is currently a source of inspiration for me.
Post-scriptum
As the G in DAG stands for Graph, it is more relevant to display them as images than as text representations. Two languages/tools I use for that purpose are:
- dot language / graphviz that I first encountered something like 13 years ago,
- mermaid that I discovered a few weeks ago.
I will probably continue to use dot language to output graph in software and mermaid when I need one for a documentation or an article.
That’s it, thanks for reading!
Feel free to comment or reach me if you have any questions or constructive criticism to make!