Skip to main content

TopologicalSort

Topological ordering of directed acyclic graphs (DAGs).

A topological sort produces a linear ordering of vertices such that for every directed edge u → v, vertex u appears before v in the ordering. This is only possible when the graph has no directed cycles.

Both implementations return nil when a cycle is detected, signaling that no valid topological order exists.

When to use each variant

Function Strategy Best when
sort DFS post-order General purpose
kahn BFS / in-degree queue You also need the in-degree counts, or want a more predictable iteration order

All functions accept either callback form for GetNeighbors — see GraphUtil for details.

Example graph

-- Task dependency graph (directed, acyclic):
--  compile ──→ link ──→ test ──→ deploy
--              ↑
--  assets ─────┘

local deps = {
    compile  = {},
    assets   = {},
    link     = {"compile", "assets"},
    test     = {"link"},
    deploy   = {"test"},
}

local allTasks = {"compile", "assets", "link", "test", "deploy"}

local function getNeighbors(v)
    return deps[v]         -- outgoing edges (v must come before its neighbors)
end

Functions​

sort​

directed
</>
TopologicalSort.sort(
allVertices: {V},
getNeighbors: GetNeighbors<V>
) → {V}?

Returns a topological ordering of allVertices using iterative DFS post-order. Each vertex is appended once all its outgoing edges are explored, yielding reverse-topological order; the list is flipped once at the end so dependencies land before dependents.

Returns nil if the graph contains a directed cycle (no valid ordering exists). 

local order = TopologicalSort.sort(allTasks, getNeighbors)
-- e.g. { "compile", "assets", "link", "test", "deploy" }

Time complexity: O(V + E)

kahn​

directed
</>
TopologicalSort.kahn(
allVertices: {V},
getNeighbors: GetNeighbors<V>
) → {V}?

Returns a topological ordering using Kahn's algorithm (BFS / in-degree queue). Vertices with zero in-degree are enqueued first; as each is removed, the in-degrees of its successors are decremented and any newly zero-degree successors are enqueued.

Returns nil if the graph contains a directed cycle (not all vertices could be processed). 

local order = TopologicalSort.kahn(allTasks, getNeighbors)
-- e.g. { "compile", "assets", "link", "test", "deploy" }
Stable ordering

Kahn's approach processes vertices in FIFO order within the same in-degree level, which can produce a more predictable ordering than DFS for graphs with multiple valid topological sorts.

Time complexity: O(V + E)

Show raw api
{
    "functions": [
        {
            "name": "sort",
            "desc": "Returns a topological ordering of `allVertices` using iterative\n**DFS post-order**.  Each vertex is appended once all its outgoing edges are\nexplored, yielding reverse-topological order; the list is flipped once at the\nend so dependencies land before dependents.\n\nReturns `nil` if the graph contains a directed cycle (no valid ordering\nexists).\n\n```lua\nlocal order = TopologicalSort.sort(allTasks, getNeighbors)\n-- e.g. { \"compile\", \"assets\", \"link\", \"test\", \"deploy\" }\n```\n\n*Time complexity:* `O(V + E)`",
            "params": [
                {
                    "name": "allVertices",
                    "desc": "",
                    "lua_type": "{ V }"
                },
                {
                    "name": "getNeighbors",
                    "desc": "",
                    "lua_type": "GetNeighbors<V>"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ V }?\n"
                }
            ],
            "function_type": "static",
            "tags": [
                "directed"
            ],
            "source": {
                "line": 76,
                "path": "lib/graphutil/src/TopologicalSort.luau"
            }
        },
        {
            "name": "kahn",
            "desc": "Returns a topological ordering using **Kahn's algorithm** (BFS / in-degree\nqueue).  Vertices with zero in-degree are enqueued first; as each is\nremoved, the in-degrees of its successors are decremented and any newly\nzero-degree successors are enqueued.\n\nReturns `nil` if the graph contains a directed cycle (not all vertices\ncould be processed).\n\n```lua\nlocal order = TopologicalSort.kahn(allTasks, getNeighbors)\n-- e.g. { \"compile\", \"assets\", \"link\", \"test\", \"deploy\" }\n```\n\n:::tip Stable ordering\nKahn's approach processes vertices in FIFO order within the same in-degree\nlevel, which can produce a more predictable ordering than DFS for graphs\nwith multiple valid topological sorts.\n:::\n\n*Time complexity:* `O(V + E)`",
            "params": [
                {
                    "name": "allVertices",
                    "desc": "",
                    "lua_type": "{ V }"
                },
                {
                    "name": "getNeighbors",
                    "desc": "",
                    "lua_type": "GetNeighbors<V>"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{ V }?\n"
                }
            ],
            "function_type": "static",
            "tags": [
                "directed"
            ],
            "source": {
                "line": 153,
                "path": "lib/graphutil/src/TopologicalSort.luau"
            }
        }
    ],
    "properties": [],
    "types": [],
    "name": "TopologicalSort",
    "desc": "Topological ordering of directed acyclic graphs (DAGs).\n\nA topological sort produces a linear ordering of vertices such that for\nevery directed edge `u → v`, vertex `u` appears before `v` in the\nordering.  This is only possible when the graph has **no directed cycles**.\n\nBoth implementations return `nil` when a cycle is detected, signaling that\nno valid topological order exists.\n\n### When to use each variant\n\n| Function | Strategy | Best when |\n| --- | --- | --- |\n| [`sort`](#sort) | DFS post-order | General purpose |\n| [`kahn`](#kahn) | BFS / in-degree queue | You also need the in-degree counts, or want a more predictable iteration order |\n\nAll functions accept either callback form for `GetNeighbors` — see\n[GraphUtil](/api/GraphUtil) for details.\n\n### Example graph\n\n```lua\n-- Task dependency graph (directed, acyclic):\n--  compile ──→ link ──→ test ──→ deploy\n--              ↑\n--  assets ─────┘\n\nlocal deps = {\n    compile  = {},\n    assets   = {},\n    link     = {\"compile\", \"assets\"},\n    test     = {\"link\"},\n    deploy   = {\"test\"},\n}\n\nlocal allTasks = {\"compile\", \"assets\", \"link\", \"test\", \"deploy\"}\n\nlocal function getNeighbors(v)\n    return deps[v]         -- outgoing edges (v must come before its neighbors)\nend\n```",
    "source": {
        "line": 50,
        "path": "lib/graphutil/src/TopologicalSort.luau"
    }
}