From Requirements to a Directed Graph
Scheduling instructions are often expressed as statements such as “prepare the data before fitting the model” or “complete both reviews before publication.” A directed graph makes the direction of each requirement explicit. It can reveal whether the requirements contradict one another, and it gives a systematic way to list the schedules that satisfy them.
Throughout, a directed graph is finite and has no loops or repeated arcs. Its vertices represent tasks. An arc \(uv\), directed from \(u\) to \(v\), means that \(u\) must occur before \(v\). We model tasks as indivisible items in a schedule: a schedule is a single ordering of all tasks, and the precedence requirements are the only restrictions considered. Durations, resource limits and tasks that can overlap are not represented by this model.
The requirement recorded by an arc is direct. A sequence of arcs \(u\to w_1\to\cdots\to v\) also implies that \(u\) must occur before \(v\), even when there is no arc \(uv\). Such a sequence is a directed path from \(u\) to \(v\). Thus the graph records both the stated requirements and, through its directed paths, their logical consequences.
A directed cycle is a sequence of distinct vertices \(v_1,\dots,v_k\), with \(k\ge 1\), whose arcs run \(v_1\to v_2\to\cdots\to v_k\to v_1\). A directed acyclic graph, or DAG, is a directed graph with no directed cycle. A topological order of a digraph is an ordering of its vertices in which every arc points from an earlier vertex to a later one. By the definitions, a topological order of a precedence digraph is exactly a valid schedule.
When Are the Requirements Consistent?
Proof. First suppose there is a valid schedule, and suppose for contradiction that the digraph contains a directed cycle \(v_1\to v_2\to\cdots\to v_k\to v_1\). Let \(p(v)\) be the position of task \(v\) in the schedule. Each arc requires its initial vertex to appear earlier, so \(p(v_1)<p(v_2)<\cdots<p(v_k)<p(v_1)\). By transitivity of the strict order \(<\), this implies \(p(v_1)<p(v_1)\), which is impossible. Therefore a digraph with a valid schedule has no directed cycle.
Conversely, suppose the digraph is acyclic. We prove by induction on \(n=|V|\) that it has a topological order. If \(n=0\), the empty ordering is a topological order. Now take \(n\ge1\). There must be a vertex with no incoming arc. Indeed, if every vertex had an incoming arc, start at any vertex and repeatedly follow an incoming arc backwards. Since the graph has finitely many vertices, some vertex would repeat; the arcs between its two appearances would give a directed cycle, contrary to acyclicity. Choose a vertex \(v\) with no incoming arc and delete it and its incident arcs. The remaining digraph is acyclic, since any cycle remaining in it would also have been a cycle in the original graph. By induction it has a topological order. Put \(v\) first, followed by that order. No arc enters \(v\), and every other arc is respected by the order of the remaining vertices, so the resulting ordering is topological. The two definitions show it is a valid schedule. Finally, valid schedules and topological orders are the same orderings because both require each arc’s initial vertex to appear before its terminal vertex. \(\square\)
The proof also explains the practical test: repeatedly choose a task with no unmet prerequisites, schedule it, and remove it and its outgoing arcs. If all tasks are removed, the removal order is a valid schedule. If tasks remain but none has zero incoming arcs among the remaining tasks, the remaining digraph contains a directed cycle, so the requirements cannot all be met.
Building and Reading a Precedence Model
Make one vertex for every task that must be scheduled. Include tasks with no precedence requirements.
For “\(u\) must happen before \(v\),” draw the arc \(u\to v\). An arc points from the prerequisite to the task that depends on it.
A directed cycle means each task on that cycle must precede the next, eventually requiring a task to precede itself.
At each stage, select any remaining vertex with no incoming arc from a remaining vertex. Different choices can produce different valid schedules.
When translating written instructions, record only what they actually require. If both \(A\to B\) and \(B\to C\) are present, then \(A\) already precedes \(C\) by implication; adding \(A\to C\) is valid but redundant. Conversely, an instruction that two tasks are both required before a third task gives two arcs, not an order between the first two.
Worked Example: Two Independent Preparations
Tasks \(A\) and \(B\) are independent preparations. Both must be completed before \(C\), and \(C\) must be completed before \(D\). The precedence digraph is the simple directed graph with \(V=\{A,B,C,D\}\) and \(E=\{AC,BC,CD\}\), where each listed pair denotes an arc in the displayed direction.
Initially, \(A\) and \(B\) have no incoming arcs, so either can come first. If \(A\) is chosen first, \(B\) is still the only other available task: \(C\) still has incoming arc \(BC\), and \(D\) still has incoming arc \(CD\). After \(B\), task \(C\) is available; after \(C\), task \(D\) is available. This gives \(A,B,C,D\). Choosing \(B\) first gives \(B,A,C,D\) by the same incoming-arc check.
There are no other schedules: \(A\) and \(B\) must both precede \(C\), and \(C\) must precede \(D\). Thus the only freedom is the order of \(A\) and \(B\). Check: in \(A,B,C,D\), the positions satisfy \(p(A)=1<p(C)=3\), \(p(B)=2<p(C)=3\), and \(p(C)=3<p(D)=4\). In \(B,A,C,D\), they satisfy \(p(A)=2<p(C)=3\), \(p(B)=1<p(C)=3\), and \(p(C)=3<p(D)=4\). Every arc is respected in both lists.
Worked Example: Enumerating Every Schedule
Suppose tasks \(P\) and \(Q\) begin a process; \(R\) requires both \(P\) and \(Q\), while \(S\) requires \(Q\). The digraph is \(V=\{P,Q,R,S\}\), \(E=\{PR,QR,QS\}\). We enumerate the schedules by listing the available tasks at each choice. “Available” means that the task has no incoming arc from any task not yet scheduled.
If \(P\) is first, \(Q\) is the only available next task: \(R\) still requires \(Q\), and \(S\) still requires \(Q\). Once \(P,Q\) have been scheduled, both \(R\) and \(S\) are available, and either order is permitted. This gives \(P,Q,R,S\) and \(P,Q,S,R\).
If \(Q\) is first, both \(P\) and \(S\) are available. Choosing \(P\) next makes \(R\) and \(S\) available, giving \(Q,P,R,S\) or \(Q,P,S,R\). Choosing \(S\) next leaves \(P\) as the only available task, followed by \(R\), giving \(Q,S,P,R\). The complete list is therefore \(P,Q,R,S\), \(P,Q,S,R\), \(Q,P,R,S\), \(Q,P,S,R\), and \(Q,S,P,R\).
Check: each listed ordering places \(P\) before \(R\), \(Q\) before \(R\), and \(Q\) before \(S\). To verify completeness, the first task must be either \(P\) or \(Q\), since \(R\) and \(S\) each have an incoming arc. The branches after these two first choices were exhausted above: two schedules start with \(P\), and three start with \(Q\). Hence there are exactly \(2+3=5\) schedules.
Worked Example: A Cycle Exposes a Contradiction
Three stages are described by the requirements “\(A\) before \(B\),” “\(B\) before \(C\),” and “\(C\) before \(A\).” Their digraph has \(V=\{A,B,C\}\) and \(E=\{AB,BC,CA\}\). These arcs form the directed cycle \(A\to B\to C\to A\).
Attempting source removal confirms the problem. Initially, \(A\) has incoming arc \(CA\), \(B\) has incoming arc \(AB\), and \(C\) has incoming arc \(BC\). No vertex has zero incoming arcs, so no task can be placed first. Equivalently, a proposed schedule would require \(p(A)<p(B)<p(C)<p(A)\), which is impossible.
Check: the theorem applies because this is a finite precedence digraph, and it has a directed cycle. It therefore has no valid schedule. The contradiction is in the requirements themselves; changing the order of attempted scheduling cannot resolve it. At least one requirement must be revised or removed.
Common Modeling Errors and Why the Model Helps
Reversing an arc. If \(A\) must happen before \(B\), the arc is \(A\to B\), not \(B\to A\). For example, take \(V=\{A,B\}\), \(E=\{AB\}\). The schedule \(B,A\) is a wrong answer: its positions are \(p(B)=1\) and \(p(A)=2\), so it violates the arc condition \(p(A)<p(B)\). The correction is to schedule \(A,B\), for which \(p(A)=1<p(B)=2\).
Inventing an order between independent tasks. In the first example, there is no requirement that \(A\) precede \(B\) or that \(B\) precede \(A\). Both schedules are valid. A graph records required order, not a preferred order, so adding an arc without a reason can incorrectly discard valid schedules.
Confusing a long dependency with a direct requirement. If \(A\to B\) and \(B\to C\), then \(A\) must precede \(C\), even without an arc \(A\to C\). This follows because any valid schedule has \(p(A)<p(B)\) and \(p(B)<p(C)\), hence \(p(A)<p(C)\). A directed path therefore captures an implied dependency.
Precedence digraphs are useful because they separate the logical structure of a scheduling problem from a particular schedule. A cycle gives a concise certificate of inconsistency. When there is no cycle, topological orders describe all schedules permitted by the stated constraints. This is especially useful when tasks have several prerequisites: the graph makes it possible to check consistency before committing to a sequence, and to see exactly where there is flexibility.
Check Your Understanding
For each question, state the vertices and arcs when a precedence model is involved, and justify your conclusion from the definitions.
- Tasks \(X,Y,Z\) have requirements \(X\) before \(Z\) and \(Y\) before \(Z\). List every valid schedule.
- For \(V=\{A,B,C,D\}\) and \(E=\{AB,AC,BD,CD\}\), enumerate all valid schedules.
- Explain why a directed cycle in a precedence digraph rules out every valid schedule.
- Give a precedence digraph with a directed path from \(A\) to \(C\) but no arc \(AC\). What order does the path imply?
- Suppose source removal leaves some vertices, but none has zero incoming arcs among the remaining vertices. What can be concluded, and why?