Controlling graph grammar expansion with a countdown

Let's create a graph grammar with Soffit that generates a fixed-sized binary tree.

How do we tell a graph grammar when to stop working? One option is to only run it for a fixed number of iterations, but that's pretty unsatisfying and fragile. If we have any rules that don't create new nodes, then the size of the tree will not be fixed.

Instead, we can use extra nodes in the graph as a countdown timer telling us how much work remains. Each time we do one unit of "work" (in this case, expanding the binary tree), then we delete one of the nodes.

"<left rule>; X[timer];" : "<right rule>" will work. However, this is a little inefficient because Soffit finds all possible matches and picks one, and X will have a lot of possible matches.

One way to restrict this is to put the countdown nodes all in a line, and take only from one side. As an added advantage, this gives us the ability to specify a rule that should fire when the countdown nodes are used up.

  0 -- 1 -- 2 -- 3 -- 4 -- 5
[fuse]                    [end]

In Soffit:

"; X[fuse]; X2; X--X2" : 
     " X2[fuse];",
"F[fuse]; E[end]; F--E;" : 
     ""

Here's an example that creates binary trees with exactly 11 leaves:

{
    "version" : "0.1",
    "start" : "X[root]; N1[node]; N2[node]; X--N1; X--N2; Y0[fuse]; Y0--Y1--Y2--Y3--Y4--Y5--Y6--Y7--Y8--Y9--Y10; Y10[end]",
    "F[fuse]; E[end]; F--E" : "Z [style=invis]",
    "R[node]; Y[fuse]; Y--Y2" : "R--I1; R--I2; R[label=]; I1[node]; I2[node]; Y2[fuse];",
    "R[node]; Z[style=invis];" : "R[leaf]; Z[style=invis]"
}