Skip to content

jar2333/GRE.NET

Folders and files

NameName
Last commit message
Last commit date

Latest commit

7ba7944 · Apr 13, 2022

History

64 Commits
Oct 10, 2021
Apr 13, 2022
Oct 10, 2021
Jul 16, 2021
Jul 26, 2021
Jul 11, 2021
Aug 10, 2021
Oct 10, 2021
Oct 10, 2021
Jul 16, 2021
Jul 16, 2021
Jul 27, 2021
Jul 16, 2021
Jul 25, 2021
Apr 13, 2022
Jul 27, 2021
Oct 10, 2021
Oct 10, 2021
Apr 13, 2022
Apr 13, 2022

Repository files navigation

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:

  1. Implement grammar rule parser/serialization
  2. Implement Probabilistic Graph Grammars and Probabilistic Rewriting
    • M. Mosbah (1996), Probabilistic Graph Grammars
  3. Optimization and cleanup
  4. 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