Rules

Graph rewriting rules.

This package contains the Rule data structure for representation of graph rewriting rules (for more on sesqui-pushout rewriting see: https://link.springer.com/chapter/10.1007/11841883_4).

class regraph.rules.Rule(p=None, lhs=None, rhs=None, p_lhs=None, p_rhs=None)[source]

Class representing rewriting rules.

A rewriting rule consists of the three graphs: p – preserved part (or interface), 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 p -> lhs mapping 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.

Attributes
pregaph.graphs.Graph

Preserved part of the rule

lhsregaph.graphs.Graph

Left-hand side (pattern) of the rule

rhsregaph.graphs.Graph

Right-hand side of the rule

p_lhsdict

Homomorphism between p and lhs given by a dictionary with keys – nodes of p, values – nodes of lhs.

p_rhsdict

Homomorphism between p and rhs given by a dictionary with keys – nodes of p, values – nodes of rhs.

Methods

added_edge_attrs(self)

Get edge attributes added by the rule.

added_edges(self)

Get edges added by the rule.

added_node_attrs(self)

Get node attributes added by the rule.

added_nodes(self)

Get nodes added by the rule.

cloned_nodes(self)

Get nodes cloned by the rule.

from_json(json_data)

Create a rule obj from JSON repr.

from_transform(pattern[, commands])

Initialize a rule from the transformation.

get_inverted_rule(self)

Get inverted rule with LHS and RHS swaped.

identity_rule()

Create an identity rule.

inject_add_edge(self, n1, n2[, attrs])

Inject addition of a new edge to the rule.

inject_add_edge_attrs(self, n1, n2, attrs)

Inject addition of edge attributes by the rule.

inject_add_edges_from(self, edge_list)

Inject addition of a new edge to the rule.

inject_add_node(self, node_id[, attrs])

Inject an addition of a new node by the rule.

inject_add_node_attrs(self, n, attrs)

Inject addition of node attributes by the rule.

inject_add_nodes_from(self, node_list)

Inject an addition of a new node by the rule.

inject_clone_node(self, n[, new_node_id])

Inject cloning of a node by the rule.

inject_merge_nodes(self, node_list[, node_id])

Inject merge of a collection of nodes by the rule.

inject_remove_edge(self, n1, n2)

Inject removal of an edge by the rule.

inject_remove_edge_attrs(self, n1, n2, attrs)

Inject a removal of edge attrs by the rule.

inject_remove_node(self, p_node_id)

Inject a new node removal to the rule.

inject_remove_node_attrs(self, n, attrs)

Inject a removal of node attrs by the rule.

inject_update_edge_attrs(self, n1, n2, attrs)

Inject an update of edge attrs by the rule.

inject_update_node_attrs(self, n, attrs)

Inject an update of node attrs by the rule.

is_identity(self)

Test if the rule is identity.

is_relaxing(self)

Check if the rule is relaxing.

is_restrictive(self)

Check if the rule is restrictive.

merged_nodes(self)

Get nodes merged by the rule.

plot(self[, filename, title])

Plot the rule.

refine(self, graph, instance)

Get refined (side-effect-free) version of the rule.

removed_edge_attrs(self)

Get edge attributes removed by the rule.

removed_edges(self)

Get edges removed by the rule.

removed_node_attrs(self)

Get node attributes removed by the rule.

removed_nodes(self)

Get nodes removed by the rule.

to_commands(self)

Convert the rule to a list of commands.

to_json(self)

Convert the rule to JSON repr.

added_edge_attrs(self)[source]

Get edge attributes added by the rule.

Returns
attrsdict

Dictionary where keys are edges from rhs and values are attribute dictionaries to add.

added_edges(self)[source]

Get edges added by the rule.

Returns
edgesset

Set of edges from rhs added by the rule.

added_node_attrs(self)[source]

Get node attributes added by the rule.

Returns
attrsdict

Dictionary where keys are nodes from rhs and values are attribute dictionaries to add.

added_nodes(self)[source]

Get nodes added by the rule.

Returns
nodesset

Set of nodes from rhs added by the rule.

cloned_nodes(self)[source]

Get nodes cloned by the rule.

Returns
nodesdict

Dictionary where keys are nodes from lhs and values are sets of corresponding nodes from p.

classmethod from_json(json_data)[source]

Create a rule obj from JSON repr.

classmethod from_transform(pattern, commands=None)[source]

Initialize a rule from the transformation.

On input takes a pattern which is used as lhs of the rule, as an optional argument transformation commands can be provided, by default the list of commands is empty and all p, lhs and rhs are initialized to be the same graph (pattern), later on when transformations are applied p and rhs are being updated. If list of commands is specified, these commands are simplified, transformed to the canonical order, and applied to p, lhs and rhs.

Parameters
patternnetworkx.(Di)Graph

Pattern graph to initialize and the lhs of the rule.

commandsstr, optional

Script containing transformation commands, which can be parsed by regraph.parser.parse.

get_inverted_rule(self)[source]

Get inverted rule with LHS and RHS swaped.

classmethod identity_rule()[source]

Create an identity rule.

inject_add_edge(self, n1, n2, attrs=None)[source]

Inject addition of a new edge to the rule.

This method adds an edge between two nodes of the rhs.

Parameters
n1hashable

Id of an edge’s source node in rhs.

n2hashable

Id of an edge’s target node in rhs.

Raises
RuleError

If some of the nodes (n1 or n2) do not exist or if there is already an edge between them in rhs.

inject_add_edge_attrs(self, n1, n2, attrs)[source]

Inject addition of edge attributes by the rule.

Parameters
n1hashable

Source node in the RHS

n2hashable

Target node in the RHS

attrsdict

Dictionary with attrs to add

Raises
RuleError

If some of the nodes defining an edge are not found in neither rhs, or if an edge is incident to smth thats is going to be removed by the rule.

inject_add_edges_from(self, edge_list)[source]

Inject addition of a new edge to the rule.

This method injects addition of edges from the list.

Parameters
edge_listiterable

Collection of edges to add, where every element is either a tuple of the form (<source_id>, <target_id>) or (<source_id>, <target_id>, <edge_attrs>). Here source and target nodes are assumed to be from the rhs.

Raises
RuleError

If some of the nodes (n1 or n2) do not exist or if there is already an edge between them in rhs.

inject_add_node(self, node_id, attrs=None)[source]

Inject an addition of a new node by the rule.

This method adds a node with node_id (and the specified attributes attrs) to rhs.

Parameters
node_idhashable

Id of a node to add

attrsdict, optional

Attributes of the node.

Raises
RuleError

If node with this id already exists in the rhs.

inject_add_node_attrs(self, n, attrs)[source]

Inject addition of node attributes by the rule.

Parameters
nhashable

Id of the node in the rhs to add attributes to.

attrsdict

Dictionary with attrs to add

Raises
RuleError

If node n does not exist in the rhs of the rule

inject_add_nodes_from(self, node_list)[source]

Inject an addition of a new node by the rule.

This method adds a nodes from the list (and the specified attributes attrs) to rhs.

Parameters
node_listiterable

Collection of nodes to add, where every element is either a tuple of the form (<node_id>, <node_attrs>) or a single value <node_id>

Raises
RuleError

If some node from the list already exists in the rhs.

inject_clone_node(self, n, new_node_id=None)[source]

Inject cloning of a node by the rule.

This procedure clones n in the preserved part and the right-hand side.

Parameters
nhashable

Node from lhs to clone

new_node_idhashable

Id for the clone

Returns
p_new_node_idhashable

Id of the new clone node in the preserved part

rhs_new_node_idhashable

Id of the new clone node in the right-hand side

Raises
RuleError

If the node to clone is already being removed by the rule or if node with the specified clone id already exists in p.

inject_merge_nodes(self, node_list, node_id=None)[source]

Inject merge of a collection of nodes by the rule.

Parameters
node_listiterable

Collection of ids of nodes from the preserved part.

node_idhashable

Id of the new node corresponding to the result of merge.

Returns
new_namehashable

Id of the new node corresponding to the result of merge.

Raises
RuleError

If a node with some id specified in node_list does not exist in the preserved part of the rule.

inject_remove_edge(self, n1, n2)[source]

Inject removal of an edge by the rule.

Parameters
n1hashable

Id of an edge’s source node in p.

n2hashable

Id of an edge’s target node in p.

Raises
RuleError

If some of the nodes are not found in p, or if a corresponding edge in p does not exist.

inject_remove_edge_attrs(self, n1, n2, attrs)[source]

Inject a removal of edge attrs by the rule.

Parameters
n1hashable

Id of an edge’s source node in p.

n2hashable

Id of an edge’s target node in p.

attrsdict

Dictionary with attributes to remove.

Raises
RuleError

If edge n1-> n2 does not exist in the preserved part of the rule, or when the node whose attrs should be removed is itself is being removed by the rule.

inject_remove_node(self, p_node_id)[source]

Inject a new node removal to the rule.

This method removes the indicated node from p

Parameters
p_node_id

Id of the node in p that should be removed by the rule.

inject_remove_node_attrs(self, n, attrs)[source]

Inject a removal of node attrs by the rule.

Parameters
nhashable

Id of a node whose attrs to remove (node from the preserved part).

attrsdict

Dictionary with attributes to remove.

Raises
RuleError

If n does not exist in the preserved part of the rule, or when the node whose attrs should be removed is itself is being removed by the rule.

inject_update_edge_attrs(self, n1, n2, attrs)[source]

Inject an update of edge attrs by the rule.

inject_update_node_attrs(self, n, attrs)[source]

Inject an update of node attrs by the rule.

Parameters
nhashable

Id of a node from the left-hand side whose attrs should be updated

attrsdict

Dictionary of new attrs that will replace the old ones

Raises
RuleError

If node n does not exist in the left-hand side or is being removed by the rule.

is_identity(self)[source]

Test if the rule is identity.

is_relaxing(self)[source]

Check if the rule is relaxing.

Rule is relaxing if it adds nodes/edges/attributes or merges nodes.

Returns
True if the rule is relaxing, False otherwise
is_restrictive(self)[source]

Check if the rule is restrictive.

Rule is restictive if it removes nodes/edges/attributes or clones nodes.

Returns
True if the rule is restrictive, False
otherwise
merged_nodes(self)[source]

Get nodes merged by the rule.

Returns
nodesdict

Dictionary where keys are nodes from rhs and values are sets of nodes from p that are merged.

plot(self, filename=None, title=None)[source]

Plot the rule.

refine(self, graph, instance)[source]

Get refined (side-effect-free) version of the rule.

removed_edge_attrs(self)[source]

Get edge attributes removed by the rule.

Returns
attrsdict

Dictionary where keys are edges from p and values are attribute dictionaries to remove.

removed_edges(self)[source]

Get edges removed by the rule.

Returns
edgesset

Set of edges from lhs removed by the rule.

removed_node_attrs(self)[source]

Get node attributes removed by the rule.

Returns
attrsdict

Dictionary where keys are nodes from p and values are attribute dictionaries to remove.

removed_nodes(self)[source]

Get nodes removed by the rule.

Returns
nodesset

Set of nodes from lhs removed by the rule.

to_commands(self)[source]

Convert the rule to a list of commands.

This method produces a list of commands corresponding to the rule. These commands follow a simple grammar of transformations that can be recognized by regraph.parser module.

Returns
commandsstr

Commands representing primitive transformations on the the lhs that are preformed in the rule.

to_json(self)[source]

Convert the rule to JSON repr.

regraph.rules.compose_rule_hierarchies(rule_hierarchy1, lhs_instances1, rhs_instances1, rule_hierarchy2, lhs_instances2, rhs_instances2)[source]

Compose two rule hierarchies.

regraph.rules.compose_rules(rule1, lhs_instance1, rhs_instance1, rule2, lhs_instance2, rhs_instance2, return_all=False)[source]

Compose two rules respecting instances.

regraph.rules.invert_rule_hierarchy(rule_hierarchy)[source]

Get inverted rule hierarchy (swapped lhs and rhs).