ReGraph tutorial: from simple graph rewriting to a graph hierarchy

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

I. Simple graph rewriting

1. Initialization of a graph

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.attribute_sets.FiniteSet

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)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):

2. Initialization of a rule

  • 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}
  • A rule of graph rewriting is implemeted in the class 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$.
  • For visualization of a rule regraph.library.plotting.plot_rule util is implemented in ReGraph.

In [6]:
rule = Rule(p, pattern, rhs, p_lhs, p_rhs)
plot_rule(rule)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):

1. Rewriting

1.1. Matching of LHS

  • The matchings of $LHS$ in $G$ ($LHS \rightarrowtail G$) can be found using 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.
  • Visualization of the matching in $G$ is implemented in the 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))


Instances:
{1: '1', 2: '2', 3: '4', 4: '3'}
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):
{1: '1', 2: '2', 3: '5', 4: '6'}

1.2. Rewriting

  1. 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.

  2. 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)


{'s': {'u'}}
Matching of RHS: {1: '1', '1_clone': '11', 2: '2', 3: '4', 4: '3', 5: 5}

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)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):

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.

II. Hierarchy of graphs & rewriting

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.

  • Total typing ($G \rightarrow T)$ is a homomorphism which maps every node of $G$ to some node in $T$ (a type);
  • Partial typing ($G \rightharpoonup T$) is a slight generalisation of total typing, which allows only a subset of nodes from $G$ to be typed by nodes in $T$ (to have types in $T$), whereas the rest of the nodes which do not have a mapping to $T$ are considered as nodes which do not have type in $T$.

Note: Use total typing if you would like to make sure that the nodes of your graphs are always strictly typed by some metamodel.

1. Example: simple hierarchy

1.1. Initialization of a hierarchy

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)


Graphs (directed == True): 

Nodes:
Graph: G {'name': {'Simple protein interaction'}}
Graph: T {'name': {'Agent interaction'}}
Graph: G_prime {'name': {'EGFR and Grb2 binding'}}

Typing homomorphisms: 
G -> T: total == True
G_prime -> G: total == True

Relations:

attributes : 
{}


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)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):
Out[13]:
{'BND_1': array([ 0.56930831,  0.66288835]),
 'EGFR': array([ 0.11558356,  1.        ]),
 'Grb2': array([ 0.,  0.]),
 'SH2': array([ 0.52620779,  0.0552404 ]),
 'binding': array([ 0.3997026 ,  0.49443071]),
 'compound': array([ 0.24936027,  0.        ]),
 'protein': array([ 0.5117382,  1.       ]),
 'region': array([ 0.        ,  0.79256944])}

1.2. Rewriting in the hierarchy

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)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):

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)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):
Instances found without pattern typing:
{1: 'EGFR', 2: 'BND_1'}
{2: 'BND_1', 1: 'SH2'}
{1: 'SH2', 2: 'Grb2'}

Instances found with pattern typing:
{1: 'EGFR', 2: 'BND_1'}

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))


Node types in `G_prime` before rewriting: 

EGFR {'G': 'protein'}
BND_1 {'G': 'binding'}
SH2 {'G': 'region'}
Grb2 {'G': 'protein'}

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)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):
Out[20]:
{'action': array([ 0.,  0.]), 'agent': array([ 0.65000734,  1.        ])}

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))


Node types in `G_prime` before rewriting: 

EGFR {'G': 'protein'}
BND_1 {'G': 'binding'}
SH2 {'G': 'region'}
Grb2 {'G': 'protein'}
3 {'G': 'region'}

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))


Node types in `G_prime` after rewriting: 

EGFR {'G': 'protein'}
BND_1 {'G': 'binding'}
SH2 {'G': 'region'}
Grb2 {'G': 'protein'}
3 {'G': 3}

In [24]:
plot_graph(newer_hierarchy.node["G_prime"].graph)
plot_graph(newer_hierarchy.node["G"].graph)
plot_graph(newer_hierarchy.node["T"].graph)


/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):
Out[24]:
{'action': array([ 0.24789213,  0.44981763]),
 'agent': array([ 0.,  0.]),
 3: array([ 1.        ,  0.88637544])}

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))


Node types in `G_prime` after rewriting: 

EGFR {'G': 'protein'}
BND_1 {'G': 'binding'}
SH2 {'G': 'region'}
Grb2 {'G': 'protein'}
3 {'G': 'region'}

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))


Graphs (directed == True): 

Nodes:
Graph: T {'name': {'Agent interaction'}}
Graph: G_prime {'name': {'EGFR and Grb2 binding'}}

Typing homomorphisms: 
G_prime -> T: total == True

Relations:

attributes : 
{}

New node types in 'G_prime':

EGFR :  {'T': 'agent'}
BND_1 :  {'T': 'action'}
SH2 :  {'T': 'agent'}
Grb2 :  {'T': 'agent'}

2. Example: advanced hierarchy

The following example illustrates more sophisticaled hierarchy example.

2.1. DAG hierarchy


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))


Node types in G3:

good_red_circle {'g1': 'red_circle', 'g2': 'good_circle'}
bad_red_circle {'g1': 'red_circle', 'g2': 'bad_circle'}
good_red_square {'g1': 'red_square', 'g2': 'good_square'}
some_circle_node {}
some_strange_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))


Node types in G3:

good_red_circle {'g1': 'red_circle', 'g2': 'good_circle'}
bad_red_circle {'g1': 'red_circle', 'g2': 'bad_circle'}
good_red_square {'g1': 'red_square', 'g2': 'good_square'}
some_circle_node {'g1': 'red_circle', 'g2': 'good_circle'}
some_strange_node {'g2': 'some_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.

2.2. Rules as nodes of a hierarchy

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)


Graphs (directed == True): 

Nodes:
Graph: colors {'id': {'https://some_url'}}
Graph: shapes {}
Graph: quality {}
Graph: g1 {}
Graph: g2 {}
Graph: g3 {}
Rule: r1 {'desc': {'Rule 1: typed by two graphs'}}

Typing homomorphisms: 
g1 -> colors: total == False
g1 -> shapes: total == False
g2 -> shapes: total == False
g2 -> quality: total == False
g3 -> g1: total == False
g3 -> g2: total == False
r1 -> g1: lhs_total == False, rhs_total == False,r1 -> g2: lhs_total == False, rhs_total == False,
Relations:

attributes : 
{}


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)


{1: 'red_circle', 2: 'red_square'}
{3: 'red_circle', 1: 'red_circle', 11: 'red_circle', 2: 'red_square'}
{1: 'good_circle', 2: 'good_square'}
{3: 'bad_circle', 1: 'good_circle', 11: 'good_circle', 2: 'good_square'}

2.3. Rewriting and propagation

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)


Instances:
{'a': 'circle', 'b': 'square'}
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:522: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(edge_color) \
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:543: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if cb.is_string_like(edge_color) or len(edge_color) == 1:
/home/eugenia/anaconda3/lib/python3.6/site-packages/networkx-1.11-py3.6.egg/networkx/drawing/nx_pylab.py:724: MatplotlibDeprecationWarning: The is_string_like function was deprecated in version 2.1.
  if not cb.is_string_like(label):
{'b': 'circle', 'a': 'square'}

In [34]:
_, m = hierarchy.rewrite("shapes", rule, {"a": "circle", "b": "square"})

In [35]:
print(hierarchy)


Graphs (directed == True): 

Nodes:
Graph: colors {'id': {'https://some_url'}}
Graph: shapes {}
Graph: quality {}
Graph: g1 {}
Graph: g2 {}
Graph: g3 {}
Rule: r1 {'desc': {'Rule 1: typed by two graphs'}}

Typing homomorphisms: 
g1 -> colors: total == False
g1 -> shapes: total == False
g2 -> shapes: total == False
g2 -> quality: total == False
g3 -> g1: total == False
g3 -> g2: total == False
r1 -> g1: lhs_total == False, rhs_total == False,r1 -> g2: lhs_total == False, rhs_total == False,
Relations:

attributes : 
{}


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)


Graph 'shapes':

===============

Nodes:

circle  :  {}
square  :  {}
circle1  :  {}

Edges:

circle -> square  :  {}
circle -> circle  :  {}
circle -> circle1  :  {}
circle1 -> square  :  {}
circle1 -> circle  :  {}
circle1 -> circle1  :  {}
========================================


Graph 'g1':

===========

Nodes:

red_circle  :  {}
red_square  :  {}
some_circle  :  {}
red_circle1  :  {}
some_circle1  :  {}

Edges:

red_circle -> red_square  :  {}
red_circle -> red_circle  :  {}
red_circle -> red_circle1  :  {}
some_circle -> red_circle  :  {}
some_circle -> red_circle1  :  {}
red_circle1 -> red_square  :  {}
red_circle1 -> red_circle  :  {}
red_circle1 -> red_circle1  :  {}
some_circle1 -> red_circle  :  {}
some_circle1 -> red_circle1  :  {}
========================================


Graph 'g2':

===========

Nodes:

good_circle  :  {}
good_square  :  {}
bad_circle  :  {}
good_guy  :  {}
some_node  :  {}
good_circle1  :  {}
bad_circle1  :  {}

Edges:

good_circle -> good_square  :  {}
bad_circle -> good_circle  :  {}
bad_circle -> bad_circle  :  {}
bad_circle -> good_circle1  :  {}
bad_circle -> bad_circle1  :  {}
good_guy -> good_square  :  {}
some_node -> good_circle  :  {}
some_node -> good_circle1  :  {}
good_circle1 -> good_square  :  {}
bad_circle1 -> good_circle  :  {}
bad_circle1 -> bad_circle  :  {}
bad_circle1 -> good_circle1  :  {}
bad_circle1 -> bad_circle1  :  {}
========================================


Graph 'g3':

===========

Nodes:

good_red_circle  :  {}
bad_red_circle  :  {}
good_red_square  :  {}
some_circle_node  :  {}
some_strange_node  :  {}
good_red_circle1  :  {}
bad_red_circle1  :  {}
some_circle_node1  :  {}

Edges:

good_red_circle -> good_red_square  :  {}
bad_red_circle -> good_red_circle  :  {}
bad_red_circle -> good_red_circle1  :  {}
good_red_circle1 -> good_red_square  :  {}
bad_red_circle1 -> good_red_circle  :  {}
bad_red_circle1 -> good_red_circle1  :  {}
========================================


Rule 'r1':

===========

LHS:

Nodes:

1  :  {}
2  :  {}

Edges:

1 -> 2  :  {}

P:

Nodes:

1  :  {}
11  :  {}
2  :  {}

Edges:

1 -> 2  :  {}

RHS:

Nodes:

1  :  {}
11  :  {}
2  :  {}
3  :  {}

Edges:

1 -> 2  :  {}

2.4 Rewriting with the rules in the hierarchy

ReGraph provides utils that allow to apply rules stored in the hierarchy to the graph nodes of the hierarchy.

In the following example the rule r1 is being applied for rewriting of the graph g3.


In [37]:
print(hierarchy.rule_lhs_typing["r1"]["g1"])
print(hierarchy.rule_rhs_typing["r1"]["g1"])
print(hierarchy.typing["g3"]["g1"])


{1: 'red_circle', 2: 'red_square'}
{3: 'red_circle', 1: 'red_circle', 11: 'red_circle', 2: 'red_square'}
{'good_red_circle': 'red_circle', 'bad_red_circle': 'red_circle', 'some_circle_node': 'red_circle', 'good_red_square': 'red_square', 'good_red_circle1': 'red_circle1', 'bad_red_circle1': 'red_circle1', 'some_circle_node1': 'red_circle1'}

In [38]:
instances = hierarchy.find_rule_matching("g3", "r1")
hierarchy.apply_rule(
    "g3",
    "r1",
    instances[0]
)


Out[38]:
(<regraph.hierarchy.Hierarchy at 0x7f6238db3c88>, None)

In [39]:
print_graph(hierarchy.node["g3"].graph)


Nodes:

good_red_circle  :  {}
bad_red_circle  :  {}
good_red_square  :  {}
some_circle_node  :  {}
some_strange_node  :  {}
good_red_circle1  :  {}
bad_red_circle1  :  {}
some_circle_node1  :  {}
good_red_circle2  :  {}
3  :  {}

Edges:

good_red_circle -> good_red_square  :  {}
bad_red_circle -> good_red_circle  :  {}
bad_red_circle -> good_red_circle1  :  {}
bad_red_circle -> good_red_circle2  :  {}
good_red_circle1 -> good_red_square  :  {}
bad_red_circle1 -> good_red_circle  :  {}
bad_red_circle1 -> good_red_circle1  :  {}
bad_red_circle1 -> good_red_circle2  :  {}

2.5 Export/load hierarchy

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]:
True

3. Example: advanced rule and rewriting

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:

  1. Strong typing of a rule (default) autocompletes the types of the nodes in a rule with the respective types of the matching.

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"
    }
)

3.1. Strong typing of a rule

Main idea of strong typing is that the typing of LHS and RHS can be inferred from the matching and autocompleted respectively. It does not allow deletion of types as every node preserved throughout the rewriting will keep its original type.


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))


Instance rewritten:  {1: 'c1', 2: 'c2'}

Instance rewritten:  {2: 'c1', 1: 'c2'}

Instance rewritten:  {1: 'c1', 2: 's1'}

Instance rewritten:  {2: 'c1', 1: 's1'}

Instance rewritten:  {1: 'c1', 2: 's2'}

Instance rewritten:  {2: 'c1', 1: 's2'}


Failed to rewrite an instance:  {1: 'c1', 2: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `2` in rhs is required (typing by the following graph stays unresolved: 'base')!


Failed to rewrite an instance:  {2: 'c1', 1: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `1` in rhs is required (typing by the following graph stays unresolved: 'base')!

Instance rewritten:  {1: 'c2', 2: 's1'}

Instance rewritten:  {2: 'c2', 1: 's1'}

Instance rewritten:  {1: 'c2', 2: 's2'}

Instance rewritten:  {2: 'c2', 1: 's2'}


Failed to rewrite an instance:  {1: 'c2', 2: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `2` in rhs is required (typing by the following graph stays unresolved: 'base')!


Failed to rewrite an instance:  {2: 'c2', 1: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `1` in rhs is required (typing by the following graph stays unresolved: 'base')!

Instance rewritten:  {1: 's1', 2: 's2'}

Instance rewritten:  {2: 's1', 1: 's2'}


Failed to rewrite an instance:  {1: 's1', 2: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `2` in rhs is required (typing by the following graph stays unresolved: 'base')!


Failed to rewrite an instance:  {2: 's1', 1: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `1` in rhs is required (typing by the following graph stays unresolved: 'base')!


Failed to rewrite an instance:  {1: 's2', 2: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `2` in rhs is required (typing by the following graph stays unresolved: 'base')!


Failed to rewrite an instance:  {2: 's2', 1: 'n1'}
Addition of an edge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Rewriting is strict (no propagation of types is allowed), typing of the node `1` in rhs is required (typing by the following graph stays unresolved: 'base')!


Nodes:

c1  :  {'a': {1}}
c2  :  {'a': {2}}
s1  :  {}
s2  :  {}
n1  :  {'x': {1}}

Edges:

c1 -> c2  :  {'c': {1}}
c1 -> s1  :  {}
c1 -> s2  :  {}
c2 -> s1  :  {}
c2 -> c1  :  {}
c2 -> s2  :  {}
s1 -> c1  :  {}
s1 -> c2  :  {}
s1 -> s2  :  {}
s2 -> n1  :  {'y': {1}}
s2 -> c1  :  {}
s2 -> c2  :  {}
s2 -> s1  :  {}


Types of nodes after rewriting:
c1 {'base': 'circle'}
c2 {'base': 'circle'}
s1 {'base': 'square'}
s2 {'base': 'square'}
n1 {}

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()


Instance rewritten:  {1: 'c1', 2: 'c2'}

Nodes:

s1  :  {}
s2  :  {}
n1  :  {'x': {1}}
c1_c2  :  {'a': {1, 2}}

Edges:

s2 -> n1  :  {'y': {1}}
c1_c2 -> c1_c2  :  {'c': {1}}
c1_c2 -> s1  :  {}


Types of nodes after rewriting:
s1 {'base': 'square'}
s2 {'base': 'square'}
n1 {}
c1_c2 {'base': ['circle']}

Instance rewritten:  {2: 'c1', 1: 'c2'}

Nodes:

s1  :  {}
s2  :  {}
n1  :  {'x': {1}}
c2_c1  :  {'a': {1, 2}}

Edges:

s2 -> n1  :  {'y': {1}}
c2_c1 -> c2_c1  :  {'c': {1}}
c2_c1 -> s1  :  {}


Types of nodes after rewriting:
s1 {'base': 'square'}
s2 {'base': 'square'}
n1 {}
c2_c1 {'base': ['circle']}


Failed to rewrite an instance:  {1: 'c1', 2: 's1'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'circle' from the lhs and as a 'square, circle' from the rhs.


Failed to rewrite an instance:  {2: 'c1', 1: 's1'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'square' from the lhs and as a 'square, circle' from the rhs.


Failed to rewrite an instance:  {1: 'c1', 2: 's2'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'circle' from the lhs and as a 'square, circle' from the rhs.


Failed to rewrite an instance:  {2: 'c1', 1: 's2'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'square' from the lhs and as a 'square, circle' from the rhs.

Instance rewritten:  {1: 'c1', 2: 'n1'}

Nodes:

c2  :  {'a': {2}}
s1  :  {}
s2  :  {}
c1_n1  :  {'a': {1}, 'x': {1}}

Edges:

c2 -> s1  :  {}
s2 -> c1_n1  :  {'y': {1}}
c1_n1 -> c2  :  {'c': {1}}


Types of nodes after rewriting:
c2 {'base': 'circle'}
s1 {'base': 'square'}
s2 {'base': 'square'}
c1_n1 {'base': ['circle']}

Instance rewritten:  {2: 'c1', 1: 'n1'}

Nodes:

c2  :  {'a': {2}}
s1  :  {}
s2  :  {}
n1_c1  :  {'x': {1}, 'a': {1}}

Edges:

c2 -> s1  :  {}
s2 -> n1_c1  :  {'y': {1}}
n1_c1 -> c2  :  {'c': {1}}


Types of nodes after rewriting:
c2 {'base': 'circle'}
s1 {'base': 'square'}
s2 {'base': 'square'}
n1_c1 {'base': ['circle']}


Failed to rewrite an instance:  {1: 'c2', 2: 's1'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'circle' from the lhs and as a 'square, circle' from the rhs.


Failed to rewrite an instance:  {2: 'c2', 1: 's1'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'square' from the lhs and as a 'square, circle' from the rhs.


Failed to rewrite an instance:  {1: 'c2', 2: 's2'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'circle' from the lhs and as a 'square, circle' from the rhs.


Failed to rewrite an instance:  {2: 'c2', 1: 's2'}
Merge was not allowed, error message received:
Exception type:  <class 'regraph.exceptions.RewritingError'>
Message:  Inconsistent typing of the rule: node '1' from the preserved part is typed by a graph 'base' as 'square' from the lhs and as a 'square, circle' from the rhs.

Instance rewritten:  {1: 'c2', 2: 'n1'}

Nodes:

c1  :  {'a': {1}}
s1  :  {}
s2  :  {}
c2_n1  :  {'a': {2}, 'x': {1}}

Edges:

c1 -> c2_n1  :  {'c': {1}}
s2 -> c2_n1  :  {'y': {1}}
c2_n1 -> s1  :  {}


Types of nodes after rewriting:
c1 {'base': 'circle'}
s1 {'base': 'square'}
s2 {'base': 'square'}
c2_n1 {'base': ['circle']}

Instance rewritten:  {2: 'c2', 1: 'n1'}

Nodes:

c1  :  {'a': {1}}
s1  :  {}
s2  :  {}
n1_c2  :  {'x': {1}, 'a': {2}}

Edges:

c1 -> n1_c2  :  {'c': {1}}
s2 -> n1_c2  :  {'y': {1}}
n1_c2 -> s1  :  {}


Types of nodes after rewriting:
c1 {'base': 'circle'}
s1 {'base': 'square'}
s2 {'base': 'square'}
n1_c2 {'base': ['circle']}

Instance rewritten:  {1: 's1', 2: 's2'}

Nodes:

c1  :  {'a': {1}}
c2  :  {'a': {2}}
n1  :  {'x': {1}}
s1_s2  :  {}

Edges:

c1 -> c2  :  {'c': {1}}
c2 -> s1_s2  :  {}
s1_s2 -> n1  :  {'y': {1}}


Types of nodes after rewriting:
c1 {'base': 'circle'}
c2 {'base': 'circle'}
n1 {}
s1_s2 {'base': ['square']}

Instance rewritten:  {2: 's1', 1: 's2'}

Nodes:

c1  :  {'a': {1}}
c2  :  {'a': {2}}
n1  :  {'x': {1}}
s2_s1  :  {}

Edges:

c1 -> c2  :  {'c': {1}}
c2 -> s2_s1  :  {}
s2_s1 -> n1  :  {'y': {1}}


Types of nodes after rewriting:
c1 {'base': 'circle'}
c2 {'base': 'circle'}
n1 {}
s2_s1 {'base': ['square']}

Instance rewritten:  {1: 's1', 2: 'n1'}

Nodes:

c1  :  {'a': {1}}
c2  :  {'a': {2}}
s2  :  {}
s1_n1  :  {'x': {1}}

Edges:

c1 -> c2  :  {'c': {1}}
c2 -> s1_n1  :  {}
s2 -> s1_n1  :  {'y': {1}}


Types of nodes after rewriting:
c1 {'base': 'circle'}
c2 {'base': 'circle'}
s2 {'base': 'square'}
s1_n1 {'base': ['square']}

Instance rewritten:  {2: 's1', 1: 'n1'}

Nodes:

c1  :  {'a': {1}}
c2  :  {'a': {2}}
s2  :  {}
n1_s1  :  {'x': {1}}

Edges:

c1 -> c2  :  {'c': {1}}
c2 -> n1_s1  :  {}
s2 -> n1_s1  :  {'y': {1}}


Types of nodes after rewriting:
c1 {'base': 'circle'}
c2 {'base': 'circle'}
s2 {'base': 'square'}
n1_s1 {'base': ['square']}

Instance rewritten:  {1: 's2', 2: 'n1'}

Nodes:

c1  :  {'a': {1}}
c2  :  {'a': {2}}
s1  :  {}
s2_n1  :  {'x': {1}}

Edges:

c1 -> c2  :  {'c': {1}}
c2 -> s1  :  {}
s2_n1 -> s2_n1  :  {'y': {1}}


Types of nodes after rewriting:
c1 {'base': 'circle'}
c2 {'base': 'circle'}
s1 {'base': 'square'}
s2_n1 {'base': ['square']}

Instance rewritten:  {2: 's2', 1: 'n1'}

Nodes:

c1  :  {'a': {1}}
c2  :  {'a': {2}}
s1  :  {}
n1_s2  :  {'x': {1}}

Edges:

c1 -> c2  :  {'c': {1}}
c2 -> s1  :  {}
n1_s2 -> n1_s2  :  {'y': {1}}


Types of nodes after rewriting:
c1 {'base': 'circle'}
c2 {'base': 'circle'}
s1 {'base': 'square'}
n1_s2 {'base': ['square']}

#### 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.

4. Merging with a hierarchy

4.1. Example: merging disjoint hierarchies (merge by ids)


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)


Graphs (directed == True): 

Nodes:
Graph: 1 {'name': {'Main hierarchy'}}
Graph: 2 {'name': {'Base hierarchy'}}
Graph: 3 {}
Graph: 4 {}
Graph: 1_1 {'name': {'Main hierarchy'}}
Graph: 2_1 {'name': {'Base hierarchy'}}
Graph: 3_1 {}
Graph: 4_1 {}

Typing homomorphisms: 
1 -> 2: total == False
1 -> 4: total == False
2 -> 3: total == False
4 -> 3: total == False
1_1 -> 4_1: total == False
1_1 -> 2_1: total == False
2_1 -> 3_1: total == False
4_1 -> 3_1: total == False

Relations:

attributes : 
{}

4.2. Example: merging hierarchies with common nodes


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)


Graphs (directed == True): 

Nodes:
Graph: 1 {'name': {'Main hierarchy'}}
Graph: 2 {'name': {'Base hierarchy'}}
Graph: 3 {}
Graph: 4 {}
Graph: 2_1 {'name': {'Base hierarchy'}}
Graph: 3_1 {}
Graph: 4_1 {}

Typing homomorphisms: 
1 -> 2: total == False
1 -> 4: total == False
1 -> 4_1: total == False
1 -> 2_1: total == False
2 -> 3: total == False
4 -> 3: total == False
2_1 -> 3_1: total == False
4_1 -> 3_1: total == False

Relations:

attributes : 
{}


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)


Graphs (directed == True): 

Nodes:
Graph: 1 {'name': {'Main hierarchy'}}
Graph: 2 {'name': {'Base hierarchy'}}
Graph: 3 {}
Graph: 4 {}
Graph: 3_1 {}
Graph: 4_1 {}

Typing homomorphisms: 
1 -> 2: total == False
1 -> 4: total == False
1 -> 4_1: total == False
2 -> 3: total == False
2 -> 3_1: total == False
4 -> 3: total == False
4_1 -> 3_1: total == False

Relations:

attributes : 
{}

{1: 1, 2: 2}

In [52]:
hierarchy4.merge_by_attr(other_hierarchy, "name")


Out[52]:
{1: '1_1', 2: '2_2'}

In [53]:
print(hierarchy4)
print(hierarchy4.edge['1_1']['2_2'].mapping)


Graphs (directed == True): 

Nodes:
Graph: 3 {}
Graph: 4 {}
Graph: 1_1 {'name': {'Main hierarchy'}}
Graph: 2_2 {'name': {'Base hierarchy'}}
Graph: 3_1 {}
Graph: 4_1 {}

Typing homomorphisms: 
4 -> 3: total == False
1_1 -> 4: total == False
1_1 -> 2_2: total == False
1_1 -> 4_1: total == False
2_2 -> 3: total == False
2_2 -> 3_1: total == False
4_1 -> 3_1: total == False

Relations:

attributes : 
{}

{1: 1, 2: 2}