= Directed acyclic graph
{c}
{wiki}
A <Directed acyclic graph> is a <directed graph> with no <directed cycle>: following its <directed edges> can never return to the starting <vertex>. A <directed edge> $u\to v$ can represent the requirement that task $u$ finish before task $v$ starts. A <directed path> then records a chain of prerequisites. The essential prerequisite for <topological sorting> is that these requirements contain no circular dependency. For finite <directed graphs>, this is equivalent to the existence of a <topological order>. https://live.ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/d9265b3b33d238ff914b0223ac8e7628_MIT6_006S20_r10.pdf[MIT, Introduction to Algorithms, Recitation 10, p. 3: directed acyclic graphs and topological sorts]{ref}
Consider an invented publishing workflow with five tasks: $A$ drafts the text, $B$ draws a figure, $C$ reviews the text, $D$ lays out the text and figure, and $E$ publishes the result. Its <directed edges> are $A\to C$, $A\to D$, $B\to D$, $C\to E$, and $D\to E$. Reviewing needs the draft; layout needs both the draft and figure; publication needs both review and layout. The drawing below encodes only these prerequisites, with no measured durations or resource constraints.
\Image[/topological-task-dependency-orders.png]
{title=Five toy publishing tasks and all five valid topological orders}
The <Directed acyclic graph> leaves room for choice: $A$ and $B$ can occur in either order, and after both are complete, $C$ and $D$ can occur in either order. Task $C$ may even precede $B$, since the review does not need the figure. A <topological order> turns these local prerequisites into a complete executable list while retaining this freedom. It supplies a feasible sequential plan; task durations, available workers, and earliest finishing times require additional information.
Back to article page
