I Built a Graph Engine in CUE

I’ve spent the last several months building a dependency graph engine entirely in CUE. Not configuration management. Not Kubernetes. Typed DAGs where unification does the analysis: critical path scheduling, gap analysis, compliance validation, provenance tracing, access policies, risk scoring, and about 60 other patterns.

It’s published as a CUE module (apercue.ca@v0), has 5 worked examples, a project scaffolder, CI that validates everything, and recently got picked up by a few W3C Community Groups who were interested in the approach. I wanted to share what I’ve learned pushing CUE into this territory: what works, and where I hit real walls.

Start here: a recipe as a dependency graph

Beef bourguignon. 17 steps – ingredients, prep, cooking – all typed nodes with depends_on edges:

"deglaze": {
    name: "deglaze"
    "@type": {CookStep: true}
    description: "Deglaze pan with red wine, reduce by half"
    depends_on: {"brown-beef": true, "saute-mirepoix": true, "red-wine": true}
    time_min: 10
}

Run it:

$ cue eval ./examples/recipe-ingredients/ -e cpm.critical_sequence
[{resource: "beef-chuck", start: 0,   finish: 0,   duration: 0},
 {resource: "brown-beef", start: 0,   finish: 15,  duration: 15},
 {resource: "deglaze",    start: 15,  finish: 25,  duration: 10},
 {resource: "braise",     start: 25,  finish: 175, duration: 150},
 {resource: "finish",     start: 175, finish: 205, duration: 30}]

Critical path: 205 minutes. The braise dominates (150 min). Prep steps have up to 172 minutes of slack, so you can dice onions anytime in the first 2.5 hours. All computed from the dependency structure at eval time.

Same graph also answers: “are all ingredients present?” (gap analysis), “do cook steps actually depend on something?” (compliance), “what’s the topology?” (layer grouping). One _steps struct, many projections.

What the engine actually does

The core is a #Graph pattern. You give it typed resources with depends_on edges, it computes:

• Topological layers
• Depth per node
• Roots and leaves
• Transitive ancestors (full closure)
• Dependents (reverse edges)
• Validation (dangling edge detection)

Then ~63 projection patterns consume that graph. Each takes Graph: #AnalyzableGraph as input and produces a different analysis:

Plus scheduling patterns, risk scoring, bootstrap planning, lifecycle phases, type validation, schema alignment. 63 definitions across 13 files, about 4,000 lines of CUE total (core packages).

Key CUE patterns

Struct-as-set for types

Resources use structs for type membership instead of lists:

"@type": {Produce: true, Seasoning: true}

• O(1) membership: resource["@type"]["Seasoning"] != _|_
• Merging is unification: {Produce: true} & {Seasoning: true} just works
• Dispatch via field overlap: patterns declare which types they serve, binding is set intersection

This is the foundation. Every pattern dispatches on @type field presence. A resource with {Dataset: true, Governed: true} matches a data catalog pattern (serves Dataset) AND a policy pattern (serves Governed) simultaneously.

Transitive closure via recursive struct merge

This is the most CUE-specific thing in the project:

_ancestors: {
    [_]: true
    if _hasDeps {
        for d, _ in _deps {
            (d): true
            resources[d]._ancestors
        }
    }
}

Each node accumulates its parents’ ancestors through struct unification. [_]: true constrains all values. Duplicates unify cleanly (true & true = true). Result: every node knows its full transitive ancestry.

This is what makes impact analysis, critical path, and gap analysis work: they’re all cheap comprehensions over precomputed ancestor sets.

Comprehensions as projections

Every analysis pattern follows the same shape:

#SomeProjection: {
    Graph: #AnalyzableGraph
    // ... comprehensions over Graph.resources
}

Swap the body, get a different output. The #AnalyzableGraph interface is what makes this composable: both #Graph (full computation) and #GraphLite (with precomputed topology) satisfy it, so all 63 patterns work with either.

Charter system

A #Charter declares what a project needs to be complete:

_charter: charter.#Charter & {
    name: "beef-bourguignon"
    scope: {
        total_resources: len(_steps)
        required_types: {Protein: true, Produce: true, CookStep: true}
    }
    gates: {
        "mise-en-place": {
            phase: 1
            requires: {"beef-chuck": true, "onions": true, "dice-onions": true}
        }
        "cooking-complete": {
            phase: 2
            requires: {"braise": true, "finish": true}
            depends_on: {"mise-en-place": true}
        }
    }
}

#GapAnalysis unifies the charter against the actual graph and reports: which gates are satisfied, which resources are missing, which types aren’t covered. If you cue vet a project that doesn’t satisfy its charter, it fails. Project completeness is a type check.

Where CUE breaks

This is the part I think CUE contributors will care about most.

No memoization on recursive struct references

The _ancestors computation? Beautiful on trees. Exponential on diamond DAGs. If C depends on A and B, and both depend on D, then D’s ancestors get recomputed through both paths. At ~40 nodes with moderate connectivity, eval times out.

Workaround: precompute externally.

Precomputed?: {
    depth:      [string]: int
    ancestors?: [string]: {[string]: true}
}

A Python toposort.py does the expensive parts, CUE consumes the result. #GraphLite skips recursion entirely. It works, but it means the engine has a Python dependency for anything non-trivial.

The 52-node governance example in the repo uses this path. The recipe (17 nodes) doesn’t need it. The boundary is around 35-40 nodes depending on graph shape: wide trees are fine, diamond DAGs blow up fast.

Question for CUE contributors: is there a path toward memoized evaluation of recursive struct references? Even opt-in memoization would eliminate the Python dependency entirely.

Both if branches always evaluate

_depth: {
    if Precomputed != _|_ { Precomputed.depth[name] }
    if Precomputed == _|_ { /* expensive recursive computation */ }
}

Both branches run regardless. Can’t short-circuit the expensive path when precomputed data exists. Had to create separate #Graph (with recursion) and #GraphLite (without) to avoid paying for both.

Comprehension-level vs body-level if

This filters elements:

for name, r in resources if r["@type"]["CookStep"] != _|_ { ... }

This produces empty structs for non-matches:

for name, r in resources {
    if r["@type"]["CookStep"] != _|_ { ... }
}

The second form bit me many times. Comprehension-level if filters; body-level if doesn’t remove the element. Once you internalize this it’s fine, but it’s a real gotcha.

Closed-world only

Every resource must be declared upfront. No open-world inference. For dependency graphs this is fine: you want the full graph at eval time. But it’s a fundamental constraint of the approach.

The ecosystem

The graph engine (apercue.ca) is the generic layer. Other projects import it as a CUE module:

apercue.ca@v0          Generic graph patterns (this project)
  └── quicue.ca@v0     Infrastructure types, providers, execution plans
  └── quicue-kg@v0     Knowledge graph types, SPARQL/Turtle projections
  └── cmhc-retrofit    Construction PM (housing retrofit domain)

Each downstream project declares domain-specific resources and types. The patterns, projections, and analysis all come from the shared module.

Try it

git clone https://github.com/quicue/apercue
cd apercue

# Recipe: critical path, gap analysis, summary
cue eval ./examples/recipe-ingredients/ -e cpm.critical_sequence
cue eval ./examples/recipe-ingredients/ -e gap_summary
cue eval ./examples/recipe-ingredients/ -e summary --out json

# Supply chain: 6-stage pipeline
cue eval ./examples/supply-chain/ -e summary --out json

# Course prerequisites: university curriculum graph
cue eval ./examples/course-prereqs/ -e summary --out json

# Scaffold a new project from the patterns
bash tools/scaffold.sh ~/myproject example.com/myproject@v0

The 52-node governance example (gc-llm-governance/) is the stress test: it uses precomputed topology and produces output across 8 different analysis dimensions.

Import it

The module is published as apercue.ca@v0:

import "apercue.ca/patterns@v0"

graph: patterns.#Graph & {Input: _myResources}
cpm:   patterns.#CriticalPath & {Graph: graph, Weights: _myWeights}
gaps:  charter.#GapAnalysis & {Charter: _myCharter, Graph: graph}

The scaffold.sh tool generates a starter project with the graph, charter, and compliance patterns already wired up.

External validation

The graph output happens to be valid JSON-LD: the engine maps CUE field names to standard vocabulary terms via a @context. This got the attention of a few W3C Community Groups working on knowledge graph construction and data governance:

• KG-Construct use case PR
• Dataspaces challenge
• Conversations with the new Context Graphs and UORA groups

I mention this not for the W3C angle but because it validates that the CUE output is structurally conformant to external specifications. The patterns produce real, standards-compliant data, not toy output.

github.com/quicue/apercue – Apache 2.0, 4,000 lines of CUE, 63 pattern definitions, 5 examples, CI, scaffolder.