Graph rewriting
Encyclopedia
Graph transformation, or Graph rewriting, concerns the technique of creating a new graph
out of an original graph using some automatic machine. It has numerous applications, ranging from software verification
to layout algorithm
s.
Graph transformations can be used as a computation abstraction. The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph.
Formally, a graph
rewriting
system consists of a set of graph rewrite rules of the form
, with 
being called pattern graph (or left-hand side) and 
being called replacement graph (or right-hand side of the rule). A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph (pattern matching
, thus solving the subgraph isomorphism problem
) and by replacing the found occurrence by an instance of the replacement graph.
Sometimes graph grammar is used as a synonym for graph rewriting system, especially in the context of formal language
s; the different wording is used to emphasize the goal of enumerating all graphs from some starting graph, i.e. describing a graph language - instead of transforming a given state (host graph) into a new state.
. The algebraic approach is divided into some sub approaches, the double-pushout approach (DPO) and the single-pushout approach (SPO) being the most important ones; further on there are the sesqui-pushout and the pullback approach.
From the perspective of the DPO approach a graph rewriting rule is a pair of morphism
s in the category of graphs with total graph morphisms as arrows:
(or 
) where 
is injective. The graph K is called invariant or sometimes the gluing graph. A rewriting
step or application of a rule r to a host graph G is defined by two pushout
diagrams both originating in the same morphism
(this is where the name double-pushout comes from). Another graph morphism 
models an occurrence of L in G and is called a match
. Practical understanding of this is that
is a subgraph that is matched from 
(see subgraph isomorphism problem
), and after a match is found, L is replaced with R in host graph G where K serves as some kind of interface.
In contrast a graph rewriting rule of the SPO approach is a single morphism
in the category labeled multigraphs with partial graph morphisms as arrows:
. Thus a rewriting step is defined by a single pushout
diagram. Practical understanding of this is similar to the DPO approach. The difference is, that there is no interface between the host graph G and the graph G' being the result of the rewriting step.
There is also a more algebraic-like approach to graph rewriting, based mainly on Boolean algebra and an algebra of matrices, called matrix graph grammars.
Yet another approach to graph rewriting, known as determinate graph rewriting, came out of logic
and database theory
. In this approach, graphs are treated as database instances, and rewriting operations as a mechanism for defining queries and views; therefore, all rewriting is required to yield unique results (up to isomorphism), and this is achieved by applying any rewriting rule concurrently throughout the graph, wherever it applies, in such a way that the result is indeed uniquely defined.
Graphs are an expressive, visual and mathematically precise formalism for modelling of objects (entities) linked by relations; objects are represented by nodes and relations between them by edges. Nodes and edges are commonly typed and attributed. Computations are described in this model by changes in the relations between the entities or by attribute changes of the graph elements. They are encoded in graph rewrite/graph transformation rules and executed by graph rewrite systems/graph transformation tools.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
out of an original graph using some automatic machine. It has numerous applications, ranging from software verification
Formal verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...
to layout algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s.
Graph transformations can be used as a computation abstraction. The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph.
Formally, a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
rewriting
Rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. What is considered are rewriting systems...
system consists of a set of graph rewrite rules of the form
, with being called pattern graph (or left-hand side) and being called replacement graph (or right-hand side of the rule). A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph (pattern matchingPattern matching
In computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...
, thus solving the subgraph isomorphism problem
Subgraph isomorphism problem
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H....
) and by replacing the found occurrence by an instance of the replacement graph.
Sometimes graph grammar is used as a synonym for graph rewriting system, especially in the context of formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s; the different wording is used to emphasize the goal of enumerating all graphs from some starting graph, i.e. describing a graph language - instead of transforming a given state (host graph) into a new state.
Graph rewriting approaches
There are several approaches to graph rewriting. One of them is the algebraic approach, which is based upon category theoryCategory theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
. The algebraic approach is divided into some sub approaches, the double-pushout approach (DPO) and the single-pushout approach (SPO) being the most important ones; further on there are the sesqui-pushout and the pullback approach.
From the perspective of the DPO approach a graph rewriting rule is a pair of morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
s in the category of graphs with total graph morphisms as arrows:
(or ) where is injective. The graph K is called invariant or sometimes the gluing graph. A rewritingRewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. What is considered are rewriting systems...
step or application of a rule r to a host graph G is defined by two pushout
Pushout (category theory)
In category theory, a branch of mathematics, a pushout is the colimit of a diagram consisting of two morphisms f : Z → X and g : Z → Y with a common domain: it is the colimit of the span X \leftarrow Z \rightarrow Y.The pushout is the...
diagrams both originating in the same morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
(this is where the name double-pushout comes from). Another graph morphism models an occurrence of L in G and is called a matchPattern matching
In computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...
. Practical understanding of this is that
is a subgraph that is matched from (see subgraph isomorphism problemSubgraph isomorphism problem
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H....
), and after a match is found, L is replaced with R in host graph G where K serves as some kind of interface.
In contrast a graph rewriting rule of the SPO approach is a single morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
in the category labeled multigraphs with partial graph morphisms as arrows:
. Thus a rewriting step is defined by a single pushoutPushout (category theory)
In category theory, a branch of mathematics, a pushout is the colimit of a diagram consisting of two morphisms f : Z → X and g : Z → Y with a common domain: it is the colimit of the span X \leftarrow Z \rightarrow Y.The pushout is the...
diagram. Practical understanding of this is similar to the DPO approach. The difference is, that there is no interface between the host graph G and the graph G' being the result of the rewriting step.
There is also a more algebraic-like approach to graph rewriting, based mainly on Boolean algebra and an algebra of matrices, called matrix graph grammars.
Yet another approach to graph rewriting, known as determinate graph rewriting, came out of logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
and database theory
Database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems....
. In this approach, graphs are treated as database instances, and rewriting operations as a mechanism for defining queries and views; therefore, all rewriting is required to yield unique results (up to isomorphism), and this is achieved by applying any rewriting rule concurrently throughout the graph, wherever it applies, in such a way that the result is indeed uniquely defined.
Implementations and applications
- Tools that are application domain neutral:
- GrGen.NETGrGenGrGen.NET is a graph transformation tool which generates efficient C#-code out of declarative graph rewrite rule specifications....
, the graph rewrite generator, a graph transformation tool emitting C#-code or .NET-assemblies - AGG, the attributed graph grammar system (JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
) - GP (Graph Programs) is a programming language for computing on graphs by the directed application of graph transformation rules.
- GMTE, the Graph Matching and Transformation Engine for graph matching and transformation. It is an implementation of an extension of Messmer’s algorithm using C++C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
.
- GrGen.NET
- Tools that solve software engineeringSoftware engineeringSoftware Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
tasks (mainly MDAModel-driven architectureModel-driven architecture is a software design approach for the development of software systems. It provides a set of guidelines for the structuring of specifications, which are expressed as models. Model-driven architecture is a kind of domain engineering, and supports model-driven engineering of...
) with graph rewriting:- GReATGReATGraph Rewriting and Transformation is a Model Transformation Language for Model Integrated Computing available in the GME environment. GReAT has a rich pattern specification sublanguage, a graph transformation sublanguage and a high level control-flow sublanguage. It has been designed to address...
- VIATRAVIATRAThe VIATRA framework is the core of a transformation-based verification and validation environment for improving the quality of systems designed using the Unified Modeling Language by automatically checking consistency, completeness, and dependability requirements.- Target Application Domains...
- Gremlin, a graph-based programming language (see Graph Rewriting)
- PROGRES, an integrated environment and very high level language for PROgrammed Graph REwriting Systems
- Fujaba uses Story driven modelling, a graph rewrite language based on PROGRES
- GReAT
- Mechanical engineering
- GraphSynth is an interpreter and UI environment for creating unrestricted graph grammars as well as testing and searching the resultant language variant. It saves graphs and graph grammar rules as XMLXMLExtensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....
files and is written in C#. - booggie integrates GrGen.NETGrGenGrGen.NET is a graph transformation tool which generates efficient C#-code out of declarative graph rewrite rule specifications....
with a port-based metamodel definition and an OpenGLOpenGLOpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...
graph visualization based on TulipTulip (software)Tulip is an information visualization framework dedicated to the analysis and visualization of relational data. Tulip aims to provide the developer with a complete library, supporting the design of interactive information visualization applications for relational data that can be tailored to the...
- GraphSynth is an interpreter and UI environment for creating unrestricted graph grammars as well as testing and searching the resultant language variant. It saves graphs and graph grammar rules as XML
- Biology
- Design and implementation of a graph grammar based language for functional-structural plant modeling (other domains: graphics, architecture)
- Artificial Intelligence/Natural Language Processing
- OpenCogOpenCogOpenCog is a project that aims to build an open source artificial general intelligence framework. OpenCog Prime is a specific set of interacting components designed to give rise to human-equivalent artificial general intelligence...
provides a basic pattern matcher (on hypergraphHypergraphIn mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
s) which is used to implement various AI algorithms. - RelEx is an English-language parser that employs graph re-writing to convert a link parseLink grammarLink grammar is a theory of syntax by Davy Temperley and Daniel Sleator which builds relations between pairs of words, rather than constructing constituents in a tree-like hierarchy. There are two basic parameters: directionality and distance...
into a dependency parseDependency grammarDependency grammar is a class of modern syntactic theories that are all based on the dependency relation and that can be traced back primarily to the work of Lucien Tesnière. Dependency grammars are distinct from phrase structure grammars , since they lack phrasal nodes. Structure is determined by...
.
- OpenCog