Home Page

GMTE: The Graph Matching and Transformation Engine Presentation

GMTE (protected by a CNRS Licence DL 03998-02), the graph matching and transformation engine is an efficient tool we have been implementing in C++ since a decade now. It is an efficient implementation of an extension of Messmer’s algorithm. Our experiments show that the tool is capable of searching small and medium graph patterns in huge graphs in a short time. A computational complexity analysis of our algorithm has conducted and performant experimental results are obtained.We have also shown that, when only constant labels are considered, this complexity is similar to the complexity of Ullmann’s algorithm . Both pattern graph (called rule graph) and host graph have labelled nodes and edges. The rule graph labels may be totally or partially instatiated. Unification is conducted for non-instantiated labels. The tool can be used non-interactively as a C++ library providing a function that can be invoked from either a C++ or a Java main program. The tool can be used through as a C++ executable that reads rule graph and host graph description from input TXT or XML files.

General Presentation

The approach ACG (Abstract Graph Component) that we use is based on graphs and coordination rules to describe the dynamic evolution of architectures. It is also used to simulate the different instantiation component stages, behaviour change during implementation, migration, and other characteristics specific to the distributed systems software architecture.

We propose to model the architecture by an architecture graph (AG), and manage its evolution by the management architecture protocol (GAP). The nodes AG describe software components, and edges describe the dependence relationship between these components. The rules that guide the dynamic evolution are modelled as graphs called rule graphs

(RG) partitioned into four zones that determine the rule application and the changes that occur when a rule is applicable.

We distinguish: :

  1. The Inv zone: representing a fragment of the RG which must be identified (by homomorphism) in the GA, if several subgraphs are homomorphic to this area, a subgraph is chosen randomly;
  2. The Abs zone: representing a fragment of RG (containing the fragment Inv) which must do not exit (by homomorphism) in the AG for the rule is applicable;
  3. The Del zone: is under a fragment of the Inv zone that will be deleted on the application of the rule;
  4. The Add zone: is the fragment that will be added after the application of the rule.

The protocol management architecture PGA involves coordinating events occurring in the system to the rule of coordination RC (or combination of coordination rules) to be applied to transform architecture. The management architecture protocol involves coordinating events occurring in the system to the rule of coordination RC (or combination of coordination rules) to be applied to transform architecture.

Paper clips
Paper clips