DAG of tasks: dependency readiness, topo order, cycle detection, parallel branches

State: open/active · Genre: analysis

Use case: dag-scheduling RFC mapping: UC7 Source: cross-repo survey of sksizer/* (2026-07-05), companion to the workflow-constellation RFC (PR #682).

The need

Dependency-graph execution has been hand-implemented repeatedly across the fleet — twice in the same repo before being unified, half-built and abandoned in two Rust engines, fully built minus parallelism in Python, and compiled to prose instead of executed in one product. The recurring core: declared depends_on edges, ready-frontier computation, topological order with priority tiebreaks, cycle detection, and failure pruning of transitive dependents.

Evidence

DarkFactory

Full hand-rolled DAG executor: scope closure, Kahn topo sort with priority tiebreaks, sticky skip lists, transitive-dependent pruning on failure, stacked-branch base-ref resolution, drain-queue mode — with parallel execution designed (PRD-551) but unbuilt.

Where: python/darkfactory/graph/_execution.py · python/darkfactory/graph/_dag.py · .darkfactory/data/prds/PRD-563-drain-ready-queue-execution-mode.md

Pain: The whole executor is bespoke and its parallel half is blocked on scheduler cost.

dev

Task depends_on readiness was built twice (next.ts and audit.ts) then unified into corpus/graph.ts; a sibling graph-scheduler library is already scaffolded as a product with a graphlib/Airflow/Kubernetes research dossier and a getReady({limit}) frontier design.

Where: plugin/lib/model/corpus/graph.ts · plugin/lib/model/entities/task/ops/next.ts · packages/ts/graph-scheduler/graph.ts · docs/planning/notes/N-OR19-graph-scheduler-research.md

Pain: Built twice in-repo, and now being designed a third time as a standalone library that overlaps @flow/dag directly.

agentpants

387-line Rust graph analyzer (edge validation, BFS reachability, Kahn sort with CycleDetected, parallel-group extraction) whose only compilation target is markdown prose — decision nodes become ‘If…’ bullets, parallel nodes become ‘wait for all parallel tasks’ instructions an LLM may or may not follow.

Where: src-tauri/src/export/compiler/graph_analyzer.rs · src-tauri/src/export/compiler/code_generator.rs · docs/prd.md

Pain: The workflows have no executable runtime; joins are hope. A typed workflow library is the natural compile target.

rust-evented-worker

petgraph readiness graph rebuilt on every reduce, but the scheduler is a one-line left-to-right ‘first runnable’ scan; the multi-activity Schedule enum is dead code and docs/todo.md names the missing dependency model.

Where: src/runner/reduce/update_graph.rs · src/runner/scheduler.rs · docs/todo.md

Pain: Graph bookkeeping exists; ‘what runs next, possibly in parallel’ was never completed.

rust-worker-prototype

StepDefinition::Parallel designed into the template type but the executor’s flatten() silently treats Parallel identically to Sequential.

Where: src/bin/prototype_three.rs

Pain: Parallel branches encoded in the data model; the scheduler was the part too expensive to hand-roll.

ontological

UnitOfWork carries depends_on and parent_id, but the ready-list query ignores dependencies entirely and Gate steps are skipped with a ‘not yet implemented’ warning; Phase 5 (hierarchical work) deferred.

Where: src-tauri/src/schema/unit_of_work.rs · src-tauri/src/store/engine_queries.rs

Pain: DAG ordering modeled in the schema, stalled at the scheduler.

Flowline fit

@flow/dag’s scheduler + fan-out. Two design decisions the evidence forces: (1) an explicit boundary/merge decision with the in-repo graph-scheduler package (duplication risk inside the same monorepo); (2) an incremental ready-frontier API (getReady-style pull) in addition to run-the-whole-DAG, since DarkFactory’s drain-queue mode, dev’s per-tick dispatch, and ontological’s supervisor all consume readiness incrementally rather than executing one static graph.

Proposed API

Builds on: 06, 09 Introduces: dag(), runDag()

Non-linear graphs: tasks declare dependencies, ready tasks run in parallel under a cap, and the earlier combinators nest as nodes:

import { dag, runDag } from "flowline/dag";

const g = dag("code-task")
  .task("analyze",   analyze,   { deps: [] })
  .task("plan",      planTask,  { deps: ["analyze"] })
  .task("research",  research,  { deps: ["analyze"] })          // parallel with plan
  .task("implement", reviewed,  { deps: ["plan", "research"] }) // 06's judge as a node
  .task("verify",    verifyAll, { deps: ["implement"] })        // 09's fanOut as a node
  .build();

const result = await runDag(g, { concurrency: 8 });

Readiness/topo-order/cycle-detection can delegate to graph-scheduler (PR #682 cleanup item 2). The queue-supervision evidence (ontological’s Supervisor, this repo’s orchestrate tick) also wants the incremental form — g.ready() as a pull API — not only run-to-completion.

---

← Back to Notes