@orcish/dag

An immutable, type-safe directed acyclic graph for TypeScript. Every structural operation returns a new graph — old snapshots never change — and acyclicity is enforced as you build: adding an edge that would close a cycle throws rather than corrupting the graph.

Ships two interchangeable APIs over the same data: a fluent Dag class and a tree-shakeable set of pure functions over an immutable DagRaw snapshot. No runtime dependencies; ESM-only; works in Node and the browser.

Install

pnpm add @orcish/dag

Usage

import { Dag } from '@orcish/dag';

// `idOf` maps each node value to its key. Nodes can be any type.
const dag = new Dag({ idOf: (n: { id: string }) => n.id })
  .addNode({ id: 'wake' })
  .addNode({ id: 'coffee' })
  .addNode({ id: 'code' })
  .addEdge('wake', 'coffee')
  .addEdge('coffee', 'code');

dag.topologicalSort(); // [{id:'wake'}, {id:'coffee'}, {id:'code'}]
dag.roots(); // [{id:'wake'}]
dag.leaves(); // [{id:'code'}]
dag.descendants('wake'); // [{id:'coffee'}, {id:'code'}]

// Each structural method returns a new instance — the original is untouched.
dag.addEdge('code', 'wake'); // throws CycleError; `dag` is unchanged

Two APIs, one model

The Dag class is a thin, fluent wrapper. If you prefer plain functions, the same operations are exported directly and operate on the immutable DagRaw snapshot:

import { addEdge, addNode, emptyDagRaw, topologicalSort } from '@orcish/dag';

let g = emptyDagRaw<{ id: string }>(n => n.id);
g = addNode(g, { id: 'a' });
g = addNode(g, { id: 'b' });
g = addEdge(g, 'a', 'b');
topologicalSort(g); // [{id:'a'}, {id:'b'}]

dag.toRaw() exposes that snapshot — the interop boundary for handing the graph to external tooling such as @orcish/dag-mermaid.

What's included

• Construction — new Dag({ idOf }), Dag.from(nodes, edges, { idOf }), and the pure emptyDagRaw / buildDag.
• Mutation (all return a new graph) — addNode, addEdge, removeEdge.
• Queries — getNode, hasNode, hasEdge, size, nodes(), predecessors, successors, ancestors, descendants, inDegree, outDegree, roots, leaves.
• Algorithms — topologicalSort, topologicalGenerations, bfs, detectCycles, isDAG, wouldCreateCycle.

Invariants & errors

The graph keeps itself well-formed and signals violations by throwing:

• DuplicateNodeError — adding a node whose id already exists.
• UnknownNodeError — referencing a node that isn't in the graph.
• SelfLoopError — an edge from a node to itself.
• CycleError — an edge (or a buildDag input) that would create a cycle.

wouldCreateCycle(from, to) is the non-throwing pre-check if you'd rather test before adding.

License

MIT © Michael Martin