Order dependencies and detect deadlock in the model
Remove ready tasks to construct a topological order or expose a blocking cycle.
By the end: distinguish a valid dependency order from a timed resource schedule.
Earlier must precede later
A directed acyclic graph, abbreviated DAG, has no directed cycle. A topological order lists all vertices so that every edge goes from an earlier entry to a later one. Here an edge means the source task must finish before the destination may begin. This is a constraint on order, not a duration.
A cycle makes such an order impossible. If A precedes B, B precedes C, and C precedes A, the requirements would force A to precede itself. Conversely, any finite DAG has a zero-indegree vertex. Following incoming edges forever without finding one would repeat a vertex and produce a cycle.
A ready task has no unfinished prerequisite
Take six tasks A through F. The complete directed edge set is A to B, A to C, B to D, C to D, D to E, and D to F. Every arrow means that its source task must finish before its destination may begin. Think of A as preparing materials, B and C as separate checks, D as assembling their results, and E and F as later uses of that assembly. The task names supply a possible interpretation, but the arrows supply the actual mathematical restrictions. The graph contains no task durations and no statement about how many people are available.
At the start, A has no incoming edge. B and C each have one, D has two, and E and F each have one. These indegrees count immediate prerequisites, not minutes of waiting. A is the only ready task because it is the only task with zero unfinished prerequisites. Emitting A means placing it next in the proposed completion order. For the ordering calculation, remove A and its outgoing edges. B and C then each have zero remaining indegree, so both become eligible. Their original indegrees have not changed as historical facts; the algorithm is tracking the remaining constraints.
D needs both B and C
The arrows are exactly A→B, A→C, B→D, C→D, D→E, D→F. Each means finish before. B and C become ready after A; D still needs both of them. Spatial separation carries no timing information.
Select B before C under the lesson's alphabetical rule. Removing B's outgoing edge reduces D's remaining indegree from two to one. D is still not ready, because C has not yet been emitted. This is an all-prerequisites rule. One finished predecessor out of two is insufficient. A drawing in which D is close to B does not weaken the missing requirement from C. After C is emitted, its edge to D disappears from the remaining calculation and D's indegree reaches zero. Only then may D enter the ready set. This intermediate count prevents the fork and join from becoming a mistaken either-or choice.
A valid order also respects indirect prerequisites. A has no direct edge to D, but A must precede B and C, and both must precede D. Thus A must precede D. This follows by chaining the meaning of must finish before. Adding a direct A-to-D edge would repeat an already implied ordering requirement without changing which complete orders are legal. It would change an indegree count and the edge-removal bookkeeping, so every count must still use the chosen edge set consistently. The underlying prerequisite logic can contain an implied relation even when no separate edge records that relation.
Why can a finite graph without a directed cycle always supply a ready vertex? Suppose every remaining task had an unfinished predecessor. Start anywhere and repeatedly choose one such predecessor. With finitely many tasks, eventually a task repeats. The edges followed then describe a closed chain of prerequisites, which is a directed cycle. Therefore a cycle-free remainder cannot have every task blocked. At least one zero-indegree task must exist. This argument uses finiteness, not a visual impression that arrows point mostly rightward. Rearranging the same graph cannot create or remove a ready task.
Removing B alone does not make D ready
Emitted prefix
Remaining indegrees B, C, D, E, F
Ready next
None
1, 1, 2, 1, 1
A
A
0, 0, 2, 1, 1
B, C
A, B
Removed, 0, 1, 1, 1
C
A, B, C
Removed, removed, 0, 1, 1
D
A, B, C, D
Removed, removed, removed, 0, 0
E, F
Only unfinished prerequisites contribute to remaining indegree. D waits after B because C→D remains. The original graph is unchanged as a record; the calculation progressively removes satisfied constraints.
Removing a ready task preserves the possibility of ordering the rest. No remaining arrow enters that task, so placing it next violates no remaining prerequisite. Its outgoing arrows merely require their destinations to come later, which they will. If the remaining graph has no cycle, repeat the same argument. This constructs a full order one vertex at a time. If a task has no edges at all, it is ready immediately and still belongs in the complete order. Ignoring it would omit required work, even though it constrains none of the other tasks.
Remove a ready task
Kahn's algorithm repeatedly selects a remaining zero-indegree vertex, emits it, and removes its outgoing edges from the remaining constraints. More than one task may be ready; alphabetical selection is only our deterministic tie-breaker. Removing a vertex cannot introduce a new cycle.
If all vertices are emitted, the result is a topological order. If work remains but nothing is ready, the remaining graph contains a cycle. Some blocked vertices can lie downstream of the cycle rather than on it. Do not call every blocked task a member of the cycle.
A complete order can be checked edge by edge
For the six-task graph, alphabetical ready-task selection emits A, B, C, D, E, F. Immediately before each selection, the ready sets are {A}, {B, C}, {C}, {D}, {E, F}, and {F}. This is not a fixed alphabetical scan that ignores prerequisites. C remains available after B finishes because D still needs C. Later, both E and F become ready at once. The rule chooses the alphabetically first among the tasks currently eligible, then recomputes eligibility. A smaller letter that is still blocked has no right to enter before a larger ready letter.
The result is easy to audit without reproducing the selection procedure. Give each task its position in the proposed list. For every original edge, check that the source position is smaller than the destination position. In A, B, C, D, E, F, the B-to-D edge goes from position two to position four, and C-to-D goes from three to four. Both pass. The same check applies to all six edges. Also verify that every vertex occurs exactly once. A list can respect every edge it happens to mention while still omitting an isolated or downstream task.
One reversed edge rejects an otherwise complete list
Candidate order
Position of C / D
All edges point forward?
A, B, C, D, E, F
3 / 4
Yes
A, B, D, C, E, F
4 / 3
No: C→D is reversed
A, C, B, D, F, E
2 / 4
Yes
Positions are counted from one. Every vertex appears once in each candidate. Only the middle candidate places D before its required predecessor C. The other two lists pass all six original arrows.
The list A, B, D, C, E, F fails even though every task appears once. D has position three while C has position four, reversing the required C-to-D edge. That one edge is enough to reject the entire candidate. It is unnecessary to argue about all possible execution histories. In contrast, A, C, B, D, F, E passes every edge check. Swapping B and C preserves legality because neither depends on the other. Swapping E and F also preserves legality. The original fork-and-join graph therefore has four complete orders, not one uniquely correct alphabetical answer.
Multiple ready choices explain where that freedom comes from. If B and C are both ready, neither can have a remaining prerequisite path to the other. Such a path would give the later vertex an unfinished incoming requirement somewhere along that path. Either ready task can therefore be emitted next while preserving some completion of the DAG. In the base example the two choices for B and C combine with two choices for E and F, yielding four orders. This multiplication works here because D separates the two independent pairs; it is not a formula for counting every DAG's orders.
Uniqueness has a direct procedural test. If exactly one task is ready at every step until all tasks are emitted, every choice is forced and the order is unique. If two tasks are ready at some step of a DAG, choosing either first permits a different valid completion. For a contrasting six-task graph, replace the edge set with A to B, B to C, C to D, D to E, and E to F. Each step exposes just one successor. Its only topological order is A, B, C, D, E, F. The same list can thus describe either a forced result or one selected among alternatives.
A chain forces every choice
This separate directed graph has only AB, BC, CD, DE, EF, all oriented in alphabetical order. It has the same alphabetical output as the fork-and-join example, but no freedom to swap either pair. The complete order alone does not identify the original graph.
The distinction matters when reviewing an algorithm's output. Two systems can return different valid lists without disagreeing about a single prerequisite. Conversely, identical lists do not prove that their underlying dependency graphs are identical. The chain graph and the fork-and-join graph both permit the alphabetical list, but the chain forbids orders that the fork permits. An order is evidence that a candidate respects the constraints. It is not a complete representation of all constraints or all allowed alternatives. Keep the original edge records available when interpreting what a selected list actually establishes.
Inspect the graph and its result
Repeatedly select a ready task
Complete order: A, B, C, D, E, F. Blocked: None.
Ready before choice
Emit
A
A
B, C
B
C
C
D
D
E, F
E
F
F
An order is valid only if all vertices are emitted. This is not a timed resource schedule.
Presets replace all dependencies. Among ready tasks the alphabetically first is chosen. Highlighted vertices were emitted; blocked vertices may be on a cycle or downstream of one.
After finishing
Newly eligible tasks
A
B and C
Both B and C
D
D
E and F
The graph leaves the relative order of B and C unspecified.
Separate a cyclic cause from its blocked consequences
Begin with the model's Fork and join preset and trace the reduction of D's remaining indegree. After A, B and C are ready. After B, only C is ready. After C, D is ready. These states distinguish waiting for a second prerequisite from a genuine deadlock. A task can be blocked temporarily in a perfectly acyclic graph. The calculation only reports a cyclic obstruction when unfinished tasks remain and the ready set is empty. The initial absence of D from the ready set is therefore expected behavior, not evidence that the model contains a cycle.
Now select Add E-before-B cycle. This adds the single edge E to B to the original six edges. A still has no prerequisite, so it can be emitted. C then becomes ready and can also be emitted. B still waits for E. D waits for B, and E waits for D. The cycle is B to D to E to B. No task on that cycle can become the first finished member, because each requires another member first. The resulting emitted prefix is A, C. It is valid as a partial ordering, but it is not a complete topological order.
F waits downstream of the cycle
Adding E→B to the six fork-and-join arrows creates the solid cycle B→D→E→B. A and C can be emitted; F is blocked by D but has no return path into the cycle. Dashed edges are other original prerequisites, not deleted permissions.
F remains blocked too, but it is not part of that cycle. Its only incoming edge is D to F, and it has no outgoing edge. It cannot return to B, D, or E by any directed route. The complete blocked set is B, D, E, F; the cyclic set is only B, D, E. A blocked report identifies tasks whose prerequisites cannot all be removed. It does not identify the smallest set of contradictory requirements. Treating all four blocked tasks as cyclic would wrongly attribute a circular prerequisite to F, which merely depends on work that the cycle prevents.
The earlier strong-component idea makes this distinction precise. B, D, and E can each reach the other two, so they form one strongly connected component containing a cycle. F forms its own singleton component downstream. A and C form separate singleton components outside the blocked remainder. Combining B, D, and E into one group would show a one-way dependency from that group to F. Grouping can summarize the obstruction, but it does not make the tasks inside executable. Their internal circular requirements still need explanation or a justified correction to the model before the original tasks can finish.
Try the Two initial tasks preset next. Its vertices are A, B, C, D, with edges A to C, B to C, and C to D. A and B are ready initially. The model emits A first, then B, then C, then D. C cannot be emitted after A alone, because B-to-C remains. Compare this with the cyclic preset: the unfinished prerequisite of C can actually be removed by doing B. Waiting and impossibility can look similar in one snapshot. The complete ready/emit trace shows whether ordinary progress resolves the wait or leaves an empty ready set with work remaining.
Two ready tasks still form an all-prerequisites join
This preset has exactly A→C, B→C, C→D. A and B are ready initially. C becomes ready only after both have been emitted, yielding alphabetical order A, B, C, D without any cycle.
If the circular preset represents real work, inspect the meaning of E-to-B before changing it. Perhaps B needs a draft that can exist before E's final approval, rather than needing E itself finished. That would require a revised task model, not an unexplained deletion of the inconvenient edge. If all three requirements genuinely mean finish before, no amount of alphabetical rearrangement repairs the cycle. The demonstration diagnoses inconsistency among stated prerequisites. It neither proves that a real organization is deadlocked nor tells you which requirement is factually mistaken. Those judgments need evidence about the work behind the arrows.
Ordering is not scheduling
Two ready tasks may run in parallel only if the real system has the necessary workers, machines, and compatibility. A topological list supplies neither start times nor resource allocation. Many lists can satisfy the same dependencies. Durations and resource limits define an additional scheduling problem.
A cycle can also reveal a modeling error rather than a physical impossibility. Perhaps a requirement applies to a later version of an artifact, or means may use rather than must finish before. Change the model only when the real semantics justify it. Arbitrarily deleting an edge does not resolve a genuine circular prerequisite.
Add time only when the scheduling assumptions are explicit
To see what dependency order leaves unresolved, add durations in a paper example using the original fork-and-join graph. Let A take two hours, B four, C one, D two, and E and F one each. Assume tasks cannot be interrupted, every prerequisite must finish before its successor starts, and enough workers are available to run all ready tasks together. These are extra assumptions, not values supplied by the model's controls. Start A at hour zero. It finishes at hour two, making B and C eligible together. Their durations, rather than their alphabetical order, now determine when D can begin.
B runs from hour two to hour six, while C runs from hour two to hour three. D must wait until hour six because it needs both results. Starting at hour three would violate B-to-D even though C is finished. D runs until hour eight, after which E and F can both run until hour nine. The elapsed completion time is nine hours. Adding every task duration gives eleven hours, but that sum double-counts periods when different workers act simultaneously. A topological list alone gives neither number. The time calculation requires durations and an explicit assumption about parallel resources.
Enough workers allow a nine-hour completion
Using the original six prerequisite arrows, B and C can overlap after A, and E and F can overlap after D. Durations are A=2, B=4, C=1, D=2, E=1, F=1 hours. D waits for the later predecessor B. Bar widths and start positions encode hours exactly.
The longest prerequisite chain explains the nine-hour lower bound here. A, B, D, E must occur sequentially, and their durations add to nine hours. A, B, D, F gives the same total. No schedule can finish all tasks in less than nine hours under these assumptions, because one worker per chain task cannot overlap a successor with its unfinished prerequisite. The schedule just described reaches the bound, so it is optimal for this constructed unlimited-worker case. A longest-chain bound can remain useful with scarce workers, but it no longer guarantees that the bound is attainable.
Now keep the same graph and durations but allow only one worker, who can perform one task at a time. The alphabetical order produces A during hours zero to two, B during two to six, C during six to seven, D during seven to nine, E during nine to ten, and F during ten to eleven. Every arrow still points forward in the order. The total is eleven hours because none of the tasks overlap. The dependency graph did not change; the resource assumption did. This contrast shows why calling two tasks ready does not establish that they will execute together.
Other resource restrictions require more than counting workers. B and C might need the same testing machine even when two people are available. That conflict is not necessarily a permanent prerequisite from B to C or C to B. Either order might be allowed, provided their use of the machine does not overlap. Adding B-to-C would force one of those alternatives and remove the other from the model. A scheduling model must distinguish required precedence from a choice made to avoid sharing a scarce resource. Otherwise a convenient chosen schedule can be mistaken for a rule inherent in the work.
One worker changes elapsed time without changing arrows
The same tasks and durations take eleven hours when a single worker performs the alphabetical order without overlap. This is a constructed scheduling comparison outside the dependency controls. The graph permits overlap between B and C; the resource assumption forbids it.
Finally, prerequisite evidence can be uncertain or change over time. A task marked finished may need revision, and a later task may depend on a specific approved version rather than any earlier completion. The static DAG assumes stable task identities and stable finish-before requirements for the calculation. Its full output certifies a legal order for those assumptions. The cyclic output certifies that no complete order satisfies all the stated requirements simultaneously. Neither output measures actual completion time, predicts worker behavior, or validates an approval rule. Those claims need the additional records that the graph deliberately omits.
Exercises
Identify downstream blocking
Edges are A to B, B to C, C to B, and C to D. After emitting A, which vertices remain blocked? Which are actually on the cycle?
Hint
D needs the cycle to finish but has no edge back to it.
Worked answer
Vertex
Reason
A
Initially ready, can be emitted
B and C
Mutual prerequisite cycle
D
Waits downstream of C
Blocked is a broader category than cyclic. Thick blue edges are the named selection; all original connections remain visible.
B, C, and D remain blocked. B and C form the directed cycle. D is downstream, not on the cycle. A partial output is not a topological order of the entire original graph.
A schedule claim
Two tasks B and C are ready after A. One worker can do only one task at a time. Does the DAG prove B and C can execute simultaneously?
Hint
The edges encode prerequisites, not workers.
Worked answer
Constraint
What it supplies
Dependencies
Permitted relative order
One worker
No simultaneous execution
Task durations
Time required by each task
Do not silently add infinite resource capacity.
No. The DAG permits either relative order, but the one-worker resource constraint prevents overlap. Add durations and resource availability to produce a feasible schedule. A topological order remains useful but is not sufficient.
Sources and further reading
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Directed reachability, strong components, DAGs, and topological orders. The lesson uses zero-indegree removal rather than the reference implementation's reverse-postorder method.