GraphUtil

Show Private

A library of generic, graph-agnostic algorithms. Describe your graph with a few callbacks — no bespoke data structure required — and run any algorithm over any representation (adjacency lists, spatial grids, implicit neighbour functions, …).

Submodules

Module	Purpose
BFS	Breadth-first traversal & unweighted shortest paths
DFS	Depth-first traversal & spanning trees
Dijkstra	Weighted shortest paths (non-negative) & cost-ordered traversal
AStar	Heuristic-guided weighted shortest path
BellmanFord	Weighted shortest paths with negative edges & cycle detection
MST	Minimum spanning trees (Prim / Kruskal)
TopologicalSort	Linear ordering of a DAG (DFS / Kahn)
Connectivity	Reachability, components, cycles, bipartite, SCCs

Shared callbacks

Algorithms are driven by callbacks rather than a fixed structure. See each type page for the full signature and worked examples: GetNeighbors (required by every algorithm), GetWeight (weighted algorithms), and GetHeuristic (A*). Path-finders return a PathResult; MST returns Edge lists.

Directed vs. undirected

Because your callbacks define the edges, most algorithms work on directed and undirected graphs alike. Every function carries a directed and/or undirected tag showing which graph kinds it supports — a function tagged with only one (e.g. TopologicalSort is directed-only, MST is undirected-only) gives wrong or meaningless results on the other kind.

local GraphUtil = require(Packages.GraphUtil)

local adjacency = {
    A = { "B", "C" },
    B = { "A", "D" },
    C = { "A", "D" },
    D = { "B", "C" },
}

local result = GraphUtil.BFS.shortestPath("A", "D", function(v)
    return adjacency[v]
end)
-- result.path == { "A", "B", "D" }

Types

GetNeighborsArray

</>

type GetNeighborsArray = (vertex: V) → {V}

A callback that returns the neighbours of vertex as an array. The simpler of the two GetNeighbors forms — return whatever's convenient and let the algorithm collect it.

local adjacencyList = {
    A = { "B", "C" },
    B = { "A", "D" },
    C = { "A", "D" },
    D = { "B", "C" },
}

local function getNeighbors(vertex: string): { string }
    -- Return an empty array (never nil) for vertices with no neighbours,
    -- so the algorithms can index the result safely.
    return adjacencyList[vertex] or {}
end

GetNeighborsIterator

</>

type GetNeighborsIterator = (vertex: V) → () → V?

A callback that returns a stateful iterator over the neighbours of vertex. More allocation-efficient than GetNeighborsArray — no intermediate table is built — at the cost of managing the iteration state yourself.

local adjacencyList = {
    A = { "B", "C" },
    B = { "A", "D" },
    C = { "A", "D" },
    D = { "B", "C" },
}

local function getNeighbors(vertex: string): () -> string?
    local neighbours = adjacencyList[vertex] or {}
    local i = 0
    return function(): string?
        i += 1
        return neighbours[i]
    end
end

GetNeighbors

</>

type GetNeighbors = GetNeighborsArray | GetNeighborsIterator

Either form of neighbour callback — GetNeighborsArray or GetNeighborsIterator. Accepted by every algorithm in this library and normalised internally, so you can pick whichever form is most natural for your graph representation.

local function arrayForm(vertex: string): { string }
    return adjacencyList[vertex] or {}
end

local ok = BFS.shortestPath("A", "D", arrayForm) -- both forms work

GetWeight

</>

type GetWeight = (

from: V,

to: V

) → number

Returns the non-negative weight of the directed edge from from to to. Required by every weighted algorithm (Dijkstra, AStar, BellmanFord, MST).

local edgeWeights = {
    A = { B = 2, C = 3 },
    B = { A = 2, D = 1 },
    C = { A = 3, D = 5 },
    D = { B = 1, C = 5 },
}

local function getWeight(from: string, to: string): number
    return edgeWeights[from][to]
end

GetHeuristic

</>

type GetHeuristic = (

vertex: V,

goal: V

) → number

An admissible heuristic: an estimate of the cost from vertex to goal that must never overestimate the true cost. Required by AStar; an inadmissible heuristic makes A* fast but no longer guaranteed optimal.

-- Straight-line distance is admissible for movement costs that are
-- never cheaper than a direct line (e.g. grid movement).
local function heuristic(vertex: { Position: Vector3 }, goal: { Position: Vector3 }): number
    return (vertex.Position - goal.Position).Magnitude
end

ShouldStop

</>

type ShouldStop = (

vertex: V,

cost: number

) → boolean

An optional cooperative cancellation predicate. Search functions that accept one call it once per expanded vertex — after the goal check, before that vertex's neighbours are relaxed — and abort the search the moment it returns true. Path-finders then return nil (indistinguishable from an unreachable goal); Dijkstra.distances returns the partial result accumulated so far.

Because these algorithms run synchronously to completion, this predicate is the only way to bound an open-ended search. cost is the accumulated cost of vertex — weighted distance for Dijkstra / AStar, hop-count for BFS — so you can stop on a budget; most callers ignore both arguments and stop on a wall-clock deadline.

-- Give up after half a second of searching.
local deadline = os.clock() + 0.5
local result = AStar.shortestPath(a, b, getNeighbors, getWeight, heuristic, function()
    return os.clock() > deadline
end)

-- Or stop once the search cost exceeds a budget of 500.
local result = Dijkstra.shortestPath(a, b, getNeighbors, getWeight, function(_vertex, cost)
    return cost > 500
end)

KIterator

</>

type KIterator = () → K?

A stateless-to-the-caller iterator that yields one value per call, returning nil once exhausted. This is the single-value form returned by BFS.toIterator and DFS.toIterator; for the (vertex, cost) pair form see KVIterator.

The nil-at-exhaustion convention is what makes these iterators directly usable in a plain for loop.

local iter: Types.KIterator<string> = BFS.toIterator(start, getNeighbors)

for vertex in iter do
    print(vertex)
end

KVIterator

</>

type KVIterator = () → (

K?,

V?

)

A stateless-to-the-caller iterator that yields a pair of values per call, returning (nil, nil) once exhausted. This is the (vertex, cost) form returned by Dijkstra.toIterator; for the single-value form see KIterator.

Write the type arguments without ? — the alias applies the optionality itself, since every slot is nil once the traversal is exhausted: KVIterator<string, number> is () -> (string?, number?).

local iter: Types.KVIterator<string, number> = Dijkstra.toIterator(start, getNeighbors, getWeight)

for vertex, cost in iter do
    print(vertex, cost)
end

PathResult

</>

interface PathResult {

path: {V}--

Ordered sequence of vertices from start to goal (both inclusive).

cost: number--

Total accumulated edge-weight along the path. For unweighted algorithms this is the hop-count.

}

The result of a path-finding algorithm — returned by BFS.shortestPath, Dijkstra.shortestPath, AStar.shortestPath, and BellmanFord.shortestPath.

local result = Dijkstra.shortestPath("A", "D", getNeighbors, getWeight)
if result then
    print(result.path) -- { "A", "B", "D" }
    print(result.cost) -- 3
end

Edge

</>

interface Edge {

from: V--

The vertex the edge starts at.

to: V--

The vertex the edge ends at.

weight: number--

The edge's weight.

}

An edge in a spanning or search tree, as produced by MST.kruskal and MST.prim.

local edges = MST.kruskal(vertices, getNeighbors, getWeight)
for _, edge in edges do
    print(`{edge.from} -> {edge.to} ({edge.weight})`)
end

Properties

BFS

</>

GraphUtil.BFS: BFS

Breadth-first search — traversal and unweighted (fewest-hop) shortest paths.

DFS

</>

GraphUtil.DFS: DFS

Depth-first search — traversal, reachability sets, and spanning trees.

Dijkstra

</>

GraphUtil.Dijkstra: Dijkstra

Weighted shortest paths (non-negative edges) and cost-ordered traversal.

AStar

</>

GraphUtil.AStar: AStar

Heuristic-guided weighted shortest path — faster than Dijkstra with a good heuristic.

BellmanFord

</>

GraphUtil.BellmanFord: BellmanFord

Weighted shortest paths that tolerate negative edges, with negative-cycle detection.

MST

</>

GraphUtil.MST: MST

Minimum spanning trees via Prim's and Kruskal's algorithms.

TopologicalSort

</>

GraphUtil.TopologicalSort: TopologicalSort

Linear ordering of a directed acyclic graph via DFS post-order or Kahn's algorithm.

Connectivity

</>

GraphUtil.Connectivity: Connectivity

Reachability, connected components, cycle detection, bipartiteness, and SCCs.