My #procjam project: Soffit

As usual, my #procjam project is way too ambitious for what I can actually get done in a work week, particularly one where I'm out at headquarters in California.

I'm trying to build a graph grammar engine which is as easy to use, as Tracery is for context-free string grammars. I named the project Soffit in keeping with the architectural theme.

Github repository: https://github.com/mgritter/soffit

To date I've mainly been working on the input format and parser. I wanted a text representation of graphs that was easy to write, so I basically copied Dot.

A--B represents a bidirectional edge between vertices A and B.

A--B [x] applies a tag to that edge.

A[12]; B[34]; A->B defines two tagged vertices, with a directed edge between them. (In a departure from Dot format, the arrow can be drawn in either direction, so B<-A->C is a valid graph.

A more complicated example, rendered in matplotlib:

A[1]; A--B [x]; B--C [y]; C->A [z]; A[1]; B[23]; B--Q; Q[4];

A grammar can then be represented as a JSON object mapping graphs to graphs. As in Tracery a list of options can be used on the right-hand side if a graph may be transformed in more than one way.

{
  "version" : "0.1",
  "start" : "A--B",
  "A--B" : "A--B--C; B--D",
  "A--B--C--D" : [ "A--B--C--D--A", "A--B; C--D;" ]
}

I had to invent a notation for transformations that merge nodes. I chose to use "A^B" to indicate that, for example "A--B--C" : "A^B-C, A--D" means to map nodes A and B to the same node in the output graph (and the delete the edge between them.) Subsequent appearances of A or B in the grammar refer to this merged node, or the user can specify "A^B" everywhere. "AvB" would be better mathematically, but I wanted to permit "v" in node identifiers (which need not be single-letter capitals as I have used them here, but it seems a good convention.) It's certainly not easy to typeset the correct join operator.

My library is written in Python and depends on:

• pyparsing, a lightweight parsing library
• networkx for storing graphs

It would be more in keeping with the spirit of Tracery to have a Javascript implementation, but I think that would be challenging.

Next steps:

• Identify valid matches for the left-hand graph inside a rule. I'm planning to use ortools for that.
• Perform the graph rewriting!
• Run the rule set for a given number of iterations, generate an animation?
• Output to graphviz. I plan to have a way to convert tags to graphviz attributes for display.