Cellular Automata on Directed Graphs

A small language, and an interpreter for it, built for experiment rather than proof

“The lattice is not the world. It is the one neighbourhood structure we could draw on graph paper.”

A cellular automaton is usually presented on a grid, and the grid does two things at once that are worth separating. It fixes who talks to whom, and it makes that relation symmetric: if I am your neighbour, you are mine. Nearly every system we actually care about violates the second condition. A neuron drives its postsynaptic partners and is not driven back by them. A citation points one way. Gossip travels downhill through an organisation chart. A gene represses another gene that has no say in the matter.

On a symmetric lattice the two coincide, which is exactly why the distinction is invisible in the classical treatment. Recovering Conway's Life here is a matter of declaring a moore graph, whose edges are laid down in both directions.Once you drop symmetry, a node has two distinct neighbourhoods: the in-neighbourhood, which is the set of nodes that can influence it, and the out-neighbourhood, the set it influences. A local rule is a function of the first. The second determines how the node's own state propagates. Direction turns a static picture into a plumbing diagram, and the interesting questions become questions about flow: where does activity accumulate, which cycles sustain themselves, what happens at a node whose in-degree is one and out-degree is forty.

The page below is a workbench for asking those questions. It contains a domain specific language for describing a directed graph, an initial condition, and an update rule, together with a complete interpreter — lexer, parser, compiler, and evaluator — written for this page alone. Nothing is fetched; nothing is stored on a server. Edit the program on the left, press Build & Run, and watch.

The workbench

Program ⌘/Ctrl + Enter to build

rate example

Graph click a node to cycle its state; hover to trace its edges

Space–time one row per node, time runs left to right; beneath it, the population of each state

The raster is the honest record. A directed graph drawn as a ball of arrows will hide almost anything; a node ordered by index, plotted against time, will not. Vertical banding means synchrony, diagonal streaks mean travelling waves along the index order, and a static horizontal line means a node has found a fixed point its in-neighbours cannot dislodge.

The examples in the menu

The language in one page

A program is a sequence of declarations. Order does not matter between blocks, and within a block one statement occupies one line. Comments begin with #, except when a # is immediately followed by three or six hexadecimal digits, in which case it is a colour.

seed 7                       # fix the random stream
param density = 0.18 [0, 1]  # a slider will appear

states { quiet #e8e4d9, firing #1c1c1c, spent #a8402c }

graph {
  ring 96                    # 96 nodes, i -> i+1
  chord 37                   # and i -> i+37 (mod n)
}

init {
  all quiet
  random firing density
}

rules {
  quiet  -> firing when in(firing) >= 1
  firing -> spent
  spent  -> quiet  when age >= 2
}

This is the Greenberg–Hastings excitable medium: a refractory period that forbids an excitation from running backwards into the tissue it just came from. On a ring with a chord it produces a wave that survives or dies depending on whether the chord lets the wavefront outrun its own refractory tail.The first state declared is the default: every node begins there before the init block runs. Each rule is a guarded transition, and the rules are tried in the order written. The first rule whose source state matches and whose guard is true is the one that fires; if none matches, the node keeps its state. A rule with no when clause always matches.

Blocks

Declaration	Meaning
states { a, b #hex, … }	Names the state set, in order. The first is the quiescent default. Colours are optional and drawn from a fixed palette otherwise.
graph { … }	Builds the directed graph by applying generators and operators in sequence.
init { … }	Sets the initial configuration. Re-run by Reset.
rules { … }	The ordered list of guarded transitions.
param p = v [lo, hi]	A named constant with a slider. The bounds are optional. Values used by `rules` take effect immediately; values used by `graph` take effect on the next build.
seed n	Seeds the deterministic generator used for graph construction, initial conditions, and stochastic rules.
update sync	Every node is updated from the same snapshot (the default).
update async `k`	One step performs `n` updates at uniformly random nodes, each visible to the next. Order matters, and on a directed graph it matters a great deal. An optional count replaces `n`, for a slower sweep.
layout circle \| grid \| force \| auto	How to place the nodes for drawing. `auto` reads the generators and guesses.

Graph generators and operators

Generators create nodes; operators act on whatever exists. They compose, so ring 64 followed by rewire 0.1 is a directed small world, and torus 20 20 followed by bidirect is an ordinary undirected lattice.

Statement	Effect
nodes n	Ensure at least `n` nodes exist.
ring n	`n` nodes, edge `i` → `i`+1 (mod `n`).
path n	As above without the closing edge.
chord k	For every existing node, edge `i` → `i`+`k` (mod `n`).
grid w h	`w`×`h` nodes, edges to the right and down, no wrap.
torus w h	The same with wrap: every node has in-degree and out-degree 2.
vonneumann w h	Wrapped 4-neighbourhood, edges in both directions.
moore w h	Wrapped 8-neighbourhood, both directions. The classical substrate.
complete n	Every ordered pair.
star n	Node 0 broadcasts to all others.
tree b d	Branching factor `b`, depth `d`, edges parent → child.
random n p	`n` nodes; each ordered pair becomes an edge with probability `p`.
outdeg n k	`n` nodes, each given exactly `k` distinct random out-edges.
scalefree n m	Preferential attachment: each newcomer is adopted by `m` established nodes, which point at it. A few hubs acquire enormous out-degree and become broadcasters.
edge a -> b	One explicit edge, creating nodes as needed.
bidirect	Add the reverse of every edge, making the graph symmetric.
reverse	Reverse every edge. Sources become sinks.
rewire p	Each edge keeps its source and, with probability `p`, takes a uniformly random new target.
selfloops	Give every node an edge to itself, so it sees its own state in `in()`.

Initial conditions

Statement	Effect
all s	Every node to state `s`.
node i s	A single node by index.
random s p	Each node independently to `s` with probability `p`.
pick k s	Exactly `k` distinct nodes chosen uniformly.
set s where `expr`	Every node whose expression is non-zero. The expression may use `id`, `indeg`, `outdeg`, `n`, `rand()`.

Rules

from -> to [when guard] [with prob p]

where from is a state name or _ for any state, and to is a state name or self to stay put. The optional probability is evaluated per node per step. Note the conflict rule: if a transition matches but its coin comes up tails, the node holds its state and no later rule is consulted. This keeps the semantics of an ordered rule list unambiguous, at the cost of making two competing probabilistic rules for the same source state behave as a cascade rather than a lottery.

Expressions

Guards are arithmetic. Comparisons yield 1 and 0, and, or, not work on those, and a state name evaluates to its index — so self == firing is a legal and occasionally useful thing to write.

Name	Value at the node being updated
self	Its current state.
age	Steps elapsed since it last changed state.
id	Its index, 0-based.
step	The current time step.
n	The number of nodes.
indeg, outdeg, deg	In-degree, out-degree, and their sum.
in(s), out(s), nbr(s)	How many in-neighbours, out-neighbours, or either, are in state `s`.
fin(s), fout(s), fnbr(s)	The same as a fraction of the relevant degree; zero when the degree is zero.
count(s), frac(s)	The global population of state `s`, as a count and as a fraction of `n`. Global coupling, for mean-field experiments.
rand(), randint(k)	Uniform on [0,1), and a uniform integer in [0,`k`).
if(c, a, b)	Conditional. Both branches are evaluated.
min max abs floor ceil round sqrt exp log sin cos pow clamp mod sgn	The usual arithmetic.

The argument of in() is an ordinary expression, not a keyword, which means in(self) counts the in-neighbours that agree with you — the whole of the voter model in five characters.

Things worth trying

The examples in the dropdown are starting points rather than results. A few suggestions for pulling on them:

Break the symmetry and watch a rule die. Load Life on a Moore torus, change moore to torus, and rebuild. The same rule now reads a two-node in-neighbourhood; gliders are no longer expressible and the population collapses. Life is a statement about its lattice at least as much as about its thresholds.
Add a shortcut. In the excitable ring, raise chord from nothing to a moderate value. Below a threshold the wave circulates forever; above it, the shortcut delivers the excitation into tissue that is still refractory and the wave annihilates itself.
Change only the update order. Take any example and switch update sync to update async. Synchronous updating is a physical assumption — a global clock — and most of the striking patterns in the literature depend on it. Blinkers stop blinking. Waves become fronts.
Reverse the arrows. Add reverse as the last line of a graph block built by scalefree. The hub stops broadcasting and starts listening, and a model of contagion becomes a model of aggregation with no other change.
Look for the sinks. Nodes with out-degree zero are graveyards for activity, and nodes with in-degree zero are unconditional dictators of their own trajectory. Use set s where outdeg == 0 in the init block to find them.

How the interpreter works

The whole thing is roughly nine hundred lines of ordinary JavaScript in the source of this page: view source and read from function lex.The pipeline is the textbook one, kept small enough to read in a sitting. A lexer turns the source into tokens, preserving line and column so that errors can point at something. Newlines survive as tokens, because a statement-per-line rule is what lets ring 30 and chord 11 be two statements rather than one four-argument confusion. A recursive-descent parser reads the block structure and hands expressions to a precedence climber. The result is an abstract syntax tree.

The tree is then compiled to closures: each expression node becomes a JavaScript function of one argument, the evaluation context, and a guard is a single call rather than a walk over a tree. Identifier resolution happens once, at compile time, which is where undefined names and misspelled states are caught. The runtime keeps the graph as two adjacency lists, in and out, and at each node recomputes a small table of how many in- and out-neighbours occupy each state before evaluating that node's guards. That is one pass over the edges per step, which is the right complexity and fast enough that the bottleneck is the drawing, not the automaton.

Randomness runs through one seeded generator, so a program with a seed line is reproducible down to the pixel: the same graph, the same initial condition, the same coin flips. A program without one still gets a fixed default seed, on the theory that an experiment you cannot repeat is an anecdote.