This notebook consists of simple examples of usage of the ReGraph library
In [2]:
import copy
import networkx as nx
from regraph.hierarchy import Hierarchy
from regraph.rules import Rule
from regraph.plotting import plot_graph, plot_instance, plot_rule
from regraph.primitives import find_matching, print_graph, equal, add_nodes_from, add_edges_from
from regraph.utils import keys_by_value
import matplotlib.pyplot as plt
In [3]:
%matplotlib inline
ReGraph works with NetworkX graph objects, both undirected graphs (nx.Graph
) and directed ones (nx.DiGraph
). The workflow of the graph initialization in NetworkX can be found here.
In [4]:
graph = nx.DiGraph()
add_nodes_from(graph,
[
('1', {'name': 'EGFR', 'state': 'p'}),
('2', {'name': 'BND'}),
('3', {'name': 'Grb2', 'aa': 'S', 'loc': 90}),
('4', {'name': 'SH2'}),
('5', {'name': 'EGFR'}),
('6', {'name': 'BND'}),
('7', {'name': 'Grb2'}),
('8', {'name': 'WAF1'}),
('9', {'name': 'BND'}),
('10', {'name': 'G1-S/CDK', 'state': 'p'}),
])
edges = [
('1', '2', {'s': 'p'}),
('4', '2', {'s': 'u'}),
('4', '3'),
('5', '6', {'s': 'p'}),
('7', '6', {'s': 'u'}),
('8', '9'),
('9', '8'),
('10', '8', {"a": {1}}),
('10', '9', {"a": {2}}),
('5', '2', {'s': 'u'})
]
add_edges_from(graph, edges)
In [6]:
type(graph.node['1']['name'])
Out[6]:
ReGraph provides some utils for graph plotting that are going to be used in the course of this tutorial.
In [4]:
positioning = plot_graph(graph)
Graph rewriting is implemented as an application of a graph rewriting rule to a given input graph object $G$. A graph rewriting rule $R$ is a span $LHS \leftarrow P \rightarrow RHS$, where $LHS$ is a graph that represents a left hand side of the rule -- a pattern that is going to be matched inside of the graph, $P$ is a graph that represents a preserved part of the rule -- together with a homomorphism $LHS \leftarrow P$ it specifies nodes and edges that are going to be preserved in the course of application of the rule. $RHS$ and a homomorphism $P \rightarrow RHS$ on the other hand specify nodes and edges that are going to be added. In addition, if two nodes $n^P_1, n^P_2$ of $P$ map to the same node $n^{LHS}$ in $LHS$, $n^{LHS}$ is going to be cloned during graph rewriting. Symmetrically, if two nodes of $n^P_1$ and $n^P_2$ in $P$ match to the same node $n^{RHS}$ in $RHS$, $n^P_1$ and $n^P_2$ are merged.
$LHS$, $P$ and $RHS$ can be defined as NetworkX graphs
In [5]:
pattern = nx.DiGraph()
add_nodes_from(
pattern,
[(1, {'state': 'p'}),
(2, {'name': 'BND'}),
3,
4]
)
add_edges_from(
pattern,
[(1, 2, {'s': 'p'}),
(3, 2, {'s': 'u'}),
(3, 4)]
)
p = nx.DiGraph()
add_nodes_from(p,
[(1, {'state': 'p'}),
'1_clone',
(2, {'name': 'BND'}),
3,
4
])
add_edges_from(
p,
[(1, 2),
('1_clone', 2),
(3, 4)
])
rhs = nx.DiGraph()
add_nodes_from(
rhs,
[(1, {'state': 'p'}),
'1_clone',
(2, {'name': 'BND'}),
3,
4,
5
])
add_edges_from(
rhs,
[(1, 2, {'s': 'u'}),
('1_clone', 2),
(2, 4),
(3, 4),
(5, 3)
])
p_lhs = {1: 1, '1_clone': 1, 2: 2, 3: 3, 4: 4}
p_rhs = {1: 1, '1_clone': '1_clone', 2: 2, 3: 3, 4: 4}
regraph.library.rules.Rule
. An instance of regraph.library.rules.Rule
is initialized with NetworkX graphs $LHS$, $P$, $RHS$, and two dictionaries specifying $LHS \leftarrow P$ and $P \rightarrow RHS$.regraph.library.plotting.plot_rule
util is implemented in ReGraph.
In [6]:
rule = Rule(p, pattern, rhs, p_lhs, p_rhs)
plot_rule(rule)
regraph.library.primitives.find_matching
function. This function returns a list of dictionaries representing the matchings. If no matchings were found the list is empty.regraph.library.plotting.plot_instance
util.
In [7]:
instances = find_matching(graph, rule.lhs)
print("Instances:")
for instance in instances:
print(instance)
plot_instance(graph, rule.lhs, instance, parent_pos=positioning) #filename=("instance_example_%d.png" % i))
Graph rewriting can be performed with the regraph.library.primitives.rewrite
function. It takes as an input a graph, an instance of the matching (dictionary that specifies the mapping from the nodes of $LHS$ to the nodes of $G$), a rewriting rule (an instance of the regraph.library.rules.Rule
class), and a parameter inplace
(by default set to True
). If inplace
is True
rewriting will be performed directly in the provided graph object and the function will return a dictionary corresponding to the $RHS$ matching in the rewritten graph ($RHS \rightarrowtail G'$), otherwise the rewriting function will return a new graph object corresponding to the result of rewriting and the $RHS$ matching.
Another possibility to perform graph rewriting is implemented in the apply_to
method of a regraph.library.Rule
class. It takes as an input a graph and an instance of the matching. It applies a corresponding (to self
) rewriting rule and returns a new graph (the result of graph rewriting).
In [8]:
# Rewriting without modification of the initial object
graph_backup = copy.deepcopy(graph)
new_graph_1, rhs_graph = rule.apply_to(graph, instances[0], inplace=False)
In [9]:
# print(equal(new_graph_1, new_graph_2))
print(new_graph_1.edge['1']['2'])
assert(equal(graph_backup, graph))
print("Matching of RHS:", rhs_graph)
In [10]:
plot_instance(graph, rule.lhs, instances[0], parent_pos=positioning)
new_pos = plot_instance(new_graph_1, rule.rhs, rhs_graph, parent_pos=positioning)
ReGraph also provides a primitive for testing equality of two graphs in regraph.library.primitives.equal
. In our previous example we can see that a graph obtained by application of a rule new_graph
(through the Rule
interface) and an initial graph object graph
after in-place rewriting are equal.
ReGraph allows to create a hierarchy of graphs connected together by means of typing homomorphisms. In the context of hierarchy if there exists a homomorphism $G \rightarrow T$ we say that graph $G$ is typed by a graph $T$. Graph hierarchy is a DAG, where nodes are graphs and edges are typing homomorphisms between graphs.
ReGraph provides two kinds of typing for graphs: partial typing and total typing.
Note: Use total typing if you would like to make sure that the nodes of your graphs are always strictly typed by some metamodel.
Consider the following example of a simple graph hierarchy. The two graphs $G$ and $T$ are being created and added to the heirarchy. Afterwards a typing homomorphism (total) between $G$ and $T$ is added, so that every node of $G$ is typed by some node in $T$.
In [11]:
# Define graph G
g = nx.DiGraph()
g.add_nodes_from(["protein", "binding", "region", "compound"])
g.add_edges_from([("region", "protein"), ("protein", "binding"), ("region", "binding"), ("compound", "binding")])
# Define graph T
t = nx.DiGraph()
t.add_nodes_from(["action", "agent"])
t.add_edges_from([("agent", "agent"), ("agent", "action")])
# Define graph G'
g_prime = nx.DiGraph()
g_prime.add_nodes_from(
["EGFR", "BND_1", "SH2", "Grb2"]
)
g_prime.add_edges_from([
("EGFR", "BND_1"),
("SH2", "BND_1"),
("SH2", "Grb2")
])
In [12]:
# Create a hierarchy
simple_hierarchy = Hierarchy()
simple_hierarchy.add_graph("G", g, {"name": "Simple protein interaction"})
simple_hierarchy.add_graph("T", t, {"name": "Agent interaction"})
simple_hierarchy.add_typing(
"G", "T",
{"protein": "agent",
"region": "agent",
"compound": "agent",
"binding": "action",
},
total=True
)
simple_hierarchy.add_graph("G_prime", g_prime, {"name": "EGFR and Grb2 binding"})
simple_hierarchy.add_typing(
"G_prime", "G",
{
"EGFR": "protein",
"BND_1": "binding",
"SH2": "region",
"Grb2": "protein"
},
total=True
)
print(simple_hierarchy)
In [13]:
plot_graph(simple_hierarchy.node["T"].graph)
pos = plot_graph(simple_hierarchy.node["G"].graph)
plot_graph(simple_hierarchy.node["G_prime"].graph, parent_pos=pos)
Out[13]:
ReGraph implements rewriting of graphs in the hierarchy, this rewriting is more restrictive as application of a rewriting rule cannot violate any typing defined in the hierarchy. The following code illustrates the application of a rewriting rule to the graph in the hierarchy. On the first step we create a Rule
object containing a rule we would like to apply.
In [14]:
lhs = nx.DiGraph()
add_nodes_from(lhs, [1, 2])
add_edges_from(lhs, [(1, 2)])
p = nx.DiGraph()
add_nodes_from(p, [1, 2])
add_edges_from(p, [])
rhs = nx.DiGraph()
add_nodes_from(rhs, [1, 2, 3])
add_edges_from(rhs, [(3, 1), (3, 2)])
# By default if `p_lhs` and `p_rhs` are not provided
# to a rule, it tries to construct this homomorphisms
# automatically by matching the names. In this case we
# have defined lhs, p and rhs in such a way that that
# the names of the matching nodes correspond
rule = Rule(p, lhs, rhs)
plot_rule(rule)
Now, we would like to use the rule defined above in the following context: in the graph G_prime
we want to find "protien" nodes connected to "binding" nodes and to delete the edge connecting them, after that we would like to add a new intermediary node and connect it to the previous "protein" and "binding".
We can provide this context by specifying a typing of the $LHS$ of the rule, which would indicated that node 1
is a "protein", and node 2
is a "binding". Now the hierarchy will search for a matching of $LHS$ respecting the types of the nodes.
In [15]:
lhs_typing = {
"G": {
1: "protein",
2: "binding"
}
}
regraph.library.Hierarchy
provides the method find_matching
to find matchings of a pattern in a given graph in the hierarchy. The typing of $LHS$ should be provided to the find_matching
method.
In [16]:
# Find matching of lhs without lhs_typing
instances_untyped = simple_hierarchy.find_matching("G_prime", lhs)
pos = plot_graph(simple_hierarchy.node["G_prime"].graph)
print("Instances found without pattern typing:")
for instance in instances_untyped:
print(instance)
plot_instance(simple_hierarchy.node["G_prime"].graph, lhs, instance, parent_pos=pos)
# Find matching of lhs with lhs_typing
instances = simple_hierarchy.find_matching("G_prime", lhs, lhs_typing)
print("\n\nInstances found with pattern typing:")
for instance in instances:
print(instance)
plot_instance(simple_hierarchy.node["G_prime"].graph, lhs, instance, parent_pos=pos)
As a rewriting rule can implement addition and merging of some nodes, an appropriate typing of the $RHS$ allows to specify the typing for new nodes.
- By default, if a typing of $RHS$ is not provided, all the nodes added and merged will be not typed. Note: If a graph $G$ was totally typed by some graph $T$, and a rewriting rule which transforms $G$ into $G'$ has added/merged some nodes for which there is no typing in $T$ specified, $G'$ will become only partially typed by $T$ and ReGraph will raise a warning.
If a typing of a new node is specified in the $RHS$ typing, the node will have this type as long as it is consistent (homomrophism $G' \rightarrow T$ is valid) with $T$.
If a typing of a merged node is specified in the $RHS$ typing, the node will have this type as long as (a) all the nodes that were merged had this type (b) new typing is a consistent homomrophism ($G' \rightarrow T$ is valid).
For our example, we will not specify the type of the new node 3
, so that G_prime
after rewriting will become only parially typed by G
.
In [17]:
print("Node types in `G_prime` before rewriting: \n")
for node in simple_hierarchy.node["G_prime"].graph.nodes():
print(node, simple_hierarchy.node_type("G_prime", node))
In [18]:
rhs_typing = {
"G": {
3: "region"
}
}
In [19]:
new_hierarchy, _ = simple_hierarchy.rewrite("G_prime", rule, instances[0], lhs_typing, rhs_typing, inplace=False)
In [20]:
plot_graph(new_hierarchy.node["G_prime"].graph)
plot_graph(new_hierarchy.node["G"].graph)
plot_graph(new_hierarchy.node["T"].graph)
Out[20]:
In [21]:
print("Node types in `G_prime` before rewriting: \n")
for node in new_hierarchy.node["G_prime"].graph.nodes():
print(node, new_hierarchy.node_type("G_prime", node))
Now, rewriting can be performed using regraph.library.hierarchy.Hierarchy.rewrite
method. It takes as an input id of the graph to rewrite, a rule, an instance of the LHS of a rule ($LHS \rightarrow G$), and a typing of $LHS$ and $RHS$.
Note: In case the graph to be rewritten is not typed by any other graph in the hierarchy, the $LHS$ and $RHS$ typings are not required.
In [22]:
newer_hierarchy, _ = simple_hierarchy.rewrite("G_prime", rule, instances[0], lhs_typing, inplace=False, strict=False)
In [23]:
print("Node types in `G_prime` after rewriting: \n")
for node in newer_hierarchy.node["G_prime"].graph.nodes():
print(node, newer_hierarchy.node_type("G_prime", node))
In [24]:
plot_graph(newer_hierarchy.node["G_prime"].graph)
plot_graph(newer_hierarchy.node["G"].graph)
plot_graph(newer_hierarchy.node["T"].graph)
Out[24]:
In [ ]:
In [25]:
print("Node types in `G_prime` after rewriting: \n")
for node in new_hierarchy.node["G_prime"].graph.nodes():
print(node, new_hierarchy.node_type("G_prime", node))
Later on if a node form $G$ is not typed in $T$, we can specify a typing for this node.
In the example we type the node 3
as a region
in G
.
It is also possible to remove a graph from the hierarchy using the regraph.library.hierarchy.Hierarchy.remove_graph
method. It takes as an input the id of a graph to remove, and if the argument reconnect
is set to True
, it reconnects all the graphs typed by the graph being removed to the graphs typing it.
In our example if we remove graph G
from the hierarchy, G_prime
is now directly typed by T
.
In [26]:
simple_hierarchy.remove_graph("G", reconnect=True)
print(simple_hierarchy)
print("New node types in 'G_prime':\n")
for node in simple_hierarchy.node["G_prime"].graph.nodes():
print(node, ": ", simple_hierarchy.node_type("G_prime", node))
In [27]:
hierarchy = Hierarchy()
colors = nx.DiGraph()
colors.add_nodes_from([
"green", "red"
])
colors.add_edges_from([
("red", "green"),
("red", "red"),
("green", "green")
])
hierarchy.add_graph("colors", colors, {"id": "https://some_url"})
shapes = nx.DiGraph()
shapes.add_nodes_from(["circle", "square"])
shapes.add_edges_from([
("circle", "square"),
("square", "circle"),
("circle", "circle")
])
hierarchy.add_graph("shapes", shapes)
quality = nx.DiGraph()
quality.add_nodes_from(["good", "bad"])
quality.add_edges_from([
("bad", "bad"),
("bad", "good"),
("good", "good")
])
hierarchy.add_graph("quality", quality)
g1 = nx.DiGraph()
g1.add_nodes_from([
"red_circle",
"red_square",
"some_circle",
])
g1.add_edges_from([
("red_circle", "red_square"),
("red_circle", "red_circle"),
("red_square", "red_circle"),
("some_circle", "red_circle")
])
g1_colors = {
"red_circle": "red",
"red_square": "red",
}
g1_shapes = {
"red_circle": "circle",
"red_square": "square",
"some_circle": "circle"
}
hierarchy.add_graph("g1", g1)
hierarchy.add_typing("g1", "colors", g1_colors, total=False)
hierarchy.add_typing("g1", "shapes", g1_shapes, total=False)
g2 = nx.DiGraph()
g2.add_nodes_from([
"good_circle",
"good_square",
"bad_circle",
"good_guy",
"some_node"
])
g2.add_edges_from([
("good_circle", "good_square"),
("good_square", "good_circle"),
("bad_circle", "good_circle"),
("bad_circle", "bad_circle"),
("some_node", "good_circle"),
("good_guy", "good_square")
])
g2_shapes = {
"good_circle": "circle",
"good_square": "square",
"bad_circle": "circle"
}
g2_quality = {
"good_circle": "good",
"good_square": "good",
"bad_circle": "bad",
"good_guy": "good"
}
hierarchy.add_graph("g2", g2)
hierarchy.add_typing("g2", "shapes", g2_shapes)
hierarchy.add_typing("g2", "quality", g2_quality)
g3 = nx.DiGraph()
g3.add_nodes_from([
"good_red_circle",
"bad_red_circle",
"good_red_square",
"some_circle_node",
"some_strange_node"
])
g3.add_edges_from([
("bad_red_circle", "good_red_circle"),
("good_red_square", "good_red_circle"),
("good_red_circle", "good_red_square")
])
g3_g1 = {
"good_red_circle": "red_circle",
"bad_red_circle": "red_circle",
"good_red_square": "red_square"
}
g3_g2 = {
"good_red_circle": "good_circle",
"bad_red_circle": "bad_circle",
"good_red_square": "good_square",
}
hierarchy.add_graph("g3", g3)
hierarchy.add_typing("g3", "g1", g3_g1)
hierarchy.add_typing("g3", "g2", g3_g2)
lhs = nx.DiGraph()
lhs.add_nodes_from([1, 2])
lhs.add_edges_from([(1, 2)])
p = nx.DiGraph()
p.add_nodes_from([1, 11, 2])
p.add_edges_from([(1, 2)])
rhs = copy.deepcopy(p)
rhs.add_nodes_from([3])
p_lhs = {1: 1, 11: 1, 2: 2}
p_rhs = {1: 1, 11: 11, 2: 2}
r1 = Rule(p, lhs, rhs, p_lhs, p_rhs)
hierarchy.add_rule("r1", r1, {"desc": "Rule 1: typed by two graphs"})
lhs_typing1 = {1: "red_circle", 2: "red_square"}
rhs_typing1 = {3: "red_circle"}
# rhs_typing1 = {1: "red_circle", 11: "red_circle", 2: "red_square"}
lhs_typing2 = {1: "good_circle", 2: "good_square"}
rhs_typing2 = {3: "bad_circle"}
# rhs_typing2 = {1: "good_circle", 11: "good_circle", 2: "good_square"}
hierarchy.add_rule_typing("r1", "g1", lhs_typing1, rhs_typing1)
hierarchy.add_rule_typing("r1", "g2", lhs_typing2, rhs_typing2)
Some of the graphs in the hierarchy are now typed by multiple graphs, which is reflected in the types of nodes, as in the example below:
In [28]:
print("Node types in G3:\n")
for node in hierarchy.node["g3"].graph.nodes():
print(node, hierarchy.node_type("g3", node))
In [29]:
hierarchy.add_node_type("g3", "some_circle_node", {"g1": "red_circle", "g2": "good_circle"})
hierarchy.add_node_type("g3", "some_strange_node", {"g2": "some_node"})
print("Node types in G3:\n")
for node in hierarchy.node["g3"].graph.nodes():
print(node, hierarchy.node_type("g3", node))
Notice that as G3
is paritally typed by both G1
and G2
, not all the nodes have types in both G1
and G2
. For example, node some_circle_node
is typed only by some_circle
in G1
, but is not typed by any node in G2
.
Having constructed a sophisticated rewriting rule typed by some nodes in the hierarchy one may want to store this rule and to be able to propagate any changes that happen in the hierarchy to the rule as well.
ReGraph's regraph.library.hierarchy.Hierarchy
allows to add graph rewriting rules as nodes in the hierarchy. Rules in the hierarchy can be (partially) typed by graphs.
Note: nothing can be typed by a rule in the hierarchy.
In the example below, a rule is added to the previously constructed hierarchy and typed by graphs g1
and g2
:
In [30]:
print(hierarchy)
In [31]:
print(hierarchy.edge["r1"]["g1"].lhs_mapping)
print(hierarchy.edge["r1"]["g1"].rhs_mapping)
print(hierarchy.edge["r1"]["g2"].lhs_mapping)
print(hierarchy.edge["r1"]["g2"].rhs_mapping)
We now show how graph rewriting can be performed in such an hierarchy. In the previous example we perfromed graph rewriting on the top level of the hierarchy, meaning that the graph that was rewritten did not type any other graph.
The following example illustrates what happens if we rewrite a graph typing some other graphs. The ReGraph hierarchy is able to propagate the changes made by rewriting on any level to all the graphs (as well as the rules) typed by the one subject to rewriting.
In [32]:
lhs = nx.DiGraph()
lhs.add_nodes_from(["a", "b"])
lhs.add_edges_from([
("a", "b"),
("b", "a")
])
p = nx.DiGraph()
p.add_nodes_from(["a", "a1", "b"])
p.add_edges_from([
("a", "b"),
("a1", "b")
])
rhs = copy.deepcopy(p)
rule = Rule(
p, lhs, rhs,
{"a": "a", "a1": "a", "b": "b"},
{"a": "a", "a1": "a1", "b": "b"},
)
In [33]:
instances = hierarchy.find_matching("shapes", lhs)
print("Instances:")
for instance in instances:
print(instance)
plot_instance(hierarchy.node["shapes"].graph, rule.lhs, instance)
In [34]:
_, m = hierarchy.rewrite("shapes", rule, {"a": "circle", "b": "square"})
In [35]:
print(hierarchy)
In [36]:
sep = "========================================\n\n"
print("Graph 'shapes':\n")
print("===============")
print_graph(hierarchy.node["shapes"].graph)
print(sep)
print("Graph 'g1':\n")
print("===========")
print_graph(hierarchy.node["g1"].graph)
print(sep)
print("Graph 'g2':\n")
print("===========")
print_graph(hierarchy.node["g2"].graph)
print(sep)
print("Graph 'g3':\n")
print("===========")
print_graph(hierarchy.node["g3"].graph)
print(sep)
print("Rule 'r1':\n")
print("===========")
print("\nLHS:")
print_graph(hierarchy.node["r1"].rule.lhs)
print("\nP:")
print_graph(hierarchy.node["r1"].rule.p)
print("\nRHS:")
print_graph(hierarchy.node["r1"].rule.rhs)
In [37]:
print(hierarchy.rule_lhs_typing["r1"]["g1"])
print(hierarchy.rule_rhs_typing["r1"]["g1"])
print(hierarchy.typing["g3"]["g1"])
In [38]:
instances = hierarchy.find_rule_matching("g3", "r1")
hierarchy.apply_rule(
"g3",
"r1",
instances[0]
)
Out[38]:
In [39]:
print_graph(hierarchy.node["g3"].graph)
ReGraph provides the following methods for loading and exporting your hierarchy:
regraph.library.hierarchy.Hierarchy.to_json
creates a json representations of the hierarchy;
regraph.library.hierarchy.Hierarchy.from_json
loads an hierarchy from json representation (returns new Hierarchy
object);
regraph.library.hierarchy.Hierarchy.export
exports the hierarchy to a file (json format);regraph.library.hierarchy.Hierarchy.load
loads an hierarchy from a .json file (returns new object as well).
In [40]:
hierarchy_json = hierarchy.to_json()
In [41]:
new_hierarchy = Hierarchy.from_json(hierarchy_json, directed=True)
In [42]:
new_hierarchy == hierarchy
Out[42]:
By default rewriting requires all the nodes in the result of the rewriting to be totally typed by all the graphs typing the graph subject to rewriting. If parameter total
in the rewriting is set to False
, rewriting is allowed to produce untyped nodes.
In addition, rewriting is available in these possible configurations:
2. Weak typing of a rule: (parameter strong=False
) only checks the consistency of the types given explicitly by a rule, and allows to remove node types. If typing of a node in RHS does not contain explicit typing by some typing graph -- this node will be not typed by this graph in the result.
Note: Weak typing should be used with parameter total
set to False, otherwise deletion of node types will be not possible.
Examples below illustrate some interesting use-cases of rewriting with different rule examples.
In [43]:
base = nx.DiGraph()
base.add_nodes_from([
("circle", {"a": {1, 2}, "b": {3, 4}}),
("square", {"a": {3, 4}, "b": {1, 2}})
])
base.add_edges_from([
("circle", "circle", {"c": {1, 2}}),
("circle", "square", {"d": {1, 2}}),
])
little_hierarchy = Hierarchy()
little_hierarchy.add_graph("base", base)
graph = nx.DiGraph()
graph.add_nodes_from([
("c1", {"a": {1}}),
("c2", {"a": {2}}),
"s1",
"s2",
("n1", {"x":{1}})
])
graph.add_edges_from([
("c1", "c2", {"c": {1}}),
("c2", "s1"),
("s2", "n1", {"y": {1}})
])
little_hierarchy.add_graph("graph", graph)
little_hierarchy.add_typing(
"graph", "base",
{
"c1": "circle",
"c2": "circle",
"s1": "square",
"s2": "square"
}
)
In [44]:
# In this rule we match any pair of nodes and try to add an edge between them
# the rewriting will fail every time the edge is not allowed between two nodes
# by its typing graphs
# define a rule
lhs = nx.DiGraph()
lhs.add_nodes_from([1, 2])
p = copy.deepcopy(lhs)
rhs = copy.deepcopy(lhs)
rhs.add_edges_from([(1, 2)])
rule = Rule(p, lhs, rhs)
instances = little_hierarchy.find_matching(
"graph",
rule.lhs
)
current_hierarchy = copy.deepcopy(little_hierarchy)
for instance in instances:
try:
current_hierarchy.rewrite(
"graph",
rule,
instance
)
print("Instance rewritten: ", instance)
print()
except Exception as e:
print("\nFailed to rewrite an instance: ", instance)
print("Addition of an edge was not allowed, error message received:")
print("Exception type: ", type(e))
print("Message: ", e)
print()
print_graph(current_hierarchy.node["graph"].graph)
print("\n\nTypes of nodes after rewriting:")
for node in current_hierarchy.node["graph"].graph.nodes():
print(node, current_hierarchy.node_type("graph", node))
In [45]:
lhs = nx.DiGraph()
lhs.add_nodes_from([1, 2])
p = copy.deepcopy(lhs)
rhs = nx.DiGraph()
rhs.add_nodes_from([1])
rule = Rule(p, lhs, rhs, p_rhs={1: 1, 2: 1})
instances = little_hierarchy.find_matching(
"graph",
rule.lhs
)
for instance in instances:
try:
current_hierarchy, _ = little_hierarchy.rewrite(
"graph",
rule,
instance,
inplace=False
)
print("Instance rewritten: ", instance)
print_graph(current_hierarchy.node["graph"].graph)
print("\n\nTypes of nodes after rewriting:")
for node in current_hierarchy.node["graph"].graph.nodes():
print(node, current_hierarchy.node_type("graph", node))
print()
except Exception as e:
print("\nFailed to rewrite an instance: ", instance)
print("Merge was not allowed, error message received:")
print("Exception type: ", type(e))
print("Message: ", e)
print()
#### 3.3. Weak typing of a rule
If rewriting parameter strong_typing
is set to False
, the weak typing of a rule is applied. All the types of the nodes in the RHS of the rule which do not have explicitly specified types will be removed.
In [46]:
g1 = nx.DiGraph()
g1.add_node(1)
g2 = copy.deepcopy(g1)
g3 = copy.deepcopy(g1)
g4 = copy.deepcopy(g1)
hierarchy = Hierarchy()
hierarchy.add_graph(1, g1, graph_attrs={"name": {"Main hierarchy"}})
hierarchy.add_graph(2, g2, graph_attrs={"name": {"Base hierarchy"}})
hierarchy.add_graph(3, g3)
hierarchy.add_graph(4, g4)
hierarchy.add_typing(1, 2, {1: 1})
hierarchy.add_typing(1, 4, {1: 1})
hierarchy.add_typing(2, 3, {1: 1})
hierarchy.add_typing(4, 3, {1: 1})
hierarchy1 = copy.deepcopy(hierarchy)
hierarchy2 = copy.deepcopy(hierarchy)
hierarchy3 = copy.deepcopy(hierarchy)
In [47]:
h1 = nx.DiGraph()
h1.add_node(2)
h2 = copy.deepcopy(h1)
h3 = copy.deepcopy(h1)
h4 = copy.deepcopy(h1)
other_hierarchy = Hierarchy()
other_hierarchy.add_graph(1, h1, graph_attrs={"name": {"Main hierarchy"}})
other_hierarchy.add_graph(2, h2, graph_attrs={"name": {"Base hierarchy"}})
other_hierarchy.add_graph(3, h3)
other_hierarchy.add_graph(4, h4)
other_hierarchy.add_typing(1, 2, {2: 2})
other_hierarchy.add_typing(1, 4, {2: 2})
other_hierarchy.add_typing(2, 3, {2: 2})
other_hierarchy.add_typing(4, 3, {2: 2})
In [48]:
hierarchy1.merge_by_id(other_hierarchy)
print(hierarchy1)
In [49]:
# Now we make node 1 in the hierarchies to be the same graph
hierarchy2.node[1].graph.add_node(2)
other_hierarchy.node[1].graph.add_node(1)
hierarchy2.merge_by_id(other_hierarchy)
print(hierarchy2)
In [50]:
# Now make a hierarchies to have two common nodes with an edge between them
hierarchy3.node[1].graph.add_node(2)
other_hierarchy.node[1].graph.add_node(1)
hierarchy3.node[2].graph.add_node(2)
other_hierarchy.node[2].graph.add_node(1)
hierarchy4 = copy.deepcopy(hierarchy3)
In [51]:
hierarchy3.merge_by_id(other_hierarchy)
print(hierarchy3)
print(hierarchy3.edge[1][2].mapping)
In [52]:
hierarchy4.merge_by_attr(other_hierarchy, "name")
Out[52]:
In [53]:
print(hierarchy4)
print(hierarchy4.edge['1_1']['2_2'].mapping)