GGL - the Graph Grammar Library
The GGL (Graph Grammar Library) is an object oriented ANSI C++ library to implement and apply graph rewrite systems. It implements a Double Push Out (DPO) approach. The library is highly modular and uses state-of-the-art algorithms and data structures. To this end, it uses the Boost Graph Library (BGL) for the internal graph representation and efficient (sub)graph isomorphism approaches as the VF2 algorithm.
Beside its general applicability, it features an extensive chemistry module to handle grammar-based graph transformation in Chemistry. Since a chemical reaction can be viewed as graph transformation from the set of educt graphs to the set of product graphs, the GGL can be used to iteratively expand the topology of chemical reaction network, starting from a set of chemical reactions (graph rewrite rules) and set of molecules (vertex and edge labeled graphs) using the general DPO framework of the GGL.
Furthermore, the GGL chemistry module sports efficient cheminformatics algorithms, for instance to estimate reaction rates or a molecule's energy or aromaticity. Furthermore, it comes with a port to the well established Open Babel Library.
- Atom mapping with constraint programming Martin Mann, Feras Nahar, Norah Schnorr, Rolf Backofen, Peter F Stadler and Christoph Flamm. Algo Mol Biol 9:23, (2014).
- The Graph Grammar Library - a generic framework for chemical graph rewrite systems Martin Mann, Heinz Ekker, and Christoph Flamm. In Proc. of International Conference on Model Transformation (ICMT) 2013, LNCS, to appear, (2013).
- In silico Evolution of early Metabolism Alexander Ullrich, Markus Rohrschneider, Peter F Stadler, and Christoph Flamm. Artifical Life 17(2):87-108, (2011).
- Evolution of Metabolic Networks: A Computational Framework Christoph Flamm, Alexander Ullrich, Heinz Ekker, Martin Mann, Daniel Högerl, Markus Rohrschneider, Sebastian Sauer, Gerik Scheuermann, Konstantin Klemm, Ivo L. Hofacker, and Peter F. Stadler. J Sys Chem 1:4, (2010).
- A Graph-Based Toy Model of Chemistry Gil Benkö, Christoph Flamm and Peter F. Stadler. J Chem Inf Comput Sci., 43(4):1085-1093, (2003).
Download and installation
- Boost Library
- Open Babel Library (optionally)
- GNU autotools (if compiling from GIT repository clone)
Release package source code distribution (
The provided source code distributions of the GGL (file names
are autotools generated packages ready for the standard compilation-installation
tar -xzf ggl-VERSION.tar.gz cd ggl-VERSION ./configure # call with '--help' for configure options make make install # call with 'prefix=INSTALLPREFIX' for local installation
Clone or Source from github
The source files hosted on github (and available as
Source.zip from the release
pages) have to be preprocessed with autotools to enable the
standard compilation-installation pipeline:
source ./autogen.sh # calls autotools, see content for details ./configure # call with '--help' for configure options make make install # call with 'prefix=INSTALLPREFIX' for local installation
The package comes with separate libraries described in the following. Furthermore, generic binaries are compiled that directly enable graph rewrite applications.
SGM - Sub Graph Matching
A library to solve the subgraph-isomorphism problem based on different approaches.
Graph_Interface: an abstract graph interface used by the matching algorithms
SubGraphMatching: an abstract interface of sub graph matching algorithms
Match_Reporter: an abstract interface to handle a found match
Graph_Interfaceimplementation wrapping around a boost graph
Graph_Interfaceimplementation wrapping around a set of boost graphs to be represented as one graph with independent components
SGM_vf2: a VF2-lib based
Match_Reporterthat writes each reported match to stream
GGL - Graph Grammar Library
A library to formulate and solve context sensitive graph grammars.
Graph: a labeled undirected boost graph used for grammar targets
Rule: a graph grammar rule encoding based on an undirected labeled BGL graph
sgm::Match_Reporterimplementation that applies a rule onto a matched subgraph that was identified by a
Graph_Storage: an abstract interface that is used by
MR_ApplyRuleto report the newly generated graphs that are the result of a grammar rule application
sgm::Graph_Interfacewrapper around a Graph for SGM usage
sgm::Graph_Interfacewrapper around a Rule for SGM usage
Graph_Storageimplemenation that writes all reported graphs to stream
Rule_GML_grammar: a parser grammar definition for GML encoded rule parsing
GGL-CHEM - GGL Chemistry
A library to formulate chemical reactions on molecule graphs using graph grammar rules.
Molecule: a labeled undirected boost graph used for molecule graph representation
SMILES_grammar: a parser grammar defintion for Daylight's SMILES molecule string representation parsing
SMILESwriter: a writer to encode molecule graphs in canonical SMILES strings. Note: the write is incomplete, i.e. only handles a few types of atoms
ggl::Graph_Storageimplementation that rewrites each generated Molecule into a SMILES string and adds it into an STL container