`(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.

explain-unordered-graphprocedure

Build the failure message for a graph Kahn's algorithm could not fully order. RESULT is the partial order it did produce.

find-cycle-pathprocedure

Find one concrete cycle, returned as an ordered node list whose last element repeats the first: ("a" "b" "a"). #f when the graph is acyclic. Unlike detect-cycles, which reports only the nodes it re-entered, this reports the PATH, which is what a reader needs in order to break the loop.

path-up-toprocedure

Prefix of PATH (most-recent-visit first) up to and including NODE.

dangling-edgesprocedure

Edges pointing at nodes the graph never defines. Kahn's algorithm can never decrement the dependent's in-degree for these, so the dependent is stuck forever even though no cycle exists. Returns a list of (dependent . missing-dependency) pairs.

duplicate-nodesprocedure

Node names appearing more than once as a graph key. A duplicate makes (length graph) overcount, so the sort's length check fires even when every node was ordered.

node-labelprocedure

Render a node for a message. Nodes are usually strings (package names, file paths) but the module is generic — callers may use structured keys to keep distinct node kinds from colliding — so degrade rather than raise.

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.