Graph replacement system

Example for graph replacement rule (optimization from the compiler construction: multiplication by 2 replaced by addition)

Graph replacement systems are used for the formal description of changing graphs . They are often implemented with computer programs and thus made executable and applicable.

A graph replacement system is a set of graph replacement rules . A graph replacement rule consists of the sample graph on the left and the replacement graph on the right. ${\ displaystyle M}$ ${\ displaystyle p \ colon L \ rightarrow R}$ ${\ displaystyle p}$ ${\ displaystyle L}$ ${\ displaystyle R}$

A rule is applied in a direct derivation , the work graph is before the rule application, the modified work graph afterwards. A rule application consists of finding an instance of in ( pattern matching , here: subgraphs - isomorphism ) and replacing the instance found by an instance on the right-hand side . A derivation is a series of rule applications that transform an output graph into a resulting graph. ${\ displaystyle p}$ ${\ displaystyle G {\ xrightarrow {p}} H}$ ${\ displaystyle G}$ ${\ displaystyle H}$ ${\ displaystyle L}$ ${\ displaystyle G}$ ${\ displaystyle R}$

If the focus shifts from changing a given graph to generating all graphs that can be derived from a start graph, we speak of graph grammar instead of a graph replacement system and of productions instead of rules. The union of the graphs resulting from systematic enumeration is the language of graph grammar. In addition, the graph elements are usually divided into non-terminals and terminals, and only the non-terminals are replaced; the language is then only understood to mean the terminal graphs that can be derived.

Well-formedness of graphs is often defined in terms of its inclusion in the language of context-free graph grammar. A given graph can then be checked for well-formedness with a graph parser, which calculates whether it is contained in the language of graph grammar; if successful, its derivation (s) are also obtained.

Graph replacement systems can (also) be viewed as a generalization of the term replacement systems of (basic) terms / their trees on graphs.

Algebraic approach

Most important in the specification of graph replacement systems is the algebraic approach, which was developed with the aim of generalizing Chomsky grammars of words on graphs . Finding an instance is defined by determining a fit graph homomorphism of in , replacing it with the construction of a single or double pushout . ${\ displaystyle m}$ ${\ displaystyle L}$ ${\ displaystyle G}$

Graph

Graphs in the sense of the algebraic approach are formally modeled as follows: a graph consists of two sets of supports and , the corners and edges of the graph, as well as two images that define the corners at which the edges begin and end. Often the corners and edges are labeled, with the definition of the graph then supplemented by two functions that map corners and edges onto suitable symbols. ${\ displaystyle G = (E, K, b, e)}$ ${\ displaystyle E}$ ${\ displaystyle K}$ ${\ displaystyle b, e \ colon K \ rightarrow E}$

These are so-called directed multigraphs with loops, structures made up of nodes (corners) and directed edges (arrows) that can be drawn as diagrams. They can be used in computer science to formalize data structures, processes, etc. This particular variation of graphs is particularly consistent with the graphical representation of categories . In the literature on graph grammar, categorical terms are preferred.

Graph homomorphisms

The semantics of the replacement rules are explained with the help of graph homomorphisms, these are structure-retaining mappings between graphs. A graph homomorphism maps a graph onto a graph in such a way that nodes can only be combined if the edges are also combined appropriately. Formally it consists of two functions and , in such a way that: ${\ displaystyle \ phi \ colon G \ rightarrow H}$ ${\ displaystyle G}$ ${\ displaystyle H}$ ${\ displaystyle \ phi}$ ${\ displaystyle \ phi _ {E} \ colon E_ {G} \ rightarrow E_ {H}}$ ${\ displaystyle \ phi _ {K} \ colon K_ {G} \ rightarrow K_ {H}}$

${\ displaystyle b_ {H} \ circ \ phi _ {K} = \ phi _ {E} \ circ b_ {G}}$
${\ displaystyle e_ {H} \ circ \ phi _ {K} = \ phi _ {E} \ circ e_ {G}}$

Replacement

In the definition of replacing the actions of the construction of a simple will push outs (single pushout, SPO) distinguished from the construction of a double push-outs (Double pushout, DPO).

Double pushout diagram

The connection between and in the DPO is established by a sticky graph and two graph homomorphisms and . In the replacement step the elements from are retained, those from are deleted, those from are added. ${\ displaystyle L}$ ${\ displaystyle R}$ ${\ displaystyle K}$ ${\ displaystyle l \ colon K \ rightarrow L}$ ${\ displaystyle r \ colon K \ rightarrow R}$ ${\ displaystyle K}$ ${\ displaystyle L \ setminus K}$ ${\ displaystyle R \ setminus K}$

Single pushout diagram

In the SPO, on the other hand, the relationship between and is established by a partial graph homomorphism . In the replacement step, related elements are retained, the unrelated elements are deleted, the unrelated elements are added. ${\ displaystyle L}$ ${\ displaystyle R}$ ${\ displaystyle r \ colon L \ rightarrow R}$ ${\ displaystyle r}$ ${\ displaystyle L}$ ${\ displaystyle R}$

Two conflicts can arise when replacing:

A sample node to be deleted and a sample node to be retained are mapped to the same work graph node; it is not clear whether it should be deleted or retained. (Note: graph homomorphism, not necessarily injective)
A node to be deleted is connected to the rest of the work graph with edges that are not specified in the sample graph; after deleting the node alone, work graph edges would hang in the air.

The rule application in the DPO is described by the construction of two pushouts, which is not possible in the two conflict cases, so that the rule cannot be applied in these cases.

The rule application in the SPO is described by the construction of a pushout, which means that in the 1st case deletion has priority over preservation, and in the 2nd case edges hanging in the air are deleted.

Alternative definitions

Other approaches within the algebraic approach are the Sesqui pushout and pullback approaches.

Less powerful, context-free formulations of graph replacement (outside of the algebraic approach) are node replacement and hyperedge replacement. In the case of node replacement, the pattern consists of only one node ; the replacement graph is connected to the instance of neighboring ( adjacent ) nodes using connection instructions . With hyperedge replacement, the pattern consists of only one hyperedge ; the replacement graph is glued to the ( incident ) nodes that were attached to the instance before the rule was applied . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle e}$ ${\ displaystyle e}$

Application of graph substitution

While graph theory in mathematics considers graphs and their properties (such as colorability ), and graph theory in theoretical computer science focuses its attention on graph replacement systems and their properties ( e.g. confluence ), practical computer science focuses on the provision of efficient graph replacement systems Foreground, which are used in the context of applied computer science for modeling data in the form of graphs and the specification of calculations on the graph by graph replacement rules.

Graphs are to be illustrative, mathematically precise and expressive formalism for modeling in relation stationary objects (entities) in which objects are generally coded to nodes and the relationships represented by edges. Different objects and relationships are expressed by different node and edge types; depending on the types, the graph elements can also be provided with attributes . In this model, calculations are represented by changing the relationships between the objects, but also by changing the attributes. They are described by graph replacement rules.

In practice, there is a stronger, more algorithmic control of the rule application than the indeterministic concept of the pure graph replacement system, which controls the indeterminism of the rule (which rule from the rule set is used?) And the indeterminism of the location (at which point in the work graph is the rule applied ?). The next rule to be applied can be determined via control constructs such as sequence, alternative or iteration (depending on the success or failure of the previous rule application), or the processing of a common approach can be ensured by passing parameters between the rules. It is then referred to as "programmed graph replacement".

Graphs can be found implicitly in the form of mapped structures (objects = nodes, references / pointers = directed edges) in every major program. If objects, in particular patterns of interconnected objects, are to be searched for and replaced, it is worthwhile to make them explicit by using a graph replacement system; you can then work with short, declarative graph replacement rules instead of extensive, hand-programmed search and replacement subroutines.

Graph replacement systems focus on the pattern-based processing of graphs in main memory, in contrast to graph databases , which are developed with the aim of persistent storage in transaction-safe multi-user operation.

Application examples

Software technology : Model-driven software development with UML graphs

Compiler construction : Optimizations on graph-based intermediate code

Biology, graphics

Product development, product configuration, systems engineering

General graph replacement systems

Systems based on graph replacement

Triple graph grammar ( model transformation )
Fujaba ( visual programming , model transformation )

literature

G. Rozenberg (Ed.): Handbook of Graph Grammars and Computing by Graph Transformation . 3 volumes. World Scientific Publishing, Singapore a. a. 1997-1999.