项目作者： jar2333
项目描述 ：
simple labelled graph rewriting for .NET
高级语言： C#
项目地址: git://github.com/jar2333/GRE.git
GRE: Graph Rewrite Engine
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:
1) 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
2) Implement Graph Grammars and Graph Rewriting (in progress) - B. König et al (2018), A Tutorial on Graph Transformation
LATER:
3) Implement grammar rule parser/serialization
4) Implement Probabilistic Graph Grammars and Probabilistic Rewriting
- M. Mosbah (1996), Probabilistic Graph Grammars
5) Optimization and cleanup
6) 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:
