Blog - Miscellaneous

When to use Directed Acyclic Graph (DAG) in programming?

Written by: Jane D, on 2012-10-29

In mathematics and computer science, a directed acyclic graph, is a directed graph with no directed cycles. DAG doesn’t really have to do with programming. It’s more about problem solving.

- DAG comes in handy when detecting deadlocks as they show the dependencies amongst a set of resources and processes. Deadlocks happen when a cycle is detected.

- Some programming languages describe systems of values that are related to each other by a directed acyclic graph. When one value changes, all the successors are recalculated. Each value is evaluated as a function of its predecessors in the DAG.

- Once we have the DAG in memory, we can write algorithms to calculate the maximum execution time of the entire set make sure the computations are evaluated in the correct order.

- Code may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation will allow the compiler to perform common sub expression elimination in a more efficient way.

- In computational geometry, some algorithms maintain a history DAG representing features of some geometric construction that have been replaced by later finer-scale features.