Hubbry Logo
Graph rewritingGraph rewritingMain
Open search
Graph rewriting
Community hub
Graph rewriting
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Graph rewriting
Graph rewriting
Graph rewriting
View on Wikipedia
from Wikipedia

In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also software verification) to layout algorithms and picture generation.

Graph transformations can be used as a computation abstraction. The basic idea is that if 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 usually 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. Rewrite rules can be further regulated in the case of labeled graphs, such as in string-regulated graph grammars.

Sometimes graph grammar is used as a synonym for graph rewriting system, especially in the context of formal languages; the different wording is used to emphasize the goal of constructions, like the enumeration of all graphs from some starting graph, i.e. the generation of a graph language – instead of simply transforming a given state (host graph) into a new state.

Graph rewriting approaches

[edit]
Top: Example graph rewrite rule (optimization from compiler construction: multiplication with 2 replaced by addition). Bottom: Application of the rule to optimize "y=x*2" into "y=x+x".

Algebraic approach

[edit]

The algebraic approach to graph rewriting is based upon category theory. The algebraic approach is further divided into sub-approaches, the most common of which are the double-pushout (DPO) approach and the single-pushout (SPO) approach. Other sub-approaches include the sesqui-pushout and the pullback approach.

From the perspective of the DPO approach a graph rewriting rule is a pair of morphisms in the category of graphs and graph homomorphisms between them: , also written , 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 , where D is a context graph (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, is replaced with in host graph where serves as an interface, containing the nodes and edges which are preserved when applying the rule. The graph is needed to attach the pattern being matched to its context: if it is empty, the match can only designate a whole connected component of the graph .

In contrast a graph rewriting rule of the SPO approach is a single morphism in the category of labeled multigraphs and partial mappings that preserve the multigraph structure: . 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.

From the practical perspective, the key distinction between DPO and SPO is how they deal with the deletion of nodes with adjacent edges, in particular, how they avoid that such deletions may leave behind "dangling edges". The DPO approach only deletes a node when the rule specifies the deletion of all adjacent edges as well (this dangling condition can be checked for a given match), whereas the SPO approach simply disposes the adjacent edges, without requiring an explicit specification.

There is also another algebraic-like approach to graph rewriting, based mainly on Boolean algebra and an algebra of matrices, called matrix graph grammars.[1]

Determinate graph rewriting

[edit]

Yet another approach to graph rewriting, known as determinate graph rewriting, came out of logic and database theory.[2] 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.

Term graph rewriting

[edit]

Another approach to graph rewriting is term graph rewriting, which involves the processing or transformation of term graphs (also known as abstract semantic graphs) by a set of syntactic rewrite rules.

Term graphs are a prominent topic in programming language research since term graph rewriting rules are capable of formally expressing a compiler's operational semantics. Term graphs are also used as abstract machines capable of modelling chemical and biological computations as well as graphical calculi such as concurrency models. Term graphs can perform automated verification and logical programming since they are well-suited to representing quantified statements in first order logic. Symbolic programming software is another application for term graphs, which are capable of representing and performing computation with abstract algebraic structures such as groups, fields and rings.

The TERMGRAPH conference[3] focuses entirely on research into term graph rewriting and its applications.

Classes of graph grammar and graph rewriting system

[edit]

Graph rewriting systems naturally group into classes according to the kind of representation of graphs that are used and how the rewrites are expressed. The term graph grammar, otherwise equivalent to graph rewriting system or graph replacement system, is most often used in classifications. Some common types are:

Implementations and applications

[edit]

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.

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Graph rewriting

View on Grokipedia
from Grokipedia
Graph rewriting, also known as graph transformation, is a formal paradigm in for defining and performing transformations on graphs through the application of production rules that identify and replace specific subgraph s with alternative structures. These rules typically consist of a left-hand side to match and a right-hand side to insert, allowing for operations such as adding, deleting, or modifying nodes and edges while preserving the overall graph integrity via mathematical constructs like pushout constructions. Unlike term rewriting, which operates on tree-like structures, graph rewriting accommodates cycles, sharing, and hyperedges, making it suitable for representing complex, non-hierarchical data such as networks or state spaces in concurrent systems. The foundational concepts of graph rewriting emerged in the late and early , building on ideas from theory and automata, with early contributions including L-systems for biological modeling by Lindenmayer in 1968 and shape grammars by Stiny and Gips in 1972. A seminal algebraic framework was introduced by Ehrig, Pfender, and Schneider in 1973, formalizing graph grammars using and homomorphisms to ensure precise definitions of rewriting steps. Over time, several approaches have been developed to handle different aspects of , including the double-pushout (DPO) method, which emphasizes context preservation and partial matches, and the single-pushout (SPO) method, which simplifies computations by focusing on gluing operations. More recent variants, such as sesqui-pushout proposed by Corradini et al. in 2006, extend these to arbitrary categories for greater generality and efficiency in handling deletions and identifications. Graph rewriting systems have proven influential across multiple domains, including for modeling visual languages and UML diagrams, through optimizations via rewrite rules, and the of concurrent and distributed processes. In engineering and , they facilitate of structures like trusses or building models, supporting optimization and synthesis tasks. Key theoretical properties studied include (uniqueness of normal forms), termination (finiteness of rewrite sequences), and parallelism (concurrent application of rules), often analyzed using tools like critical pair analysis adapted from term rewriting. Implementations range from academic tools like GROOVE and AGG to industrial applications in database query optimization and modeling.

Fundamentals

Definition and Principles

Graph rewriting is a computational for transforming graphs by applying production rules that match a subgraph in a host graph and replace it with another subgraph, thereby preserving or modifying the overall structure according to specified conditions. This process enables the modeling and evolution of complex relational structures in fields such as formal language theory and . At its core, graph rewriting operates on a host graph, which serves as the initial structure subject to transformations, and relies on production rules of the form P:L→RP: L \to R, where LL is the left-hand side (a pattern to match) and RR is the right-hand side (the replacement structure). The application of a rule involves matching, which identifies an occurrence of LL as a subgraph in the host graph via an injective mapping, and embedding, which integrates RR into the host graph by reconnecting preserved elements and removing or adding components as needed. This can introduce non-determinism, as multiple matches may exist for the same rule in a given host graph. The standard model for graph rewriting employs directed labeled graphs, consisting of vertices (nodes) and directed arcs (edges), where both carry labels drawn from finite alphabets to encode types or attributes. Vertices represent entities, while arcs denote relations between them, allowing for hierarchical or networked representations. Some formalisms extend this to hypergraphs, where hyperedges connect multiple vertices, but the binary directed case remains foundational. A simple illustrative rule might replace a single node labeled "A" (as LL) with a chain of two nodes labeled "B" and "C" connected by a directed edge (as RR), with incoming and outgoing edges from the original node reattached to the new chain's endpoints. For instance, in an arithmetic expression graph, a rule could transform add(s(x),y)→s(add(x,y))\text{add}(s(x), y) \to s(\text{add}(x, y)), where ss denotes successor, matching the left side and the right to simplify the structure, potentially with multiple possible matches for xx and yy. Unlike string rewriting, which operates on linear sequences and corresponds to tree structures without sharing or cycles, graph rewriting accommodates cycles, multiple edges between nodes (), and hyperedges, facilitating the representation of intricate dependencies and non-linear relations. Algebraic approaches extend these principles to handle partial matches via more flexible morphisms.

Historical Development

The origins of graph rewriting trace back to the late 1960s, when Azriel Rosenfeld and John L. Pfaltz introduced web grammars as a formal mechanism for generating and recognizing picture languages represented as directed graphs with labeled vertices. This work extended string-based theory to two-dimensional structures, laying foundational ideas for and applications. Early precursors included L-systems for biological modeling introduced by Aristid Lindenmayer in 1968. In the , Hans-Jörg Kreowski advanced the field through contributions to graph grammars, including work on derivation sequences and formal systems. In the 1990s, Kreowski and Grzegorz Rozenberg developed structured graph grammars, emphasizing canonical derivations and pumping lemmas for context-free graph languages to analyze generative power and complexity. The algebraic formalisms were pioneered by Hartmut Ehrig, Manfred Pfender, and Hans-Jürgen Schneider in 1973, introducing pushout constructions as a categorical framework for graph transformation. This approach provided rigorous semantics for rule-based , influencing subsequent developments in software specification and concurrency. Concurrently, term graph emerged in the late 1980s and as an efficient implementation strategy for term systems, allowing sharing of subterms in graph representations to optimize computations in and . In the , graph rewriting integrated with concurrency theory, particularly through Grzegorz Rozenberg's efforts to unify graph grammars with Petri nets for modeling distributed systems and transformations. This period also saw the establishment of key publication venues, including the International Workshops on Graph Grammars and Their Application to , starting in , which fostered collaborative advancements. The culmination was the "Handbook of Graph Grammars and Computing by Graph Transformation" edited by Rozenberg in 1997, compiling foundational theories and applications across volumes. Post-2000 developments expanded graph rewriting into , where Ehrig and collaborators applied transformation rules to automate and verification processes. More recently, in the 2020s, explorations in have leveraged graph rewriting for manipulating quantum graph states, as seen in analyses of transformation complexity to Bell pairs using local operations. These advancements highlight graph rewriting's evolving role in bridging classical and emerging computational paradigms.

Formal Foundations

Graphs and Morphisms

In graph rewriting, graphs serve as the fundamental structures being transformed, typically formalized to support precise rule matching and application. A directed edge-labeled graph GG is defined as a G=(V,E,s,t,l)G = (V, E, s, t, l), where VV is a of vertices, EE is a of edges, s:E→Vs: E \to V and t:E→Vt: E \to V are the source and target functions specifying the endpoints of each edge, and l:E→Λl: E \to \Lambda is a labeling function that assigns labels from a fixed Λ\Lambda to edges, allowing representation of typed relations or attributes. This structure accommodates parallel edges (multiple edges between the same pair of vertices) but assumes no self-loops unless specified. Unlabeled graphs omit the labeling function ll, treating all edges as indistinguishable beyond their connectivity, while node-labeled variants extend the definition with an additional function lV:V→ΛVl_V: V \to \Lambda_V for vertex labels. Undirected graphs can be modeled within this framework by enforcing (e.g., for each edge from uu to vv, adding a reverse edge from vv to uu) or by using symmetric relations instead of directed edges. Hypergraphs generalize further, where edges () connect arbitrary finite sets of vertices rather than exactly two; formally, a H=(V,E,att)H = (V, E, att) replaces ss and tt with an attachment function att:E→Pfin(V)att: E \to \mathcal{P}_{fin}(V) mapping each hyperedge to a nonempty finite of vertices, enabling the representation of n-ary relations in systems. Graph morphisms provide the means to embed or map one graph into another while preserving structure, essential for identifying subgraphs during rewriting. A morphism f:G→Hf: G \to H between graphs G=(VG,EG,sG,tG,lG)G = (V_G, E_G, s_G, t_G, l_G) and H=(VH,EH,sH,tH,lH)H = (V_H, E_H, s_H, t_H, l_H) consists of functions fV:VG→VHf_V: V_G \to V_H and fE:EG→EHf_E: E_G \to E_H such that sH(fE(e))=fV(sG(e))s_H(f_E(e)) = f_V(s_G(e)), tH(fE(e))=fV(tG(e))t_H(f_E(e)) = f_V(t_G(e)), and lH(fE(e))=lG(e)l_H(f_E(e)) = l_G(e) for all edges e∈EGe \in E_G, ensuring compatibility of sources, targets, and labels. For hypergraphs, the condition generalizes to attH(fE(e))=fV(attG(e))att_H(f_E(e)) = f_V(att_G(e)). Morphisms compose componentwise: if g:H→Kg: H \to K, then g∘f=(gV∘fV,gE∘fE)g \circ f = (g_V \circ f_V, g_E \circ f_E), with identity morphisms being inclusions on vertices and edges. In the context of rewriting, injective morphisms—where both fVf_V and fEf_E are injective—are particularly important, as they enable exact, non-overlapping matches of rule patterns into host graphs without identifying distinct elements. An is a bijective (with bijective fVf_V and fEf_E), along with its inverse, establishing structural equivalence between graphs; two graphs are isomorphic if such a morphism exists. From a categorical perspective, the collection of all graphs (of a fixed type, e.g., directed edge-labeled) forms the category Graph, with graphs as objects and morphisms as arrows; this category has componentwise composition, identity morphisms, and supports limits and colimits constructed set-theoretically on vertices and edges. Colimits, such as pushouts, facilitate "gluing" graphs along shared subgraphs via parallel morphisms, providing a formal basis for constructing transformed graphs in processes. A representative example in graph rewriting involves an injective m:L→Gm: L \to G from the left-hand side LL of a rewrite rule to a host graph GG, which embeds L as a subgraph in G such that all edges in L correspond to edges in G via m, allowing for possible additional contextual edges in G between the matched vertices, initially preventing dangling edges that could arise from partial matches.

Rewrite Rules

In graph rewriting, a rewrite rule is formally defined as a span r=(L←K→R)r = (L \leftarrow K \rightarrow R), where LL is the left-hand side graph representing the pattern to be matched, KK is the interface graph specifying the preserved gluing shared between the left- and right-hand sides, and RR is the right-hand side graph indicating the replacement structure. The morphisms L←KL \leftarrow K and K→RK \rightarrow R are graph homomorphisms that identify corresponding elements in the interface, ensuring that elements in KK remain unchanged during rewriting while allowing modifications outside this . This structure enables precise control over which parts of a graph are deleted, preserved, or added, forming the basis for local transformations in larger host graphs. To apply a rule rr to a host graph GG, one first identifies a match, which is a graph morphism m:L→Gm: L \to G injecting the left-hand side into GG such that the image of mm embeds LL as a subgraph. The resulting graph HH is then constructed by removing the image under m of the elements in L∖KL \setminus K from GG, preserving the context outside this matched subgraph, and gluing in the elements of R∖KR \setminus K along the image of KK under the composed morphisms. This process operationalizes the rule by transforming only the matched portion while maintaining the overall connectivity and structure of the host graph through the interface. Contexts in graph rewriting refer to the subgraph of GG excluding the matched portion, which is preserved intact during the application of rr; the interface KK acts as the boundary ensuring seamless integration of the replacement RR without disrupting external connections. For instance, dangling edges or nodes adjacent to the matched subgraph but outside m(L)m(L) remain attached to their counterparts in HH via the preserved elements in KK. Rule application is inherently non-deterministic, as multiple matches m:L→Gm: L \to G may exist for a given rule in GG, or several rules from a set may apply simultaneously to overlapping or disjoint subgraphs, leading to branching derivation paths. This non-determinism reflects the generative power of graph rewriting systems, where choices in matching or rule selection can produce diverse outcomes from the same initial graph. Derivations in graph rewriting can proceed sequentially, forming a chain G0⇒G1⇒⋯⇒GnG_0 \Rightarrow G_1 \Rightarrow \cdots \Rightarrow G_n where each step applies one rule to obtain the next graph, or in parallel, applying multiple compatible rules (on disjoint matches) in a single step to yield a combined transformation. Sequential derivations emphasize step-by-step , while parallel ones accelerate by exploiting of non-overlapping rewrites, both generating languages of reachable graphs from an initial G0G_0. As a representative example, consider an initial graph G0G_0 consisting of a central node with an attached edge to another node, with a rule rr where LL is a single edge (two nodes and one edge), KK is one node (the interface, the attached node), and RR is a cycle of three nodes sharing the interface node. Matching m:L→G0m: L \to G_0 identifies the edge, removes it while preserving the interface node, and glues in the cycle, yielding G1G_1 as a where the interface node is part of the cycle and attached to the central node in the unmatched context of G0G_0; further sequential applications of similar rules can extend this to larger polygonal structures attached to the central node.

Rewriting Approaches

Algebraic Approaches

Algebraic approaches to graph rewriting formalize the transformation process using , particularly through constructions like pushouts in categories of graphs and graph morphisms. These methods provide a precise semantic foundation for rule application, treating graphs as objects and rewrite rules as spans of morphisms, thereby enabling rigorous analysis of properties such as and termination. The double-pushout (DPO) semantics is a of these algebraic approaches, where a rewrite rule p=(L←K→R)p = (L \leftarrow K \rightarrow R) is applied to a graph GG via a match m:L→Gm: L \to G in two successive pushout constructions. The first pushout deletes elements from GG corresponding to L∖KL \setminus K, yielding an intermediate graph DD, while the second pushout adds elements from R∖KR \setminus K to DD, resulting in the output graph HH. This ensures the absence of dangling edges or vertices by requiring the existence of pushout complements, which glues the constructions soundly. Formally, given a match m:L→Gm: L \to G, the DPO construction proceeds as follows: first, form the pushout square with morphisms m:L→Gm: L \to G and k:K→Lk: K \to L (inclusion), yielding d:K→Dd: K \to D and g′:L∖K→Dg': L \setminus K \to D, where DD is the deletion result isomorphic to G−L+KG - L + K. Then, construct the second pushout square with d:K→Dd: K \to D and r:K→Rr: K \to R, yielding h:R→Hh: R \to H and g′′:R∖K→Hg'': R \setminus K \to H, so HH is isomorphic to D+R−KD + R - K. This is visualized as two adjacent pushout squares sharing the morphism from KK: The first pushout square: K→kL↓d↓mD→g′G\begin{array}{ccc} K & \xrightarrow{k} & L \\ \downarrow d & & \downarrow m \\ D & \xrightarrow{g'} & G \\ \end{array}
Add your contribution
Related Hubs
User Avatar
No comments yet.