An engine for simple labelled graph rewriting.
Provides interfaces for implementing subgraph isomorphism algorithms
Included is VF2++ (Jüttner and Madarasi, 2018) https://www.sciencedirect.com/science/article/abs/pii/S0166218X18300829
For the purposes of graph transformation, all morphisms are assumed to be injective. The included VF2 modules produce such morphisms. This assumption may change in the future.
Currently functional:
- naive VF2 Induced Subgraph matching (partially implemented, edge labels not preserved)
- Graph Rewriting through Rewriter objects (functional, not optimized, not all cases tested)
Roadmap:
IN PROGRESS:
- Implement VF2++ fully (in progress)
- L. P. Cordella et al (2004), A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs
- C. Vincenzo et al (2015), VF2 Plus: An Improved version of VF2 for Biological Graphs
- A. Jüttner and P. Madarasi (2018), VF2++—An Improved Subgraph Isomorphism Algorithm
- Implement Graph Grammars and Graph Rewriting (in progress)
- B. König et al (2018), A Tutorial on Graph Transformation
LATER:
- Implement grammar rule parser/serialization
- Implement Probabilistic Graph Grammars and Probabilistic Rewriting
- M. Mosbah (1996), Probabilistic Graph Grammars
- Optimization and cleanup
- First NuGet release
A future extension package for Probabilistic Edge Replacement Grammars (PERGs) is possible in the future:
- Grammar construction and production weight learner classes
- T. Oates et al (2003), Estimating Maximum Likelihood Parameters for Stochastic Context-Free Graph Grammars
- Aguinaga et al (2016), Growing Graphs from Hyperedge Replacement Graph Grammars
- Wang et al (2018), Growing Better Graphs With Latent-Variable Probabilistic Graph Grammars
- Reddy et al (2019), Edge Replacement Grammars: A Formal Language Approach for Generatign Graphs
- Production weight solver classes given graph property probabilities (linear and nonlinear systems of equations)
- B. Courcelle (1990), Graph Rewriting: An Algebraic and Logic Approach
- M. Mosbah (1996), Probabilistic Graph Grammars
Dependencies:
- QuikGraph 2.3.0