Generated on Wed Apr 29 2015 11:51:41 for GGL-4.1.2 by doxygen
GGL - Graph Grammar Library
GGL - 4.1.2

This document provides reference information about the Graph Grammar Library.

The goal

This C++ programming library provides a platform for the formulation and application of context sensitive graph grammars on arbitrary labeled graphs.

It is split into several sub-libraries to achieve a high level of modularity.


GGL - Graph Grammar Library

The GGL collects the necessary interfaces and core functionalities to enable the formulation of graph grammar rules and their application. Therefore, the algorithms use the sgm::Graph_Interface to enable the independence of the concrete graph implementation used. The rule definition is currently based on BGL graphs which allows for a high level of flexibility (see Dependencies) All classes and functions are templated to maintain the flexibility of the boost graphs.

The GGL is extended by the GGL-CHEM library (see GGL-CHEM - GGL Chemistry) for the application of graph grammars to chemical molecules and reactions.

The application of graph grammar rules is based on the detection of subgraph isomorphisms. This is done using the SGM library.

SGM - Subgraph Matching Library

The SGM library provides a generic interface for graph or subgraph isomorphism algorithms. A graph handled by the SGM has to implement the sgm::Graph_Interface. A templated wrapper class for BGL graphs is provided. Furthermore, graphs that serve as patterns have to provide the extended sgm::Pattern_Interface interface.

A first implementation of a subgraph matcher is done based on the VF2 library. The VF2 algorithm is the state-of-the-art algorithm for this objective. We integrated the VF2 library source into the package to reduce the dependencies of the package. See the vflib2* folder in the source directory.

GGL-CHEM - GGL Chemistry

This library extends the GGL with classes to represent chemical molecules as BGL graphs. The molecules are read and written in the standard Daylight's SMILES format. The graph grammar rules specify valid chemical reactions that modify molecules.

GGL Tools

Based on the GGL we have set up several tools for a direct application of the library.


The GGL depends on the following libraries:

Optionally one can extend the function volume of GGL-CHEM using


Additionally, the documentation also features the following parts:

The following lists and indices are available