.graph.* — graph algorithms

Builds a CSR-backed graph from an edge table, then exposes a family of algorithms — traversal, shortest paths, centrality, community detection, spanning trees — that consume the graph handle and return tables keyed by node ID. The graph is an opaque i64 atom with the RAY_ATTR_GRAPH bit set; it owns a ray_rel_t* that must be released with .graph.free when no longer needed.

All algorithm wrappers follow the same template: validate the handle, fold positional parameters off args[], build a one-node DAG, dispatch through ray_execute, return the result table. Algorithms that consume edge weights read the 'weight column registered at build time.

Reference

Function	Arity	Flags	Description
.graph.build	variadic	—	Build a graph handle from an edge table.
.graph.free	unary	—	Release a graph handle (idempotent).
.graph.info	unary	—	Dict of n_nodes / n_edges / sorted / has_weights.
.graph.expand	variadic	—	1-hop neighbour expansion from a seed node.
.graph.var-expand	variadic	—	BFS variable-depth expansion with optional path tracking.
.graph.dfs	variadic	—	Depth-first traversal from a seed node.
.graph.random-walk	variadic	—	Uniform random walk from a seed node.
.graph.shortest-path	variadic	—	BFS shortest path between two nodes.
.graph.dijkstra	variadic	—	Weighted shortest paths from a source (optionally to a target).
.graph.k-shortest	variadic	—	Yen's k shortest weighted paths between two nodes.
.graph.pagerank	variadic	—	Iterative PageRank scores.
.graph.degree	variadic	—	In/out/total degree per node.
.graph.betweenness	variadic	—	Brandes betweenness centrality (exact or sampled).
.graph.closeness	variadic	—	Closeness centrality (exact or sampled).
.graph.connected	variadic	—	Connected components via label propagation.
.graph.louvain	variadic	—	Louvain modularity-based community detection.
.graph.cluster	variadic	—	Local clustering coefficient per node.
.graph.mst	variadic	—	Minimum spanning tree (Kruskal).
.graph.topsort	variadic	—	Topological sort (Kahn).

.graph.build

Signatures:

• (.graph.build tbl 'src 'dst) — unweighted graph.
• (.graph.build tbl 'src 'dst 'weight) — weighted graph; the weight column must be numeric (I64/I32/F32/F64 — coerced to F64 internally).

src/dst columns can be I64/I32/I16/U8/SYM — non-I64 columns are widened to I64 into a scratch vector. The node universe is max(max(src), max(dst)) + 1.

Returns: an opaque graph handle. Free with .graph.free when done — leaking it keeps the CSR alive (it may be tens of MB for large graphs).

(set edges (table [src dst w]
  (list [0 0 1 1 2 2 3 4]
        [1 2 2 3 3 4 5 5]
        [1.0 4.0 2.0 5.0 1.0 3.0 2.0 1.0])))

(set g (.graph.build edges 'src 'dst 'w))

Errors: rank (arity != 3 or 4), type (tbl not a table / column refs wrong type), name (column not in tbl), length (src/dst/weight len mismatch), oom.

.graph.free

Signature: (.graph.free g). Releases the underlying CSR. Idempotent — a second call returns type (the RAY_ATTR_GRAPH bit is cleared on the first call), not a double-free.

(.graph.free g)

.graph.info

Signature: (.graph.info g). Returns a dict with keys n_nodes, n_edges, sorted (bool: true when adjacency lists are sorted, required for LFTJ-style joins), has_weights.

(.graph.info g)
;; => {n_nodes: 6, n_edges: 8, sorted: true, has_weights: true}

.graph.expand

Signature: (.graph.expand g src [direction]). direction is 0 (forward, default), 1 (reverse), 2 (both). Returns a {_src, _dst} table — direct neighbours of src in the chosen direction.

(count (.graph.expand g 0))      ;; forward neighbours of node 0
(set rev (.graph.expand g 5 1))  ;; reverse neighbours of node 5

Errors: rank, type, domain (direction out of {0,1,2}).

.graph.var-expand

Signature: (.graph.var-expand g src min-depth max-depth [direction] [track-path]). BFS to between min-depth and max-depth hops, returning a node table. When track-path is true the per-node path is included as a list column. Depths are clamped to [0, 255] and min-depth ≤ max-depth.

;; All nodes 1..3 hops from node 2, both directions, paths tracked
(.graph.var-expand g 2 1 3 2 1)

.graph.dfs

Signature: (.graph.dfs g src [max-depth]). Returns {_node, _depth, _parent} in DFS visit order. Default max-depth is 255.

.graph.random-walk

Signature: (.graph.random-walk g src [walk-len]). Returns {_step, _node}. Default walk-len is 10.

.graph.shortest-path

Signature: (.graph.shortest-path g src dst [max-depth]). Bidirectional BFS — unweighted hop-count shortest path. Default max-depth is 255.

(>= (count (.graph.shortest-path g 0 5)) 1)   ;; reachable
(count (.graph.shortest-path g 3 3))          ;; 1 (start = goal)

.graph.dijkstra

Signature: (.graph.dijkstra g src [dst] [max-depth]). With dst omitted (or null) it runs single-source mode, returning all reachable nodes. With dst set, it returns the path to that target. max-depth defaults to 255.

Requires that the graph was built with a weight column — otherwise returns schema error "graph has no weight column". Negative edge weights surface a domain error from the executor.

;; Single-source distances from node 0
(set dst (.graph.dijkstra g 0))

;; Path from 0 to 5
(set path (.graph.dijkstra g 0 5))

.graph.k-shortest

Signature: (.graph.k-shortest g src dst k). Yen's algorithm — finds up to k shortest weighted paths between src and dst. k must be in [1, 65535]. Requires a weight column.

.graph.pagerank

Signature: (.graph.pagerank g [iter] [damping]). Defaults: iter=30, damping=0.85. Bounds: iter ∈ (0, 65535], damping ∈ (0, 1). Returns {_node, _rank}.

(.graph.pagerank g)              ;; defaults
(.graph.pagerank g 100 0.9)      ;; more iterations, higher damping

.graph.degree

Signature: (.graph.degree g). Returns {_node, _in_degree, _out_degree, _degree}.

.graph.betweenness

Signature: (.graph.betweenness g [sample]). sample=0 (default) runs the exact Brandes algorithm; sample>0 samples that many source nodes (faster, approximate). Bounds: sample ∈ [0, 65535]. Returns {_node, _centrality}.

.graph.closeness

Signature: (.graph.closeness g [sample]). Same sample semantics as betweenness. Returns {_node, _centrality}.

.graph.connected

Signature: (.graph.connected g). Label-propagation connected components — returns {_node, _component}. Treats the graph as undirected.

.graph.louvain

Signature: (.graph.louvain g [max-iter]). Modularity-maximising community detection. Default max-iter=100. Returns {_node, _community}.

.graph.cluster

Signature: (.graph.cluster g). Local clustering coefficient per node — the fraction of each node's neighbours that are also connected to each other. Returns {_node, _coefficient}. Pendant nodes (degree < 2) get coefficient 0.0.

.graph.mst

Signature: (.graph.mst g). Kruskal's minimum spanning forest. Requires a weight column. Returns {_src, _dst, _weight} — one row per MST edge.

.graph.topsort

Signature: (.graph.topsort g). Kahn's topological sort. Returns {_node, _order} on a DAG; errors on a graph that contains a cycle.

See also

• Graph Algorithms — C API equivalents, opcode reference, complexity table, SIP and factorized execution.
• Graph Storage — CSR construction details and the ray_rel_t lifetime contract.
• Datalog Guide — declarative reachability queries that often replace explicit traversal.