Graph transformation, or
Graph rewriting, concerns the technique to create a new
graphIn 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 to layout
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
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.
Graph transformation, or
Graph rewriting, concerns the technique to create a new
graphIn 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 to layout
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
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
graphIn 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...
rewritingIn 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 matchingIn computer science, pattern matching is the act of checking for the presence of the constituents of a given pattern. In contrast to pattern recognition, the pattern is rigidly specified. Such a pattern concerns conventionally either sequences or tree structures...
, thus solving the
subgraph isomorphism problemIn 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 languageA formal language is a set of words, i.e. finite strings of letters, symbols, or tokens. The set from which these letters are taken is called the alphabet over which the language is defined...
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 theoryIn mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from sets and functions to objects linked in diagrams by morphisms or arrows....
. 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 morphismIn mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures.The study of morphisms and of the structures over which they are defined, is central to category theory...
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 rewritingIn 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 pushoutIn 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 .The pushout is the categorical dual of the...
diagrams both originating in the same morphismIn mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures.The study of morphisms and of the structures over which they are defined, is central to category theory...
(this is where the name double-pushout comes from). Another graph morphism models an occurrence of L in G and is called a
matchIn computer science, pattern matching is the act of checking for the presence of the constituents of a given pattern. In contrast to pattern recognition, the pattern is rigidly specified. Such a pattern concerns conventionally either sequences or tree structures...
. Practical understanding of this is that is a subgraph that is matched from (see
subgraph isomorphism problemIn 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
morphismIn mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures.The study of morphisms and of the structures over which they are defined, is central to category theory...
in the category labeled multigraphs with partial graph morphisms as arrows: . Thus a rewriting step is defined by a single
pushoutIn 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 .The pushout is the categorical dual of 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, called
matrix graph grammars. This topic is expanded at
mat2gra.info.
Yet another approach to graph rewriting, known as determinate graph rewriting, came out of
logicLogic, from the Greek λογική is the art and science of reasoning. More specifically, it is defined by the Penguin Encyclopedia to be "The formal systematic study of the principles of valid inference and correct reasoning". As a discipline, logic dates back to Aristotle, who established its...
and
database theoryDatabase 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
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.
- Tools that are application domain neutral:
- 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
XML is a set of rules for encoding documents electronically. It is defined in the produced by the W3C and several other related specifications; all are fee-free open standards....
files and is written in C#.
- GrGen.NET
GrGen.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 (Java
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...
)
- Tools that solve software engineering
Software 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 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:
- GReAT
Graph 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...
- VIATRA
The 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...
- Fujaba uses Story driven modelling, a graph rewrite language based on PROGRES
- Biology