Suppose we want to create a graph grammar that makes rectangular grids.
A first cut at it would be something like "expand outwards from any edge that hasn't already been used", something like this:
o-o o-o-o
| | => | | |
o-o o-o-o
with the appropriate tags used to keep track of whether we already expanded or not. The problem with this is that while it's locally correct (everything is a square) it's not globally correct. The toplogy is all wrong, so even if we had the rules to stitch things together, it wouldn't fit.
Instead, we need a design where there is only one rule that can be applied at any given time, and this rule maintains invariants that preserve global structure. (This strips out most of the point of using a graph grammar and makes it more like a conventional programming language, but I should at least be able to demonstrate that it's possible.)
My idea here is to work on just one edge at a time, with a "mouse" (or turtle, if you prefer) adding squares on until it reaches the end, then turning the corner to work on the next edge. I mark the nodes "e" for one on the boundary of the grid, "c" for the corners, and "i" for internal nodes.
c-------c
| | | | |
v-e-i-i--
| | | |
e------
| | | |
c------
c-------c (moving down)
| | | | |
e-i------
| | | | |
v-e------
| | | |
c------
c-------c (down again)
| | | | |
e-i------
| | | | |
e-i------
| | | | |
v-c------
c-------c (turn the corner)
| | | | |
e-i------
| | | | |
e-i------
| | | | |
e-e------
| |
c->
Here's the Soffit grammar which implements this design:
{
"version" : "0.1",
"start" : "X->Y->Z [h]; X2->Y2->Z2 [h]; X->X2 [v]; Y->Y2[v]; Z->Z2[v]; X[c]; Y[c]; Z[up]; X2[c]; Y2[e]; Z2[c]",
"C->M [h]; C[c]; M[up];" :
"C->M [h]; C[e]; M[e]; A[left]; B[c]; A->B [h]; A->C[v]; B->M[v];",
"M->R [v]; L->R [h]; L[e]; R[e]; M[left];" :
"M->R [v]; L->R [h]; L[e]; R[i]; M[e]; N[left]; N->M[h]; N->L[v];",
"M->R [v]; L->R [h]; L[c]; R[e]; M[left];" :
"M->R [v]; L->R [h]; L[c]; R[i]; M[e]; N[left]; N->M[h]; N->L[v];",
"M->C [v]; C[c]; M[left];" :
"M->C [v]; C[e]; M[e]; A[c]; B[down]; A->M[h]; A->B[v]; B->C[h];",
"M->T [h]; T->B [v]; T[e]; B[e]; M[down];" :
"M->T [h]; T->B [v]; T[i]; B[e]; M[e]; N[down]; M->N[v]; N->B[h];",
"M->T [h]; T->B [v]; T[e]; B[c]; M[down];" :
"M->T [h]; T->B [v]; T[i]; B[c]; M[e]; N[down]; M->N[v]; N->B[h];",
"M->C [h]; C[c]; M[down];" :
"M->C [h]; C[e]; M[e]; A[c]; B[right]; M->A[v]; A->B[h]; C->B[v];",
"M<-L [v]; L->R [h]; L[e]; R[e]; M[right];" :
"M<-L [v]; L->R [h]; L[i]; R[e]; M[e]; N[right]; M->N[h]; R->N[v];",
"M<-L [v]; L->R [h]; L[e]; R[c]; M[right];" :
"M<-L [v]; L->R [h]; L[i]; R[c]; M[e]; N[right]; M->N[h]; R->N[v];",
"C->M [v]; C[c]; M[right];" :
"C->M [v]; C[e]; M[e]; A[up]; B[c]; M->B[h]; C->A[h]; A->B[v];",
"B->M [h]; T->B [v]; T[e]; B[e]; M[up];" :
"B->M [h]; T->B [v]; T[e]; B[i]; M[e]; N[up]; T->N[h]; N->M[v];",
"B->M [h]; T->B [v]; T[c]; B[e]; M[up];" :
"B->M [h]; T->B [v]; T[c]; B[i]; M[e]; N[up]; T->N[h]; N->M[v];"
}
And here's what it looks like after 40 iterations:
(Graphviz isn't smart enough to know which orientation I wanted.)
From working on examples, here's a few things I've been thinking of adding: