Calculator
Example data
| Scenario | Nodes | Edges (dependency) | One valid order |
|---|---|---|---|
| Course prerequisites | A, B, C, D, E, F | A→C, B→C, C→D, D→E, B→F | A → B → C → D → E → F |
| Project tasks | Design, Build, Test, Deploy | Design→Build, Build→Test, Test→Deploy | Design → Build → Test → Deploy |
| Cycle example | X, Y, Z | X→Y, Y→Z, Z→X | No ordering |
Tip: For task scheduling, make edges point from prerequisite to dependent.
Method used
Topological sorting orders nodes so every edge u→v places u before v. The key quantity is indegree:
indegree(v) = number of incoming edges into v
Kahn’s method repeatedly selects any node with indegree = 0, outputs it, and decreases indegrees of its outgoing neighbors. If nodes remain with positive indegree, the graph contains a cycle, so no ordering exists.
DFS method outputs nodes in reverse finishing time (reverse postorder). Encountering a back-edge during DFS indicates a cycle.
How to use this calculator
- Enter nodes (optional). Use spaces, commas, or new lines.
- Enter directed edges, one per line, like A->B.
- Choose an algorithm and optional settings.
- Press Submit to see the ordering above the form.
- Use CSV or PDF buttons to export your result.
FAQs
1) What is a topological sort?
A topological sort is an ordering of nodes in a directed graph where every dependency edge points forward in the order. It only exists when the graph has no directed cycles.
2) What does an edge A→B mean here?
It means A must come before B. For prerequisites, point edges from prerequisite to dependent course or task.
3) Why do I see “no valid ordering”?
That message appears when a directed cycle is detected. Cycles create circular dependencies, so no ordering can satisfy all edges at the same time.
4) Are there multiple correct answers?
Yes. Many graphs have several valid topological orders. If you enable random tie breaks, the queue method may output different valid orders on repeated runs.
5) When should I use Kahn vs DFS?
Kahn is great for step-by-step queue tracing using indegrees. DFS is compact and useful for cycle detection via back-edges, returning a reverse postorder when acyclic.
6) What does “Show steps” display?
It shows the chosen node at each iteration and how the queue changes. For the queue method, it also lists indegree updates for affected neighbors.
7) Why is enumeration limited to small graphs?
The number of valid orders can grow extremely fast, even for moderate sizes. Limiting nodes prevents large runtimes and keeps results readable.
8) What input formats are accepted for edges?
You can use A->B, A B, A,B, or A=>B, one edge per line. Blank lines are ignored and comments can start with # or //.