My library finally performed a graph rewrite today! Still a ways from a "launch" version, but the core of the engine works, at least in a simple case.
Repository: https://github.com/mgritter/soffit
As of this commit I have a unit test which successfully applies a graph rewrite rule.
Left hand of rule: Two nodes tagged "left" and "right" with an edge between them.
A[left]; B[right]; A--B
Right hand of rule: Unlabel "left", change "right" to "left", and add a new "right" with an edge connecting it to the existing chain.
A; B[left]; C[right]; A--B--C
Test case: X[left]; Y[right]; Z[head]; Z--X--Y
The engine uses its own graph numbering instead of preserving the names in the original graph; I don't know if I'll keep this or not. The debug output shows the renumbered graph, the match of A and B to nodes in that graph, and then the result of the transformation:
*** BEFORE ***
0 [left];
1 [right];
2 [head];
0 -- 1;
0 -- 2;
{ B=>1, A=>0 }
*** AFTER ***
0;
1 [left];
2 [head];
3 [right];
0 -- 1;
0 -- 2;
1 -- 3;
i.e., the new graph is 2 (head) -- 0 -- 1 (left) -- 3 (right)