Topological Sort Calculator

Introduction: how this topological sort calculator orders directed graphs

This topological sort calculator reads a 5×5 adjacency matrix and turns it into a dependency-safe order for the vertices in a directed graph. Each row describes outgoing edges from one vertex to the others, so the matrix is a compact way to encode prerequisites, build steps, or any other “must happen before” relationship. When the graph is acyclic, the output is a linear order in which every arrow points forward. In the matrix, the entry marks a directed edge from vertex to vertex .

Topological sorting depends on incoming-edge counts. For each column , the indegree can be summarized as , which is just a compact way of saying “count the 1s that point into .” The calculator does that count before it starts removing vertices, so the first displayed order always matches the matrix you entered rather than an inferred guess.

The algorithm behind the page is Kahn's algorithm, and its running time is $O(V+E)$ for a graph with $V$ vertices and $E$ edges. It maintains a queue of vertices with no incoming edges. Each time the algorithm removes a vertex, it treats the outgoing edges from that vertex as deleted, which can expose new zero-indegree vertices. The working set is the zero-indegree queue .

This page breaks ties by choosing the smallest-numbered available vertex first, so rerunning the same matrix gives the same displayed order. That convention is useful when you are comparing a dependency list before and after a single change. If two vertices are simultaneously ready, the tie-break determines which one appears earlier, but it never creates a dependency that is not already present in the graph.

If the queue becomes empty before all five vertices are written out, the graph still has edges left and therefore contains a cycle. A self-loop is just a one-vertex cycle, so a 1 on the diagonal is enough to make a clean topological order impossible. The calculator reports that situation instead of pretending there is a partial schedule that satisfies every arrow. In other words, the output is either a full order for a DAG or a clear warning that the directed graph cannot be ordered as written.

Because the matrix is fixed at five vertices, the calculator is best used as a compact DAG checker rather than a general graph editor. It is handy for small build graphs, course prerequisite lists, and workflow diagrams when you want a quick answer about ordering without switching tools. If your source graph uses a different numbering scheme, renumber it first so row and column labels line up with the matrix.

Worked example: sorting a four-vertex dependency graph step by step

This worked example uses a four-vertex dependency graph and follows the same logic the calculator applies to a 5×5 matrix. The matrix encodes the edges 1→2, 2→3, 2→4, and 3→4. Vertex 1 has indegree zero, so it is the only legal starting point. Once 1 is removed, vertex 2 becomes available. Removing 2 then frees vertex 3, and after 3 is placed, vertex 4 is the only remaining vertex. The resulting order is (1, 2, 3, 4), and every arrow in the graph points from an earlier position to a later one.

Mathematically, the topological ordering respects the partial order defined by reachability. If we denote the reachability relation as when a path from to exists, the topological order is any linear extension of this partial order. Such extensions are guaranteed to exist only for acyclic graphs. The existence of a cycle implies , forming a contradiction.

This calculator checks for cycles implicitly: if fewer than five vertices are output, a cycle prevented removal of all edges. The result section will warn about cycles. That warning is especially helpful when the graph is almost acyclic except for one back edge or one self-loop that keeps a vertex from ever reaching indegree zero.

Applications of topological sorting in build pipelines and prerequisites

Topological sorting is useful whenever one item must wait for another. Build systems apply it to compile libraries before the files that depend on them, and package managers rely on the same idea to install prerequisites before dependents. When the dependency list is acyclic, a topological order gives a legal execution sequence instead of a guess.

The same pattern appears in project plans, course schedules, content pipelines, and data workflows. If a task graph is clean, the order tells you what can happen now and what must wait. If a cycle appears, the graph is telling you that one prerequisite chain loops back on itself and cannot be satisfied as written. A topological sort calculator is useful here because it exposes the structure of the graph directly rather than hiding it behind a longer planning tool.

In algorithm design, topological ordering is a building block for shortest paths in DAGs, dynamic programming over dependency graphs, and critical-path style analyses. Because edges always point forward, each vertex can be processed after its predecessors have been resolved, which keeps the computation simple and linear in the size of the graph. The same ordering also makes it easier to reason about what changed when a single new arrow is added.

This calculator is especially helpful when you want to inspect a small graph quickly. Enter the matrix, check the order, and if the output stops short, look for a reversed edge or a self-loop. A tiny edit can change the result from a clean sequence to an impossible cycle. If several vertices are available at once, the smallest-numbered rule is useful for debugging because it removes randomness from the process.

Summing up, topological sorting turns dependency information into a concrete sequence, and this calculator gives you a compact way to watch that process on a fixed-size graph. It is a quick way to confirm that the structure you sketched on paper is actually a directed acyclic graph before you rely on the order elsewhere.

How to use this topological sort calculator for adjacency matrices

To use this topological sort calculator, enter the graph exactly as a 5×5 adjacency matrix and read the result as an ordering of the five labeled vertices. The row-and-column layout matters: row , column means “an edge from to .” A matrix entry of 1 means the arrow exists, and 0 means it does not.

1. Label the vertices first. Decide which real tasks, courses, modules, or milestones will correspond to vertices 1 through 5, then keep that numbering consistent while you fill the matrix.
2. Mark only true dependencies. Enter 1 where one vertex must precede another and 0 everywhere else. If you put a 1 on the diagonal, you are telling the calculator that a vertex depends on itself, which creates a cycle immediately.
3. Check the direction before you submit. In a prerequisite list, the prerequisite should point to the item that depends on it. If you reverse that arrow, the topological order will describe the opposite relationship from the one you intended.
4. Read the result as a valid schedule, not as a ranking. The output is a dependency-safe order. If the result contains all five vertices, every arrow in the matrix points forward in that order. If it stops early, revisit the graph for a back edge, a self-loop, or another cycle.

If you are comparing two similar matrices, rerun the calculator after each change so you can see exactly which edge altered the ordering. One added arrow can move a vertex later in the sequence, while one removed arrow can make a previously blocked vertex available earlier. That is the main practical value of a topological sort calculator: it shows the consequence of each dependency clearly.

How this topological order is assembled from a 5×5 matrix

This topological sort calculator does not evaluate a numeric formula. Instead, it repeatedly counts indegrees, builds a queue of zero-indegree vertices, and removes the smallest available vertex each time. Each chosen vertex is appended to the result, and every edge leaving that vertex is removed from consideration so that any newly freed neighbors can enter the queue. The visible order is therefore the result of repeated graph pruning, not of a score or a weight calculation.

Because the page always works with five vertices, the output table lists positions 1 through 5 whenever a full order exists. If more than one vertex is available at the same step, the smallest-numbered available vertex is chosen first. That tie-break keeps the result stable when you rerun the same matrix or compare two nearly identical dependency graphs. In practical terms, it means the calculator is deterministic even when the underlying graph allows several valid topological orders.

If the queue empties before all vertices have been emitted, the remaining edges must be part of a cycle. At that point the calculator cannot extend the order any further, and the result panel reports the failure instead of inventing a partial solution. This is why a topological sort is such a good cycle test: a DAG eventually exhausts every zero-indegree vertex, while a directed cycle always keeps at least one dependency trapped.

L = empty list that will contain the ordered nodes
S = set of nodes with no incoming edge
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each edge (n, m) in E do
        remove edge (n, m) from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L

Limitations and assumptions for this topological sort calculator on DAGs

This topological sort calculator is designed for a single 5×5 binary adjacency matrix. It does not handle weighted edges, multiple edge labels, or graphs larger than five vertices, and it assumes the matrix uses row-to-column direction consistently. A misplaced 1 can change the meaning of the graph entirely, so double-check the row and column labels before you submit the matrix.

The result depends on an accurate graph and on the absence of directed cycles. If a cycle is present, no ordering can satisfy every arrow, so the calculator must stop short of a full list. The displayed order is one valid topological sort chosen by the page's smallest-available-vertex rule, not the only possible order. Different tie-break rules could produce a different but still correct order for the same acyclic graph.

Use the output as a quick check against the source dependency list, build graph, or course prerequisite table you started with. If that source changes, rerun the calculator; a single new edge, removed edge, or self-loop can turn a clean DAG into a cycle or can unlock a different valid order. If you are working from a diagram rather than a matrix, translate it carefully so the arrow directions match the row and column positions in the form.