Graph Scheduler

Status: open/draft

Summary

A small library that answers one question about a dependency graph: given nodes, dependency edges, and each node’s status, which nodes are runnable now — and hand me the next N to run in parallel.
Holds only opaque node ids plus light attributes; the caller keeps its real objects in its own store. Sorters and filters read that light attribute bag directly; for the caller’s full object they close over the caller’s store and look it up by id.
Built as a standalone library at packages/rust/graph-scheduler/ from the start (a cargo + moon workspace member), consumed in-process by the work-runner engine — no incubate-then-extract step. Rust per P-0012-rust-core-adapters-as-needed; the TypeScript scaffold that preceded this carried no logic and was retired rather than ported.
Layered like PR-0002-intersect: a pure immutable DAG core, a push readiness engine over caller-supplied state, and convenience helpers (sorters, trigger-rule presets, goal-directed / pull) above it.

What it is

Graph-scheduler is a dependency-graph readiness engine. You register nodes (opaque ids + optional attributes) and dependency edges, supply each node’s status, and ask getReady({ limit }) for up to N nodes whose dependencies are satisfied and whose trigger rule holds — the frontier you can safely run in parallel. It does not execute work, own your objects, or model resources; it answers what’s next, returns it, and lets you gate and order the result with registered functions.

It exists because the SDLC orchestrator already computes this by hand — “dispatch up to max_implementations task-work runs against open/ready tasks whose depends_on is satisfied, under per-category in-flight caps” (DR-G846-orchestrator-parallel-dispatch) — and the ecosystem’s closest off-the-shelf answer, Python’s graphlib.TopologicalSorter, is a bare get_ready() / done() loop with no rules, categories, ordering, or goal-direction (graph-scheduler-research). JavaScript/TypeScript has no equivalent at all (DR-0JEP-graph-readiness-ecosystem-gap).

The first adoption is that hand-rolled path itself: sdlc task next (D-Q2WR-task-pickup-order) is re-based onto this library as its reference consumer (T-8I15-adapt-task-next-onto-graph-scheduler), which both validates the API and retires the duplicate frontier/cycle/lift code T-7EJO-extract-corpus-depgraph-module consolidated into solutions/ontological/lib/model/corpus/. The four gaps that adoption surfaced are recorded in D-BPD8-graph-scheduler-api §First consumer.

Boundary

Graph-scheduler is one of the sibling OSS libraries PR-0001-sdlc’s Boundary anticipates — a general-purpose piece kept separate from the plugin and shipped standalone. It earns its own Product now because real SDLC work motivates it.

Inside this product:

The immutable DAG core — nodes + edges, topological queries, cycle detection.
The push readiness engine: getReady(graph, state) — the frontier, recomputed as caller-supplied state changes.
The status model (a small pending | running | success | failed | skipped enum) and trigger rules generalizing “all deps done.”
Registered sorters (priority_weight), eligibility filters, and the goal-directed / pull wrappers.

Outside it:

Execution. Graph-scheduler says what is runnable; the caller runs it. No task running, threads, or I/O.
Object storage. Nodes are opaque ids + light attributes; the caller’s real objects stay in the caller’s store.
Resource / quota modeling beyond “ask for N” plus caller filters. Weighted resource budgets (Buck2-style permits / exclusivity) are a later nice-to-have, not v1 (graph-scheduler-research).
Conflict / precedence resolution between two independently-runnable nodes. A caller may consult PR-0002-intersect for file-scope overlap and pass the verdict in as a filter, but graph-scheduler does not own it.

It lives at packages/rust/graph-scheduler/ as a standalone workspace member with its own Cargo.toml; the work-runner engine calls it in-process on the dispatcher tick. It is a separate library from day one — no incubation step. A TypeScript peer is built only if a TypeScript consumer of the frontier appears (P-0012-rust-core-adapters-as-needed).

The core question

Everything reduces to one primitive:

getReady(graph, state) — which nodes are runnable now, and give me the next N?

A node is runnable iff its status is pending and its parents’ statuses satisfy its trigger rule (default all_success). “Next N in parallel” is that frontier, capped at N and ordered by a registered sorter when it overflows.

Formal model

A dependency graph is a DAG; readiness is its topological frontier — Kahn’s-algorithm set of nodes with no unsatisfied prerequisites. Graph-scheduler generalizes “prerequisite satisfied” from all parents done to parents’ statuses satisfy this node’s trigger rule, and tracks status in a small enum so rules like all_done / one_failed / none_skipped are expressible — a boolean done cannot tell success from failure from skip (see D-BPD8-graph-scheduler-api).

The frontier is recomputed as state changes (a push model): the caller updates status, the engine re-derives what is ready. Capacity is the caller asking for N; ordering when the frontier exceeds N is a registered sorter (priority_weight). Complexity is friendly: computing the frontier is O(V + E); answering “next N” is a bounded top-N selection over it.

Design tenets & non-goals

Opaque ids; the caller owns objects. The graph carries ids and a light attribute bag, nothing more.
Pure immutable core; caller supplies state. getReady is a function of (graph, state); transitions return a new value — safe under the parallel-worktree world the plugin already lives in.
One primitive. Dependency satisfaction is the always-on built-in trigger rule; custom rules and filters compose on the same mechanism — there is no separate “dependency check.”
Layered, zero-dep core. Optional features (goal-direction, pull) accrete behind their own surfaces; the core pulls no runtime deps (PR-0002-intersect pattern).
Non-goals (v1): no execution; no object persistence; no weighted resource budgets (deferred); no conflict / precedence resolution.

Drivers & goals

Driver	Kind	What it wants
DR-G846-orchestrator-parallel-dispatch	use-case	Choose the next N tasks to run in parallel given `depends_on` and per-category in-flight caps — the orchestrator’s dispatch decision.
DR-QKVQ-goal-directed-frontier	use-case	A goal-directed frontier — the next work toward finishing a milestone, and what blocks it.
DR-0JEP-graph-readiness-ecosystem-gap	opportunity	Fill an ecosystem gap — no TS library answers “what’s runnable now” with rules, ordering, and goal-direction.

Goals attach here once the Product-layer Goal schema ships.

Status

open/draft — boundary, formal model, and API direction defined; prior art researched (graph-scheduler-research); no library code yet. The API is settled in D-BPD8-graph-scheduler-api and sliced into an ordered task set for v0.1.

References

Design: D-BPD8-graph-scheduler-api — the layered API (immutable core + push engine + helpers), with TypeScript examples.
Research: graph-scheduler-research — prior art (graphlib, Airflow, Kubernetes, Buck2, Bazel/Ninja), recommended API, and pitfalls.
Consumer / sibling: PR-0002-intersect — a caller may pass intersect’s scope-overlap verdict in as an eligibility filter.
Parent boundary: PR-0001-sdlc Boundary (OSS libraries extracted from the plugin).

← Back to Products