DAG (directed acyclic graph)

A directed acyclic graph, or DAG, is the formal data structure that Tree projects are built on. The term comes from graph theory and describes a specific shape: a graph where edges have direction (one node leads to another) and where no cycles are possible (you can't trace a path from a node back to itself).

Tree as a DAG

Tree's data model is a DAG by design. Nodes represent work. Edges represent dependencies, pointing from prerequisites to the work they unlock. The acyclic constraint means a node can't depend on itself, directly or transitively. If task A depends on task B, then B cannot depend on A.

Why the constraint matters

The DAG structure is what makes Tree's mechanics possible.

• Topological sort (the algorithm that computes the available tier) requires a DAG; it doesn't work on graphs with cycles.
• Critical path analysis requires a DAG.
• Forward and backward traversal both depend on the acyclic constraint.

Cycles are blocked

This is also why Tree refuses to create cycles. When a user tries to add an edge that would form a cycle (task A depends on task B, and the user tries to make B depend on A), Tree blocks the operation. The constraint isn't arbitrary; it's what allows the rest of the data model to work.

What the constraint costs

The cost of the DAG constraint is that some real-world relationships can't be represented. Mutual dependencies, iterative loops, and bidirectional reviews don't fit the model and have to be broken into intermediate nodes. This is sometimes inconvenient. It's also usually a sign that the work isn't decomposed enough.

Related

• Node
• Edge
• How cycles are prevented