Rewriting rules tutorial¶
In the context of ReGraph, by rewriting rules we mean the rules of sesqui-pushout rewriting (see more details here). A rewriting rule consists of the three graphs: P – preserved part, LHS – left hand side, RHS – right hand side, and two mappings: from P to LHS and from P to RHS.
Informally, LHS represents a pattern to match in a graph, subject to rewriting. P together with the mapping P -> LHS specifies a part of the pattern which stays preseved during rewriting, i.e. all the nodes/edges/attributes present in LHS but not P will be removed. RHS and P -> RHS specify nodes/edges/attributes to add to the P. In addition, rules defined is such a way allow to clone and merge nodes. If two nodes from P map to the same node in LHS, the node corresponding to this node of the pattern will be cloned. Symmetrically, if two nodes from P map to the same node in $rhs$, the corresponding two nodes will be merged.
This tutorial will illustrate the idea behind the sesqui-pushout rewriting rules in more detail.
Let us start by importing the necessary data structures and functions:
from regraph import NXGraph, Rule, plot_rule
Creating a rewriting rule from a pattern¶
# Define the left-hand side of the rule
pattern = NXGraph()
pattern.add_nodes_from([1, 2, 3])
pattern.add_edges_from([(1, 2), (2, 3)])
rule1 = Rule.from_transform(pattern)
# `inject_clone_node` returns the IDs of the newly created
# clone in P and RHS
p_clone, rhs_clone = rule1.inject_clone_node(1)
rule1.inject_add_node("new_node")
rule1.inject_add_edge("new_node", rhs_clone)
Now, let us plot the rule
>>> plot_rule(rule1)
Every rule can be converted to a sequence of human-readable commands:
>>> print(rule1.to_commands())
CLONE 1 AS 11.
ADD_NODE new_node {}.
ADD_EDGE new_node 11 {}.
Creating a rewriting rule from a span¶
By default, Rule objects in ReGraph are initialized with three graph objects (NXGraph) corresponding to P, LHS and RHS, together with two Python dictionaries encoding the homomorphisms P -> LHS and P -> RHS. This may be useful in a lot of different scenarios. For instance, as in the following example:
# Define the left-hand side of the rule
pattern = NXGraph()
pattern.add_nodes_from([1, 2, 3])
pattern.add_edges_from([(1, 2), (1, 3), (1, 1), (2, 3)])
# Define the preserved part of the rule
rule2 = Rule.from_transform(pattern)
p_clone, rhs_clone = rule2.inject_clone_node(1)
>>> plot_rule(rule2)
>>> print("New node corresponding to the clone: ", p_clone)
New node corresponding to the clone: 11
>>> print(rule2.p.edges())
[(1, 2), (1, 3), (1, 1), (1, '11'), (2, 3), ('11', 1), ('11', 3), ('11', '11'), ('11', 2)]
As the result of cloning of the node 1, all its incident edges are copied to the newly created clone node (variable p_clone). However, in our rule we would like to keep only some of the edges and remove the rest as follows.
rule2.inject_remove_edge(1, 1) rule2.inject_remove_edge(p_clone, p_clone) rule2.inject_remove_edge(p_clone, 1) rule2.inject_remove_edge(p_clone, 2) rule2.inject_remove_edge(1, 3)
>>> print(rule2.p.edges())
[(1, 2), (1, '11'), (2, 3), ('11', 3)]
>>> plot_rule(rule2)
Instead of initializing our rule from the pattern and injecting a lot of edge removals, we could directly initialize three objects for P, LHS and RHS, where P contains only the desired edges. In the following example, because the rule does not specify any merges or additions (so RHS is isomorphic to P), we can omit the parameter RHS in the constructor of Rule.
# Define the left-hand side of the rule
lhs = NXGraph()
lhs.add_nodes_from([1, 2, 3])
lhs.add_edges_from([(1, 2), (1, 3), (1, 1), (2, 3)])
# Define the preserved part of the rule
p = NXGraph()
p.add_nodes_from([1, "1_clone", 2, 3])
p.add_edges_from([
(1, 2),
(1, "1_clone"),
("1_clone", 3),
(2, 3)])
p_lhs = {1: 1, "1_clone": 1, 2: 2, 3: 3}
# Initialize a rule object
rule3 = Rule(p, lhs, p_lhs=p_lhs)
>>> plot_rule(rule3)
>>> print(rule3.p.edges())
[(1, 2), (1, '1_clone'), ('1_clone', 3), (2, 3)]