Topological Sort Calculator

About Topological Sort Calculator

The Topological Sort Calculator computes a linear ordering of the vertices of a directed acyclic graph (DAG) such that every directed edge from u to v places u before v. Enter your graph as an edge list or adjacency list and the tool returns the topological order using Kahn's algorithm or DFS post-order, detects cycles (with the exact cycle path), groups tasks into parallel-execution layers, counts the number of valid orderings, and animates each step on an interactive graph.

What is a topological sort?

Given a directed graph G = (V, E), a topological sort (or topological ordering) is a linear arrangement v₁, v₂, …, vₙ of its vertices such that for every directed edge (u → v), u appears before v in the arrangement. A topological ordering exists if and only if the graph has no directed cycles — that is, the graph is a DAG. The ordering is rarely unique: a graph can have many valid topological sorts when several vertices have in-degree zero at the same time.

Algorithms used by this calculator

Kahn's algorithm (BFS-based, 1962)

Kahn's algorithm is the most intuitive topological sort. At every step it picks a vertex with in-degree zero (no incoming edges), appends it to the output, and "removes" it from the graph by decrementing the in-degree of each of its successors. When several vertices have in-degree zero, tie-breaking can use a min-heap (giving the lexicographically smallest ordering) or a FIFO queue (giving the insertion order). Kahn's algorithm runs in O(|V| + |E|) time and doubles as a cycle detector: if any vertex still has in-degree > 0 after the queue empties, the graph has a cycle.

DFS post-order (Tarjan, 1976)

The DFS algorithm runs depth-first search, and whenever a vertex finishes (i.e. all its successors have been fully explored) it is pushed onto a stack. Reversing the stack at the end yields a valid topological order. Cycle detection is natural: encountering a vertex that is still in progress (marked GRAY) means a back edge has been found, so the graph is not a DAG. DFS post-order also runs in O(|V| + |E|) time.

Parallel-execution layers

A layered view of a DAG partitions its vertices into levels such that every edge goes from a lower-numbered level to a higher one. Vertices in the same layer are independent of each other, so they can be executed in parallel. The number of layers equals the length of the longest path plus one — this is the critical path of the DAG, the minimum number of sequential rounds needed to finish all tasks even with unlimited parallelism. This calculator produces the layer view automatically whenever the input is a DAG.

Cycle detection

If the graph contains a directed cycle, no topological sort is possible. Our calculator reports the exact cycle path (e.g. A → B → C → A) and highlights the cycle edges in red on the visualization. Removing any single edge on the cycle is sufficient to restore acyclicity.

Input formats

Edge list

Write each directed edge as source -> target, separated by commas or newlines. Accepted arrow variants: ->, →, =>, -->, :. You can also chain edges: A -> B -> C is shorthand for A->B and B->C. Vertex labels can be letters, digits, underscores, dashes, and dots.

Adjacency list

Write each vertex, a colon, and its direct successors (vertices it points to). A vertex with no successors still needs its line, such as D:.

How to use this calculator

1. Pick a format: Toggle between edge list and adjacency list with the radio buttons.
2. Enter the graph: Paste your data or click one of the quick examples (dressing order, course prerequisites, build targets, a graph with a cycle, and more).
3. Choose an algorithm: Kahn's lexicographic for a unique, reproducible order; insertion order to preserve input ordering; DFS post-order for the classic depth-first method; or Show all to see every ordering side-by-side.
4. Click "Sort Topologically": The ordering, cycle detection, layer view, critical path length, total number of valid orderings, and an interactive graph appear below.
5. Explore: Press Play to watch each vertex get emitted one step at a time. The in-degree badges update live. Drag any node to rearrange the layout.

Real-world applications

Build systems and compilers

Tools like make, Bazel, Gradle, and npm topologically sort their build targets so each target is compiled only after all its dependencies. A cycle in the dependency graph is usually reported as a fatal error — the build system cannot decide where to start.

Task scheduling

Project managers use DAGs to capture task dependencies. The topological sort gives a valid execution order, and the layer view gives the minimum number of rounds under unlimited parallelism. The longest chain is the critical path that determines project duration.

Course prerequisite planning

A university course catalog is a DAG: edges are prerequisite relationships. A topological order is a valid study plan, and the layers tell students which sets of courses they can take in parallel during each semester.

Spreadsheet recalculation

When a cell changes, a spreadsheet must recompute every downstream cell in dependency order — a topological sort of the cell-dependency DAG. Circular references (cycles) are rejected by the application.

Package managers and plugin loaders

Apt, pip, Homebrew, Maven and countless plugin frameworks resolve install or load order by topologically sorting their dependency DAGs.

Symbol resolution and instruction scheduling

Compilers use topological sort to order declarations, and CPUs use data-dependency DAGs to schedule instructions in the reorder buffer without violating data hazards.

Counting topological orderings

For a DAG with n vertices, the number of distinct valid topological orderings can range from 1 (for a totally ordered chain) to n! (for the edgeless graph). Computing the exact count is #P-complete in general, but for graphs up to 16 vertices this calculator enumerates them using a bitmask dynamic-programming formulation: f(S) = Σ f(S ∪ {v}) over all v ∉ S whose predecessors are all in S.

Complexity and performance

• Time: Both Kahn's algorithm and DFS post-order run in O(|V| + |E|) — linear in the size of the graph.
• Space: O(|V|) for in-degree tracking and the output order, plus O(|V| + |E|) for the adjacency structure.
• Cycle detection: Built into both algorithms. Kahn's detects cycles when |output| < |V|; DFS detects them when a back edge (GRAY neighbor) is found.
• Limits in this tool: up to 80 vertices and 800 edges for interactive visualization. Counting orderings caps at 16 vertices.

Frequently asked questions

What is a topological sort?

A topological sort of a directed acyclic graph is a linear ordering of its vertices such that every directed edge from u to v places u before v. It represents a valid order in which to process tasks that respect their dependencies.

Which algorithm does this calculator use?

The calculator runs both Kahn's algorithm and DFS post-order. Kahn's algorithm repeatedly removes a vertex with in-degree zero and decrements in-degrees of its successors. DFS post-order runs depth-first search and reverses the finish order. Both run in O(|V| + |E|) time.

What if my graph has a cycle?

A graph with a directed cycle has no topological sort. The calculator detects the cycle, highlights it in red on the visualization, and reports the exact cycle path so you can see which edges to remove to make the graph a DAG.

What is the lexicographically smallest topological order?

When many topological orderings are valid, the lexicographically smallest one is obtained by always picking the alphabetically smallest vertex whose in-degree is zero at each step. The default Kahn's mode of this calculator returns this unique ordering, which is stable and easy to reproduce.

What is the layer or level view?

The layer view groups vertices by the longest path length from any source. Vertices in the same layer have no dependency between them, so they can run in parallel. The number of layers equals the longest dependency chain plus one and gives the minimum number of parallel rounds needed to finish all tasks.

Can a graph have many valid topological orderings?

Yes. If at any step Kahn's algorithm has multiple vertices with in-degree zero, any of them can be picked next. This calculator counts the exact number of distinct topological orderings for graphs up to 16 vertices.

What is the difference between Kahn's algorithm and DFS post-order?

Kahn's works top-down: it repeatedly picks sources (in-degree 0) and emits them first. DFS post-order works bottom-up: it finishes sinks first and prepends them to the order. Both are O(|V| + |E|) and produce valid topological orderings, but typically different ones. Kahn's is easier to parallelize and to adapt for lexicographic ordering; DFS is easier to combine with other DFS-based analyses such as strongly connected components.

What is the maximum graph size this tool supports?

The calculator supports up to 80 vertices and 800 edges. Counting the total number of valid topological orderings is capped at 16 vertices because the problem is #P-complete and the state space grows as 2ⁿ. The interactive visualization and algorithm animation scale smoothly up to the full size.

Further Reading

• Topological sorting — Wikipedia
• Directed acyclic graph — Wikipedia
• Depth-first search — Wikipedia
• Critical path method — Wikipedia
• Strongly connected component — Wikipedia