DAGs & Topological Sorting

Directed acyclic graph (DAG)

These are graphs that do not have cycles.
Hence they can be topologically sorted.
When graph is arranged from the starting node it moves in one direction.
These graphs do not visit their predecessors; only successors.

Topological sorting

DAGs come up a lot when we speak about topological sorting.

Topological sorting is a really cool technique for solving a myriad of problems.

• 1. Prerequsites for courses in college
• 2. CICD pipelines where one stage needs to run before the other.
• 3. Data engineering pipelines
• 4. Git commit log graph

The pattern that comes up for DAGs are that all nodes depend forward.

Any problem that has this pattern can be solved using topological sorting.

Notice that all arrows move in one direction.
None of the arrows depends backwards.
All nodes depend forward.