Directed Acyclic Graph (DAG)
2 min readAug 3, 2020
DAG is a mix of linked lists, Trees, and graphs. Not only it has a swag acronym, but a cool implementation, If you use git in your day to day life, committing your changes, tagging with ease then you need to know how DAG has made your life easier.
In a DAG, causal relationships are represented by arrows between the variables, pointing from cause to effect.
Let me get into some theory before I give you it’s python implementation.
DAG has few properties you need to know about :
- Each node has a unique value. Interior nodes always represent the operators, Exterior nodes can be identifiers, constants.
- From its name we can understand that its Acyclic, meaning it does not have any cycles in it.
- It has Directed edges. A directed edge (or “arrow”) from one node to another represents a relationship between those two nodes.
- It’s used to optimize Basic Blocks.
- Avoids re-computation of common sub-expressions by checking if there exists a node with the same value and creates a node only if the values are unique.
- Assignment operations performed only when its necessary.
- Unidirectional, DAG must not contain a feedback loop where a variable causes itself.
- For a DAG to be complete, the shared cause of any two variables in the DAG must be included.
Time For Code
I have used the networkx module to implement the DAG Since they are well known for Graph implementation.
I have also added a function that helps you in visualizing the graph.
The above code must generate an image similar to this
References:
