Immutable DAG core

Status: open/planned · Kind: component · Audience: system

Summary

• The immutable graph substrate: opaque node ids with light attributes, directed dependency edges, topological queries, and cycle detection.

• Pure and zero-dep; knows nothing about status, rules, or scheduling — those live above it.

• Sub-capability of C-D2GO-readiness-scheduling.

Statement

The DAG core holds the structure everything else reads. Nodes are opaque ids plus an attribute bag; edges are dependencies (a depends on b). It answers structural questions — dependencies, dependents, ancestors, descendants, topological order — and reports cycles. Every builder method returns a new graph, so a graph is safe to share across concurrent readers without a lock.

The attribute bag has no open index signature, because Rust has none. The three fields the frontier and the built-in sorters read — category, weight, trigger — are named, and anything else the caller carries rides in an opaque passthrough map.

What it provides

• A Graph builder: Graph::new(), add_node(id, attrs), depends_on(node, dependency), each returning a new immutable graph.
• Topology queries: dependencies(id), dependents(id), ancestors(id), descendants(id), topo_sort().
• Cycle handling: has_cycle() reports, cycles() returns the member sets, and topo_sort() returns Err(CycleError). Detection is lazy — a cyclic graph is constructible, because has_cycle being queryable requires it.

use graph_scheduler::graph::{Graph, NodeAttrs};

let g = Graph::new()
    .add_node("T-1", NodeAttrs::new().category("impl").weight(3))
    .add_node("T-2", NodeAttrs::new())
    .depends_on("T-2", "T-1"); // T-2 needs T-1

g.ancestors("T-2"); // ["T-1"]
g.has_cycle();      // false

Inputs

• Node ids (opaque strings) and optional per-node attributes.
• Directed dependency edges.

Outputs

• An immutable graph value; topology query results (id lists, ordering).

Underlying implementation

• No code realizes this yet — the capability is planned. It lands with the crate at packages/rust/graph-scheduler/, the DAG core in src/graph.rs. Until the crate exists there is no anchor to record here.
• Hand-rolled adjacency structure (zero-dep core, per PR-DZTZ-graph-scheduler tenets); Kahn’s algorithm for topological order and cycle detection. Substrate choice (hand-roll vs. wrap a graph library) settled in D-BPD8-graph-scheduler-api.

---

← Back to Capabilities