4

I'm interested in a library for:

  • Representing graph rewriting rules
  • Representing formal grammars relating to graphs
  • (Low priority:) representing graph automata
  • (Low priority:) Running graph automata on a given graph
  • Quickly applying rewriting rules to a graph, once-off and repeatedly

It does not matter whether the library represents graphs itself or whether it relies on an external library, or the user, for that representation

The library should support:

  • Directed and undirected graphs
  • Simple and multigraphs
  • Edge and vertex labels and colors, preferably of multiple kinds

The programming language should be, in order of decreasing preference:

  • Modern C++ (i.e. C++11 and later)
  • old(ish) C++
  • Anything else

License:

  • Does not need to go into commercial code
  • Preferably something I can create derived work from and include elsewhere in code
  • Less preferably, something I can link against

Price Limit: Must be freely available for download.

1

Graph grammars and rewriting have long been a hot topic in German academic organizations.

The most practical tool I know about for this is Andy Schurr's PROGRES: PROgrammed Graph REwrite Systems. This was work done in the late 1980s/early 1990s and looked like it was reasonably mature.

I've read the papers and it all sounds great; but I have no personal experience. Poking around the web it is unclear if this project is still active, and/or where you can obtain the tool, if you can obtain it all.

[I have experience with AST rewriting systems, used to judge the utility of this].

Wikipedia lists a variety of graph rewriting engines, one of which is PROGRES. I know little about the others.

protected by Undo Mar 28 '16 at 15:17

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.