Skip to content

graph

The graph module provides graph data structure with support for both directed and undirected graphs. It includes functionality for topological sorting, cycle detection, and graph manipulation. This is an extension module of xmake.

TIP

To use this module, you need to import it first: import("core.base.graph")

graph.new

  • Create a new graph
lua
import("core.base.graph")

local g = graph.new(directed)

Creates a new graph object. The directed parameter specifies whether the graph is directed (true) or undirected (false).

lua
-- Create a directed graph (DAG)
local dag = graph.new(true)

-- Create an undirected graph
local ug = graph.new(false)

graph:clear

  • Clear the graph
lua
graph:clear()

Removes all vertices and edges from the graph, resetting it to an empty state.

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(2, 3)

print(#g:vertices())  -- Output: 3

g:clear()
print(#g:vertices())  -- Output: 0
print(g:empty())      -- Output: true

graph:empty

  • Check if the graph is empty
lua
local is_empty = graph:empty()

Returns true if the graph contains no vertices.

lua
local g = graph.new(true)
print(g:empty())  -- Output: true

g:add_vertex(1)
print(g:empty())  -- Output: false

graph:is_directed

  • Check if the graph is directed
lua
local directed = graph:is_directed()

Returns true if the graph is directed, false if it's undirected.

lua
local dag = graph.new(true)
print(dag:is_directed())  -- Output: true

local ug = graph.new(false)
print(ug:is_directed())   -- Output: false

graph:vertices

  • Get all vertices
lua
local vertices = graph:vertices()

Returns an array containing all vertices in the graph.

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(2, 3)
g:add_vertex(4)

local vertices = g:vertices()
for _, v in ipairs(vertices) do
    print(v)  -- Output: 1, 2, 3, 4
end

graph:vertex

  • Get vertex at the given index
lua
local v = graph:vertex(idx)

Returns the vertex at the specified index (1-based).

lua
local g = graph.new(true)
g:add_edge("a", "b")
g:add_edge("b", "c")

print(g:vertex(1))  -- Output: a
print(g:vertex(2))  -- Output: b
print(g:vertex(3))  -- Output: c

graph:has_vertex

  • Check if the graph has the given vertex
lua
local exists = graph:has_vertex(v)

Returns true if the vertex exists in the graph.

lua
local g = graph.new(true)
g:add_vertex(1)
g:add_vertex(2)

print(g:has_vertex(1))  -- Output: true
print(g:has_vertex(3))  -- Output: false

graph:add_vertex

  • Add an isolated vertex
lua
graph:add_vertex(v)

Adds a vertex to the graph without any edges. If the vertex already exists, this operation has no effect.

lua
local g = graph.new(true)
g:add_vertex(1)
g:add_vertex(2)
g:add_vertex(3)

print(#g:vertices())  -- Output: 3
print(#g:edges())     -- Output: 0

graph:remove_vertex

  • Remove the given vertex
lua
graph:remove_vertex(v)

Removes a vertex and all its associated edges from the graph.

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(2, 3)
g:add_edge(3, 4)

g:remove_vertex(2)
print(g:has_vertex(2))  -- Output: false
-- Edges 1->2 and 2->3 are also removed

graph:edges

  • Get all edges
lua
local edges = graph:edges()

Returns an array containing all edges in the graph. Each edge has from() and to() methods.

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(2, 3)

for _, e in ipairs(g:edges()) do
    print(e:from(), "->", e:to())
    -- Output: 1 -> 2
    --         2 -> 3
end

graph:adjacent_edges

  • Get adjacent edges of the given vertex
lua
local edges = graph:adjacent_edges(v)

Returns an array of edges that are adjacent to the specified vertex.

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(1, 3)
g:add_edge(2, 3)

local edges = g:adjacent_edges(1)
for _, e in ipairs(edges) do
    print(e:from(), "->", e:to())
    -- Output: 1 -> 2
    --         1 -> 3
end

graph:add_edge

  • Add an edge
lua
graph:add_edge(from, to)

Adds a directed edge from from to to. For undirected graphs, this creates a bidirectional connection. Automatically creates vertices if they don't exist.

lua
-- Directed graph
local dag = graph.new(true)
dag:add_edge("a", "b")
dag:add_edge("b", "c")

-- Undirected graph
local ug = graph.new(false)
ug:add_edge(1, 2)
-- For undirected graphs, both 1->2 and 2->1 are connected

graph:has_edge

  • Check if the graph has the given edge
lua
local exists = graph:has_edge(from, to)

Returns true if an edge exists from from to to.

lua
local g = graph.new(true)
g:add_edge(1, 2)

print(g:has_edge(1, 2))  -- Output: true
print(g:has_edge(2, 1))  -- Output: false (directed graph)

graph:topo_sort

  • Perform topological sort
lua
local order, has_cycle = graph:topo_sort()

Performs a topological sort on a directed graph using Kahn's algorithm. Returns an array of vertices in topological order and a boolean indicating if a cycle was detected. Only works on directed graphs.

lua
local dag = graph.new(true)
dag:add_edge(0, 5)
dag:add_edge(0, 2)
dag:add_edge(0, 1)
dag:add_edge(3, 6)
dag:add_edge(3, 5)
dag:add_edge(3, 4)
dag:add_edge(5, 4)
dag:add_edge(6, 4)
dag:add_edge(6, 0)
dag:add_edge(3, 2)
dag:add_edge(1, 4)

local order, has_cycle = dag:topo_sort()
if not has_cycle then
    for _, v in ipairs(order) do
        print(v)  -- Output: vertices in topological order
    end
else
    print("Graph has cycle!")
end

TIP

Topological sort is only applicable to directed acyclic graphs (DAGs). If a cycle is detected, the has_cycle flag will be true.

graph:partial_topo_sort_reset

  • Reset partial topological sort state
lua
graph:partial_topo_sort_reset()

Resets the internal state for partial topological sorting. This must be called before starting a new partial topological sort.

lua
local dag = graph.new(true)
dag:add_edge(1, 2)
dag:add_edge(2, 3)

dag:partial_topo_sort_reset()
-- Now ready for partial topological sorting

graph:partial_topo_sort_next

  • Get next node in topological order
lua
local node, has_cycle = graph:partial_topo_sort_next()

Returns the next node with zero in-degree in the topological sort. Returns nil when complete or if a cycle is detected. The has_cycle flag indicates if a cycle was detected.

lua
local dag = graph.new(true)
dag:add_edge("a", "b")
dag:add_edge("b", "c")

dag:partial_topo_sort_reset()

local order_vertices = {}
while true do
    local node, has_cycle = dag:partial_topo_sort_next()
    if node then
        table.insert(order_vertices, node)
        dag:partial_topo_sort_remove(node)
    else
        if has_cycle then
            print("Cycle detected!")
        end
        break
    end
end

-- order_vertices = {"a", "b", "c"}

TIP

Partial topological sort allows you to process nodes incrementally and supports dynamic graph modifications during the sort.

graph:partial_topo_sort_remove

  • Remove node and update in-degrees
lua
graph:partial_topo_sort_remove(node)

Removes the specified node from the partial topological sort and updates the in-degrees of its dependent nodes. This should be called after processing each node from partial_topo_sort_next().

lua
local dag = graph.new(true)
dag:add_edge(1, 2)
dag:add_edge(2, 3)

dag:partial_topo_sort_reset()

local node, has_cycle = dag:partial_topo_sort_next()
if node then
    print("Processing node:", node)
    dag:partial_topo_sort_remove(node)
    -- This updates in-degrees for nodes dependent on this node
end

graph:find_cycle

  • Find cycle in the graph
lua
local cycle = graph:find_cycle()

Searches for a cycle in the graph using depth-first search. Returns an array of vertices that form a cycle, or nil if no cycle exists.

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(2, 3)
g:add_edge(3, 1)  -- Creates a cycle

local cycle = g:find_cycle()
if cycle then
    print("Found cycle:")
    for _, v in ipairs(cycle) do
        print(v)  -- Output: 1, 2, 3 (forming a cycle)
    end
end

graph:clone

  • Clone the graph
lua
local new_graph = graph:clone()

Creates a complete copy of the graph with all vertices and edges. The new graph is independent of the original.

lua
local g1 = graph.new(true)
g1:add_edge(1, 2)
g1:add_edge(2, 3)

local g2 = g1:clone()

-- Modifying the copy doesn't affect the original
g2:add_edge(3, 4)
print(#g1:edges())  -- Output: 2 (original unchanged)
print(#g2:edges())  -- Output: 3 (copy modified)

graph:reverse

  • Reverse the graph
lua
local reversed = graph:reverse()

Creates a new graph with all edges reversed. For directed graphs, this reverses the direction of all edges. For undirected graphs, this is equivalent to clone().

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(2, 3)

local rg = g:reverse()

-- Original: 1 -> 2 -> 3
-- Reversed: 1 <- 2 <- 3
print(rg:has_edge(2, 1))  -- Output: true
print(rg:has_edge(3, 2))  -- Output: true

graph:dump

  • Dump graph information
lua
graph:dump()

Prints detailed information about the graph including all vertices and edges. Useful for debugging.

lua
local g = graph.new(true)
g:add_edge(1, 2)
g:add_edge(2, 3)

g:dump()
-- Output:
-- graph: directed, vertices: 3, edges: 2
-- vertices:
--   1
--   2
--   3
-- edges:
--   1 -> 2
--   2 -> 3

TIP

The graph module is useful for modeling dependencies, scheduling tasks, analyzing relationships, and detecting cycles. It supports both directed and undirected graphs and provides efficient algorithms for common graph operations.

WARNING

  • Topological sort only works on directed graphs
  • Removing a vertex also removes all its associated edges
  • For undirected graphs, add_edge(a, b) creates a bidirectional connection
  • Partial topological sort supports dynamic graph modifications during the sort