xmake-graph-module

core.base.graph — Graph Data Structure

core.base.graph is xmake's general-purpose graph module. It implements both directed and undirected graphs with topological sort and cycle detection. Use it when you need to model dependencies / relationships in a custom script but don't want to run them as async jobs (for that, use async.jobgraph, which wraps this).

Must be imported:

import("core.base.graph")

1. Create a graph

local dag = graph.new(true)    -- directed (DAG)
local ug  = graph.new(false)   -- undirected

2. Vertices and edges

g:add_vertex("a")
g:add_vertex("b")
g:add_vertex("c")

g:add_edge("a", "b")           -- a → b  (directed)
g:add_edge("b", "c")

print(g:has_vertex("a"))       -- true
print(g:has_edge("a", "b"))    -- true
print(#g:vertices())           -- 3

Vertices can be any value (strings, numbers, tables — anything you can use as a table key).

Shorthand

add_edge auto-adds endpoints:

local g = graph.new(true)
g:add_edge("a", "b")           -- "a" and "b" added automatically
g:add_edge("b", "c")

Inspect

for _, v in ipairs(g:vertices()) do print(v) end
for _, e in ipairs(g:edges()) do
    print(e:from(), "->", e:to())
end
for _, e in ipairs(g:adjacent_edges("a")) do
    print(e:to())              -- outgoing edges from "a"
end

Remove

g:remove_vertex("a")           -- also removes incident edges
g:clear()                      -- reset
print(g:empty())               -- true

3. Topological sort (DAG only)

local g = graph.new(true)
g:add_edge("parse",     "analyze")
g:add_edge("analyze",   "optimize")
g:add_edge("optimize",  "emit")

local order, has_cycle = g:topo_sort()
if has_cycle then
    raise("cycle detected!")
end
for _, v in ipairs(order) do
    print(v)     -- parse, analyze, optimize, emit
end

topo_sort() returns (list, has_cycle). If there's a cycle, use find_cycle() to get the offending path:

local cycle = g:find_cycle()
if cycle then
    raise("cycle: %s", table.concat(cycle, " -> "))
end