Topological Sort Challenge Generator
Given tasks where some must happen before others, in what order can they run? Usually there are many valid answers, and how many is a better measure of the constraint than the dependency count is — three dependencies that all point at one task barely constrain anything, and three arranged in a chain leave exactly one order. This counts every valid order by enumeration, so that number is exact.
What this generator does
Generates dependencies that only ever run forward through a shuffled order, so the graph is acyclic by construction. It reports one valid order, the total number of valid orders, and which tasks have no prerequisites at all.
How to use this tool
- Choose how many tasks and how densely they depend on each other.
- Work out an order that respects every dependency.
- Compare with the order shown.
- Look at how many valid orders exist, and which tasks could start first.
Understanding the controls
- How many tasks
- Between 3 and 8. Every valid order is enumerated, which is factorial in the worst case.
- Dependency density (%)
- More dependencies leave fewer valid orders. At zero every ordering works; at a hundred there is exactly one.
- Seed
- Reproduces the same dependency set exactly.
Common use cases
- Build-order and pipeline-ordering exercises
- Showing that dependency count is a poor measure of how constrained a plan is
- Test instances for a topological sort implementation
- Teaching why a cycle makes ordering impossible
- Reproducing the same dependency set from a seed
How this generator works
Because dependencies only ever point forward through a hidden order, the graph cannot contain a cycle and at least one valid ordering is guaranteed. The check verifies every dependency is respected by the stated order, re-counts the valid orders by enumeration, and confirms the startable-task list.
Randomness and fairness
Which dependencies exist is random; the acyclicity is a property of the construction. Seeded sets reproduce and are therefore explicitly not cryptographically secure, and unseeded ones use the browser's cryptographically secure generator.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Eight tasks is the ceiling, because counting every valid order is factorial work.
- Dependencies are hard constraints with no durations, so this orders tasks rather than scheduling them.
- Cyclic dependency sets are never generated, though the checker would catch one.
- Task names come from a fixed list.
- Dependency sets are discarded on leaving; seed one to set it as an exercise.
Privacy and your data
Dependencies and orders are computed in your browser. Nothing is transmitted or kept.
Related generators
- DAG GeneratorDirected acyclic graphs where the absence of cycles is structural rather than checked afterwards — for testing schedulers, build systems and topological sorts.
- Critical Path CalculatorWorks out which tasks decide your finish date, and how much slack everything else has.
- Graph Traversal GeneratorThe same graph visited breadth-first and depth-first side by side, with the hop count each node sits at.
- Makespan Scheduling Problem GeneratorJobs across identical machines, scheduled longest-first, with two lower bounds that often prove the schedule optimal.