Hierarchies

Abstract hierarchies of graphs in ReGraph.

This module contains abstact data structures for graph hierarchies. A graph hierarchy is a DAG, whose nodes are graphs and whose directed edges represent homomorphisms between graphs. In addition, hierarchies are equipped with relations on graphs (which can be thought of as undirected edges or, alternatively, spans).

class regraph.hierarchies.Hierarchy

Abstract class for graph hierarchy objects in ReGraph.

A graph hierarchy is a DAG, where nodes are graphs with attributes and edges are homomorphisms representing graph typing in the system.

Methods

add_empty_graph(self, graph_id[, attrs])	“Add a new empty graph to the hierarchy.
add_graph(self, graph_id, graph[, graph_attrs])	Add a new graph to the hierarchy.
add_graph_from_data(self, graph_id, …[, attrs])	Add a new graph to the hierarchy from the input node/edge lists.
add_graph_from_json(self, graph_id, json_data)	Add a new graph to the hirarchy from its JSON-reprsentation.
add_relation(self, left, right, relation[, …])	Add relation to the hierarchy.
add_typing(self, source, target, mapping[, …])	Add homomorphism to the hierarchy.
adjacent_relations(self, g)	Return a list of related graphs.
apply_rule_hierarchy(self, rule_hierarchy, …)	Apply rule hierarchy.
bfs_tree(self, graph[, reverse])	BFS tree from the graph to all other reachable graphs.
compose_path_typing(self, path)	Compose homomorphisms along the path.
copy_graph(self, graph_id, new_graph_id[, …])	Create a copy of a graph in a hierarchy.
duplicate_subgraph(self, graph_dict[, …])	Duplicate a subgraph induced by the set of nodes.
export(self, filename)	Export the hierarchy to a file.
find_matching(self, graph_id, pattern[, …])	Find an instance of a pattern in a specified graph.
from_json(json_data[, ignore])	Create a hierarchy object from JSON-representation.
get_ancestors(self, graph_id)	Return ancestors of a graph with the typing morphisms.
get_descendants(self, graph_id[, maybe])	Return descendants of a graph with the typing morphisms.
get_graph(self, graph_id)	Get a graph object associated to the node ‘graph_id’.
get_graph_attrs(self, graph_id)	Get attributes of a graph in the hierarchy.
get_relation(self, left_id, right_id)	Get a relation dict associated to the rel ‘left_id->target_id’.
get_relation_attrs(self, left, right)	Get attributes of a reltion in the hierarchy.
get_rule_hierarchy(self, origin_id, rule[, …])	Find rule hierarchy corresponding to the input rewriting.
get_typing(self, source_id, target_id)	Get a typing dict associated to the edge ‘source_id->target_id’.
get_typing_attrs(self, source, target)	Get attributes of a typing in the hierarchy.
graphs(self[, data])	Return a list of graphs in the hierarchy.
graphs_typed_by_node(self, graph_id, node_id)	Get graphs typed by ‘node_id’ in ‘graph_id’.
load(filename[, ignore])	Load the hierarchy from a file.
new_apply_rule_hierarchy(self, …)	Apply rule hierarchy.
node_type(self, graph_id, node_id)	Get a list of the immediate types of a node.
predecessors(self, node_id)	Return the set of predecessors.
refine_rule_hierarchy(self, rule_hierarchy, …)	Refine the input rule hierarchy to its reversible version.
relabel_graph(self, graph_id, new_graph_id)	Relabel a graph in the hierarchy.
relabel_graph_node(self, graph_id, node, …)	Rename a node in a graph of the hierarchy.
relabel_graphs(self, mapping)	Relabel graphs in the hierarchy.
relabel_nodes(self, graph, mapping)	Relabel nodes of a graph in the hierarchy.
relation_to_span(self, left, right[, edges, …])	Convert relation to a span.
relations(self[, data])	Return a list of relations.
remove_graph(self, graph_id[, reconnect])	Remove graph from the hierarchy.
remove_relation(self, left, right)	Remove a relation from the hierarchy.
remove_typing(self, s, t)	Remove a typing from the hierarchy.
rewrite(self, graph_id, rule, instance[, …])	Rewrite and propagate the changes backward & forward.
set_graph_attrs(self, node_id, attrs)	Set attributes of a graph in the hierarchy.
set_node_relation(self, left_graph, …)	Set relation for a particular node.
set_relation_attrs(self, left, right, attrs)	Set attributes of a relation in the hierarchy.
set_typing_attrs(self, source, target, attrs)	Set attributes of a typing in the hierarchy.
shortest_path(self, source, target)	Shortest path from ‘source’ to ‘target’.
successors(self, node_id)	Return the set of successors.
to_json(self[, rename_nodes])	Return json representation of the hierarchy.
typings(self[, data])	Return a list of graph typing edges in the hierarchy.
unique_graph_id(self, prefix)	Generate a new graph id starting with a prefix.

abstract add_empty_graph(self, graph_id, attrs=None)

“Add a new empty graph to the hierarchy.

Parameters

graph_idhashable

Id of a new node in the hierarchy

graph_attrsdict, optional

Dictionary containing attributes of the new node

abstract add_graph(self, graph_id, graph, graph_attrs=None)

Add a new graph to the hierarchy.

Parameters

graph_idhashable

Id of a new node in the hierarchy

graphregraph.Graph

Graph object corresponding to the new node of the hierarchy

graph_attrsdict, optional

Dictionary containing attributes of the new node

abstract add_graph_from_data(self, graph_id, node_list, edge_list, attrs=None)

Add a new graph to the hierarchy from the input node/edge lists.

Parameters

graph_idhashable

Id of a new node in the hierarchy

node_listiterable

List of nodes (with attributes)

edge_listiterable

List of edges (with attributes)

graph_attrsdict, optional

Dictionary containing attributes of the new node

add_graph_from_json(self, graph_id, json_data, attrs=None)

Add a new graph to the hirarchy from its JSON-reprsentation.

Parameters

graph_idhashable

Id of the new graph

json_datadict

JSON-like dictionary containing the representation of the graph

attrsdict

Attributes to attach to the new graph

abstract add_relation(self, left, right, relation, attrs=None)

Add relation to the hierarchy.

This method adds a relation between two graphs in the hierarchy corresponding to the nodes with ids left and right, the relation itself is defined by a dictionary relation, where a key is a node in the left graph and its corresponding value is a set of nodes from the right graph to which the node is related. Relations in the hierarchy are symmetric (see example below).

Parameters

left

Id of the hierarchy’s node represening the left graph

right

Id of the hierarchy’s node represening the right graph

relationdict

Dictionary representing a relation of nodes from left to the nodes from right, a key of the dictionary is assumed to be a node from left and its value a set of ids of related nodes from right

attrsdict

Dictionary containing attributes of the new relation

Raises

HierarchyError

This error is raised in the following cases:

• node with id left/right is not defined in the hierarchy;

• node with id left/right is not a graph;

• a relation between left and right already exists;

• some node ids specified in relation are not found in the

left/right graph.

abstract add_typing(self, source, target, mapping, attrs=None)

Add homomorphism to the hierarchy.

Parameters

sourcehashable

Id of the source graph node of typing

targethashable

Id of the target graph node of typing

mappingdict

Dictionary representing a mapping of nodes from the source graph to target’s nodes

attrsdict

Dictionary containing attributes of the new typing edge

Raises

HierarchyError

This error is raised in the following cases:

• source or target ids are not found in the hierarchy

• a typing edge between source and target already exists

• addition of an edge between source and target creates

a cycle or produces paths that do not commute with some already existing paths

InvalidHomomorphism

If a homomorphisms from a graph at the source to a graph at the target given by mapping is not a valid homomorphism.

adjacent_relations(self, g)

Return a list of related graphs.

apply_rule_hierarchy(self, rule_hierarchy, instances)

Apply rule hierarchy.

Parameters

rule_hierarchydict

Dictionary containing the input rule hierarchy

instancesdict

Dictionary containing an instance for every rule in the hierarchy

Returns

rhs_instancesdict

Dictionary containing the RHS instances for every graph in the hierarchy

abstract bfs_tree(self, graph, reverse=False)

BFS tree from the graph to all other reachable graphs.

compose_path_typing(self, path)

Compose homomorphisms along the path.

Parameters

pathlist

List of nodes of the hierarchy forming a path

Returns

If source node of the path is a graph

homomorphismdict

Dictionary containg the typing of the nodes from the source graph of the path by the nodes of the target graph

if source node of the path is a rule

lhs_homomorphismdict

Dictionary containg the typing of the nodes from the left-hand side of the source rule of the path by the nodes of the target graph

rhs_homomorphismdict

Dictionary containg the typing of the nodes from the right-hand side of the source rule of the path by the nodes of the target graph

abstract copy_graph(self, graph_id, new_graph_id, attach_graphs=[])

Create a copy of a graph in a hierarchy.

duplicate_subgraph(self, graph_dict, attach_graphs=[])

Duplicate a subgraph induced by the set of nodes.

Parameters

graph_dictdict

Dictionary contaning names of graphs to duplicate as keys and their new IDs in the hierarchy as values

attach_graphslist, optional

List of not duplicated graph IDs that should be reattached to the duplicated graphs, if empty, duplicated subgraph is disconnected from the rest of the hierarchy

export(self, filename)

Export the hierarchy to a file.

find_matching(self, graph_id, pattern, pattern_typing=None, nodes=None)

Find an instance of a pattern in a specified graph.

Parameters

graph_idhashable

Id of a graph in the hierarchy to search for matches

patternGraph object

A pattern to match

pattern_typingdict

A dictionary that specifies a typing of a pattern, keys of the dictionary – graph id that types a pattern, this graph should be among parents of the graph_id graph; values are mappings of nodes from pattern to the typing graph;

nodesiterable

Subset of nodes where matching should be performed

Returns

instanceslist of dict

List of matched instances

classmethod from_json(json_data, ignore=None)

Create a hierarchy object from JSON-representation.

Parameters

json_datadict

JSON-like dict containing representation of a hierarchy

ignoredict, optional

Dictionary containing components to ignore in the process of converting from JSON, dictionary should respect the following format: {

“graphs”: <collection of ids of graphs to ignore>, “rules”: <collection of ids of rules to ignore>, “typing”: <collection of tuples containing typing

edges to ignore>,

“rule_typing”: <collection of tuples containing rule

typing edges to ignore>>,

“relations”: <collection of tuples containing

relations to ignore>,

}

Returns

hierarchyregraph.hierarchies.Hierarchy

get_ancestors(self, graph_id)

Return ancestors of a graph with the typing morphisms.

get_descendants(self, graph_id, maybe=None)

Return descendants of a graph with the typing morphisms.

abstract get_graph(self, graph_id)

Get a graph object associated to the node ‘graph_id’.

abstract get_graph_attrs(self, graph_id)

Get attributes of a graph in the hierarchy.

Parameters

graph_idhashable

Id of the graph

abstract get_relation(self, left_id, right_id)

Get a relation dict associated to the rel ‘left_id->target_id’.

abstract get_relation_attrs(self, left, right)

Get attributes of a reltion in the hierarchy.

Parameters

lefthashable

Id of the left graph

righthashable

Id of the right graph

get_rule_hierarchy(self, origin_id, rule, instance=None, p_typing=None, rhs_typing=None)

Find rule hierarchy corresponding to the input rewriting.

Parameters

graph_idhashable

Id of the graph to rewrite

ruleregraph.Rule

Rewriting rule

instancedict, optional

Instance of the rule in the graph. If not specified, the identity of the left-hand side is used

p_typingdict

Relations controlling backward propagation. The keys are ancestors of the rewritten graph, values are dictionaries containing individual relations between the nodes of a given ancestor and the preserved part of the rule

rhs_typingdict

Relation controlling forward propagation. The keys are descendants of the rewritten graph, values are dictionaries containing individual relations between the right-hand side of the rule and the nodes of a given descendant

Returns

——-

rule_hierarchydictionary

Dictionary contains two keys: (1) rules whose value is a dictionary with id’s of the graphs in the hierarchy and the computed propagation rules; (2) rule_homomorphisms whose value is a dictionary with pairs of graphs in the hierarchy and the computed homomorphisms between rules.

abstract get_typing(self, source_id, target_id)

Get a typing dict associated to the edge ‘source_id->target_id’.

abstract get_typing_attrs(self, source, target)

Get attributes of a typing in the hierarchy.

Parameters

sourcehashable

Id of the source graph

targethashable

Id of the target graph

abstract graphs(self, data=False)

Return a list of graphs in the hierarchy.

graphs_typed_by_node(self, graph_id, node_id)

Get graphs typed by ‘node_id’ in ‘graph_id’.

classmethod load(filename, ignore=None)

Load the hierarchy from a file.

Parameters

filenamestr

Path to the file containing JSON-representation of the hierarchy

ignoredict

Dictionary with graph elemenets to ignore when loading

Returns

——-

hierarchyregraph.hierarchies.Hierarchy

new_apply_rule_hierarchy(self, rule_hierarchy, instances)

Apply rule hierarchy.

Parameters

rule_hierarchydict

Dictionary containing the input rule hierarchy

instancesdict

Dictionary containing an instance for every rule in the hierarchy

Returns

rhs_instancesdict

Dictionary containing the RHS instances for every graph in the hierarchy

node_type(self, graph_id, node_id)

Get a list of the immediate types of a node.

abstract predecessors(self, node_id)

Return the set of predecessors.

refine_rule_hierarchy(self, rule_hierarchy, instances)

Refine the input rule hierarchy to its reversible version.

Parameters

rule_hierarchydict

Rule hierarchy to refine

instancesdict of dict

Dictionary containing ids of the graphs in the hierarchy as keys and dictionaries represening instances of the corresponding rules

Returns

new_instancesdict of dict

Dictionary containing ids of the graphs in the hierarchy as keys and dictionaries represening new instances of the corresponding refined rules

abstract relabel_graph(self, graph_id, new_graph_id)

Relabel a graph in the hierarchy.

Parameters

graph_idhashable

Id of the graph to relabel

new_graph_idhashable

New graph id to assign to this graph

abstract relabel_graph_node(self, graph_id, node, new_name)

Rename a node in a graph of the hierarchy.

abstract relabel_graphs(self, mapping)

Relabel graphs in the hierarchy.

Parameters

mapping: dict

A dictionary with keys being old graph ids and their values being new id’s of the respective graphs.

Raises

ReGraphError

If new id’s do not define a set of distinct graph id’s.

relabel_nodes(self, graph, mapping)

Relabel nodes of a graph in the hierarchy.

relation_to_span(self, left, right, edges=False, attrs=False)

Convert relation to a span.

This method computes the span of the form left <- common -> right from a binary symmetric relation between two graphs in the hierarchy.

Parameters

left

Id of the hierarchy’s node represening the left graph

right

Id of the hierarchy’s node represening the right graph

edgesbool, optional

If True, maximal set of edges is added to the common part graph

attrsbool, optional

If True, maximal dict of attrs is added to the nodes of the common part graph

Returns

commonnx.(Di)Graph

Graph representing the common part graph induced by the relation

left_hdict

Homomorphism from the common part graph to the left graph of the relation

right_hdict

Homomorphism from the common part graph to the right graph of the relation

Raises

HierarchyError

If nodes corresponding to either left or right ids do not exist in the hierarchy, or there is no relation between them.

abstract relations(self, data=False)

Return a list of relations.

abstract remove_graph(self, graph_id, reconnect=False)

Remove graph from the hierarchy.

Removes a graph from the hierarchy, if the reconnect parameter is set to True, adds typing from the predecessors of the removed node to all its successors, by composing the homomorphisms (for every predecessor p and for every successor ‘s’ composes two homomorphisms p->`node_id` and node_id->`s`, then removes node_id and all its incident edges, by which makes node’s removal a procedure of ‘forgetting’ one level of ‘abstraction’).

Parameters

node_id

Id of a graph to remove

reconnectbool

Reconnect the descendants of the removed node to its predecessors

Raises

HierarchyError

If graph with node_id is not defined in the hierarchy

abstract remove_relation(self, left, right)

Remove a relation from the hierarchy.

abstract remove_typing(self, s, t)

Remove a typing from the hierarchy.

rewrite(self, graph_id, rule, instance, p_typing=None, rhs_typing=None, strict=False)

Rewrite and propagate the changes backward & forward.

Rewriting in the hierarchy cosists of an application of the SqPO-rewriting rule (given by the ‘rule’ parameter) to a graph in the hierarchy. Such rewriting often triggers a set of changes that are applied to other graphs and homomorphisms in the hierarchy, which are necessary to ensure that the hierarchy stays consistent. If the rule is restrictive (deletes nodes/edges/attrs or clones nodes), in general, the respective changes to all the graphs (transitively) typed by the graph subject to rewriting are made. On the other hand, if the rule is relaxing (adds nodes/edges/attrs or merges nodes), in general, the respective changes to all the graphs that (tansitively) type the graph subject to rewriting are made.

Parameters

graph_id

Id of the graph in the hierarchy to rewrite

ruleregraph.rule.Rule

Rule object to apply

instancedict, optional

Dictionary containing an instance of the lhs of the rule in the graph subject to rewriting, by default, tries to construct identity morphism of the nodes of the pattern

p_typingdict, optional

Dictionary containing typing of graphs in the hierarchy by the interface of the rule, keys are ids of hierarchy graphs, values are dictionaries containing the mapping of nodes from the hierarchy graphs to the inteface nodes (note that a node from a graph can be typed by a set of nodes in the interface of the rule, e.g. if we want to perform cloning of some types, etc).

rhs_typingdict, optional

Dictionary containing typing of the rhs by graphs of the hierarchy, keys are ids of hierarchy graphs, values are dictionaries containing the mapping of nodes from the rhs to the nodes of the typing graph given by the respective key of the value (note that a node from the rhs can be typed by a set of nodes of some graph, e.g. if we want to perform merging of some types, etc).

strictbool, optional

Rewriting is strict when propagation down is not allowed

Raises

HierarchyError

If the graph is not in the database

RewritingError

If the provided p and rhs typing are inconsistent

abstract set_graph_attrs(self, node_id, attrs)

Set attributes of a graph in the hierarchy.

Parameters

graph_idhashable

Id of the graph

abstract set_node_relation(self, left_graph, right_graph, left_node, right_node)

Set relation for a particular node.

abstract set_relation_attrs(self, left, right, attrs)

Set attributes of a relation in the hierarchy.

Parameters

lefthashable

Id of the left graph

righthashable

Id of the right graph

abstract set_typing_attrs(self, source, target, attrs)

Set attributes of a typing in the hierarchy.

Parameters

sourcehashable

Id of the source graph

targethashable

Id of the target graph

abstract shortest_path(self, source, target)

Shortest path from ‘source’ to ‘target’.

abstract successors(self, node_id)

Return the set of successors.

to_json(self, rename_nodes=None)

Return json representation of the hierarchy.

Parameters

rename_nodesdict, optional

Dictionary specifying mapping of node ids from the original graph to its JSON-representation

abstract typings(self, data=False)

Return a list of graph typing edges in the hierarchy.

unique_graph_id(self, prefix)

Generate a new graph id starting with a prefix.