Connectivity

Graph connectivity queries: reachability, components, cycle detection, bipartiteness, and strongly connected components.

Most functions come in two flavours depending on whether the graph is directed or undirected. Check each function's directed / undirected tags to confirm which it operates on.

allVertices parameter

Several functions require allVertices: { V } — the complete list of vertices in the graph. This is needed to find disconnected components and to seed multi-source traversals.

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

Example graphs used in the docs below

-- Undirected: one component A─B─C─D, plus a separate component E─F
--  A ── B ── C ── D        E ── F
local undirAdj = {
    A = {"B"}, B = {"A","C"}, C = {"B","D"}, D = {"C"},
    E = {"F"}, F = {"E"},
}

-- Directed: a cycle A→B→C→A, plus an acyclic edge D→E
--  A ──→ B ──→ C          D ──→ E
--  ▲           │
--  └───────────┘
local dirAdj = {
    A = {"B"}, B = {"C"}, C = {"A"},
    D = {"E"}, E = {},
}

Functions

isConnected

directedundirected

</>

Connectivity.isConnected(

start: V,

goal: V,

getNeighbors: GetNeighbors<V>

) → boolean

Returns true if goal is reachable from start by following edges (directed or undirected depending on your getNeighbors callback).

This is a single-target BFS and short-circuits as soon as goal is found.

print(Connectivity.isConnected("A", "D", getNeighbors)) -- true
print(Connectivity.isConnected("A", "E", getNeighbors)) -- false (different component)

Time complexity: O(V + E) worst case, often much better.

components

undirected

</>

Connectivity.components(

allVertices: {V},

getNeighbors: GetNeighbors<V>

) → {{V}}

Finds all connected components of an undirected graph and returns them as an array of vertex arrays. Each inner array is one component; vertices within a component are in BFS discovery order.

Pass a bidirectional getNeighbors (each undirected edge appears in both directions) so that every connected group is fully explored.

local comps = Connectivity.components({"A","B","C","D","E","F"}, getNeighbors)
-- { {"A","B","C","D"}, {"E","F"} }  (order may vary)

Time complexity: O(V + E)

hasDirectedCycle

directed

</>

Connectivity.hasDirectedCycle(

allVertices: {V},

getNeighbors: GetNeighbors<V>

) → boolean

Returns true if the directed graph contains at least one cycle.

-- dirAdj: A→B→C→A forms a cycle
print(Connectivity.hasDirectedCycle({"A","B","C","D","E"}, getNeighbors)) -- true

Directed graphs only

For undirected cycle detection use hasUndirectedCycle.

:::info Internals Uses iterative DFS with a three-colour marking scheme:

• white (0) — unvisited
• grey (1) — on the current DFS path (in the recursion stack)
• black (2) — fully processed

A back edge (grey → grey) indicates a cycle. :::

Time complexity: O(V + E)

hasUndirectedCycle

undirected

</>

Connectivity.hasUndirectedCycle(

allVertices: {V},

getNeighbors: GetNeighbors<V>

) → boolean

Returns true if the undirected graph contains at least one cycle, using BFS with parent tracking. An edge to an already-visited non-parent vertex indicates a cycle.

-- A-B-C-A forms an undirected cycle
print(Connectivity.hasUndirectedCycle({"A","B","C"}, getNeighbors)) -- true

Undirected graphs only

For directed cycle detection use hasDirectedCycle.

Time complexity: O(V + E)

isBipartite

undirected

</>

Connectivity.isBipartite(

start: V,

getNeighbors: GetNeighbors<V>

) → boolean

Returns true if the graph component reachable from start is bipartite — its vertices can be divided into two groups such that every edge connects a vertex in one group to a vertex in the other.

Uses BFS two-colouring: colour start with 0 and alternate 0/1 for each discovered vertex. If a neighbour already has the same colour as the current vertex, the graph is not bipartite.

-- A-B-C-D square (even cycle) → bipartite
-- A-B-C triangle (odd cycle)   → not bipartite
print(Connectivity.isBipartite("A", getNeighbors))

Per-component

This only checks the component reachable from start. Call once per component (e.g. using components) to check the full graph.

Time complexity: O(V + E)

stronglyConnectedComponents

directed

</>

Connectivity.stronglyConnectedComponents(

allVertices: {V},

getNeighbors: GetNeighbors<V>

) → {{V}}

Finds all Strongly Connected Components (SCCs) of a directed graph using Kosaraju's algorithm and returns them as an array of vertex arrays. Within each SCC, every vertex can reach every other vertex.

Kosaraju's requires traversing the graph and its reverse. Because the library's callback design doesn't expose a reverse-edge callback, this function builds the reverse adjacency internally during the first DFS pass.

-- A→B→C→A  (one SCC), D→E (two singleton SCCs)
local sccs = Connectivity.stronglyConnectedComponents(
    {"A","B","C","D","E"}, getNeighbors
)
-- { {"A","B","C"}, {"D"}, {"E"} }  (order may vary)

Time complexity: O(V + E)