`(sigil build graph)`

(sigil build graph) - Graph Algorithms for Build Systems

This library provides generic graph algorithms useful for dependency resolution in build systems:

Topological sorting (Kahn's algorithm)
Cycle detection (DFS-based)

Graphs are represented as association lists where each entry is (node . (list of dependencies)).

Example usage:

(define graph '(("a" . ("b" "c"))
                ("b" . ("c"))
                ("c" . ())))
(topological-sort graph)  ; => ("c" "b" "a")
(has-cycle? graph)        ; => #f

Exports

alist-refprocedure

Get value from alist with default. Looks up KEY in ALIST using equal? comparison. Returns the associated value, or DEFAULT if not found.

alist-setprocedure

Set value in alist, returning a new alist. Removes any existing entry for KEY and adds the new (KEY . VALUE) pair.

topological-sortprocedure

Topologically sort a dependency graph.

Input: graph as alist of (node . (list of dependencies)) Returns: list of nodes in dependency order (dependencies first) Raises error if cycle detected.

Example:

(topological-sort '(("a" . ("b")) ("b" . ("c")) ("c" . ())))
; => ("c" "b" "a")

topological-sort-fromprocedure

Topologically sort a subgraph reachable from a target node.

Useful for building just the dependencies of a specific target. Returns only the nodes needed to build TARGET, in dependency order.

compute-in-degreesprocedure

Compute in-degrees for all nodes. In-degree = number of dependencies this node has.

build-reverse-graphprocedure

Build reverse graph: for each node, list nodes that depend on it.

kahn-processprocedure

Kahn's algorithm main loop.

decrement-in-degreesprocedure

Decrement in-degrees for a list of nodes.

collect-reachableprocedure

Collect all nodes reachable from a target (including the target itself). Used to find all transitive dependencies.

has-cycle?procedure

Check if graph has any cycles.

detect-cyclesprocedure

Detect cycles in graph using depth-first search. Returns list of nodes involved in cycles, or empty list if none.

Uses three-color marking:

white: unvisited
gray: currently being visited (on stack)
black: completely visited

A cycle exists when we encounter a gray node during DFS.

dfs-visitprocedure

DFS visit for cycle detection.