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:
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.