graph-grammar

A fast, framework-agnostic graph rewriting (graph grammar) engine for TypeScript. Author rewrite rules , a left-hand-side pattern to find and a right-hand-side result to replace it with , and apply them to a host graph: subgraph matching, edge embedding, negative application conditions, property expressions, and stochastic/parallel application strategies.

The only runtime dependency is zod (used for validated import/export). No DOM, React, or D3 , runs in Node, the browser, or a worker.

npm install graph-grammar

ESM-only. Ships TypeScript types.

Quick start

import { rule, pn, pe, rn, re, grammar, Engine } from 'graph-grammar'

// Rule: every A,A edge gains a B in the middle (A,B,A).
const subdivide = rule({
  name: 'subdivide',
  lhs: { nodes: [pn('a', 'A'), pn('b', 'A')], edges: [pe('e', 'a', 'b')] },
  rhs: {
    nodes: [rn('a', 'A', { mapFrom: 'a' }), rn('mid', 'B'), rn('b', 'A', { mapFrom: 'b' })],
    edges: [re('e1', 'a', 'mid'), re('e2', 'mid', 'b')],
  },
})

const start = {
  nodes: [
    { id: '1', label: 'A', props: {} },
    { id: '2', label: 'A', props: {} },
  ],
  edges: [{ id: 'x', source: '1', target: '2', label: '', directed: false, props: {} }],
}

const engine = new Engine(grammar('demo', [subdivide], start, { strategy: 'maximal', maxSteps: 3 }))
engine.run()
console.log(engine.graph.nodes.length)

Features

• Expressive rules , label + wildcard matching, property predicates (>, ==, regex, in, exists, …), exact-degree context, NACs.
• Edge embedding , control what happens to a deleted node's edges (remove, redirectTo, redirectToAll) , including node merging/contraction.
• Property expressions , literals, seeded randoms, a global counter, copy and increment from matched nodes (child.depth = parent.depth + 1).
• Strategies , random (weighted/stochastic), priority (phased), sequential, and maximal (parallel rewriting).
• Validated I/O , importGrammar / exportGrammar with zod schemas exported for your own runtime checks.
• Fast , O(1) label buckets, an allocation-free VF2-style matcher, and single-match rewriting keep parallel-growth grammars O(N).

Documentation

Full guides and API reference: the docs site (see the repository).

• Getting started, core concepts, authoring rules, application strategies, serialization & validation, and the complete API reference.

Examples

Ready-to-run example grammars (L-systems, infection spread, binary trees, a dungeon generator, …) ship behind a subpath so they tree-shake away when unused:

import { buildExample, EXAMPLES } from 'graph-grammar/examples'

const dungeon = buildExample('dungeon')

License

MIT