G³: Geometric Graph Grammar ToolChain

What it does

A Geometric Graph Grammar (GGG) encodes both topology and 2D/3D geometry. Learning works like data compression on graphs: find frequently repeated, geometrically-isomorphic subgraphs (“isogroups”), replace each occurrence with a single node, and emit a rewriting rule — repeated hierarchically to build a compact, generative description of the input.

Demo (2D Python)

Forward — apply a recursive grammar to generate a fractal (the paper's Fig. 12 Sierpinski triangle); inverse — feed that fractal back and induce a grammar that recovers the recursive triangle hierarchy, colour-coding each occurrence.

cd src/g3-2d/python
pip install -e ".[dev,viz]"

# forward: generate the Sierpinski triangle
python -m g3_2d.examples sierpinski -n 6 -o sierpinski.png

# round-trip: induce a recursive triangle grammar back from a generated fractal
python -m g3_2d sierp4.json -o sierp4.ggg.json --draw sierp4.png --max-order 3 --prefer dense

The induction prints an analysis report (isogroup counts, per-rule table, compression %), writes the grammar as *.ggg.json, and draws the occurrences.

Syntax analysis — parse a geometry against a grammar

The recognition counterpart of learning: given a geometry and a grammar, reduce the geometry by the grammar's rules step by step — recording the derivation (which rule fired where) — then replay it in reverse to regenerate the geometry exactly. On the depth-4 Sierpinski fractal, 123 vertices collapse to a single axiom node in 8 steps:

Replaying the derivation in reverse reconstructs the original fractal exactly (matches input: True).

Real-world maps — African settlements

Ron Eglash's African Fractals documents the recursive, self-similar organization of indigenous African settlements. This toolchain detects exactly that kind of repeated geometric structure, so we can point it at a real settlement: import an OpenStreetMap road/path network, train a grammar on it, and analyze it. The example uses the old walled Hausa city of Kano, Nigeria.

The tolerance knob is the story. Organic streets don't repeat exactly; loosening the geometric tolerance reveals the approximate, scale-invariant self-similarity Eglash describes — the dominant 3-junction motif repeats 10× at 5% tolerance but 80× at 30%. The grammar explains the entire patch (322 junctions → 1 node in 9 steps), and replaying the derivation rebuilds the original map exactly — the analysis loses nothing.

Map data © OpenStreetMap contributors (ODbL). Presets include kano-old-city, fez-medina, marrakesh-medina, accra-jamestown, plus barcelona-eixample and manhattan-midtown.

Time series — EEG phase-space reconstruction

A geometric graph doesn't have to be a map. A scalar time series becomes 2D geometry through phase-space reconstruction (Takens time-delay embedding): plot each sample against a delayed copy and join consecutive points into a trajectory. The shape of that trajectory is the signal's attractor — and recurring waveform patterns become recurring loops, exactly the repeated structure the grammar detects. Here: a real EEG channel (PhysioNet, eyes-closed occipital electrode Oz), band-passed to 4–30 Hz.

Because the isomorphism is scale-invariant, loops of different amplitude are the same shape, so the learner finds a recurring order-3 arc motif (here it repeats 32×). The hierarchical grammar then reduces the whole 500-point trajectory to a single node in 9 steps:

Replaying the derivation reconstructs the original trajectory exactly (matches input: True).

Repository layout

docs/                     Paper + algorithm notes (the conceptual reference)
src/
  g3-2d/                  2D geometric graph grammars
    python/               Python implementation   ← current focus
    cpp/                  C++ implementation
  g3-3d/                  3D geometric graph grammars
    python/  cpp/
LICENSE                   MIT (© Serendip Commons Society)

There are four parallel implementations (2D/3D × Python/C++). The 2D dimension is being designed and built first, beginning with the Python implementation; the others follow.

Status

• 2D Python — functional end to end: forward generation (fractals) and inverse learning (detection → selection → encoding → hierarchical rewriting), with analysis reports and visualization.
• 2D C++, 3D Python, 3D C++ — planned; the 2D-Python module and shared fixtures are the specification they validate against.

Beyond graphs — higher-dimensional grammars (planned)

A research direction takes the 2-simplex (triangle) as the generative primitive and climbs dimension by gluing (k-simplices → (k+1)-simplices), aiming at one dimension-agnostic engine, plus a conjecture that m-D induction reduces to repeated 2-complex problems. It also bridges to simplicial physics — spin foams are labelled 2-complexes, and production rules correspond to Pachner moves (cf. CDT, Regge calculus, tensor models). This is the methodological bridge from graph-theoretic geometry to field-theoretic spacetime named in the project's approval.