NetworkX-based hierarchies

NetworkX-based in-memory graph hierarchy objects.

This module contains a data structure implementing graph hierarchies based on NetworkX graphs.

• NXHierarchy – class for in-memort graph hierarchies.

class regraph.backends.networkx.hierarchies.NXHierarchy(attrs=None)

Class for in-memory hierarchies.

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_relation(self, left, right, relation[, …])	Add relation to the hierarchy.
add_rule(self, rule_id, rule[, attrs])	Add rule to the hierarchy.
add_rule_typing(self, rule_id, graph_id, …)	Add typing of a rule.
add_typing(self, source, target[, mapping, …])	Add homomorphism to the hierarchy.
apply_rule(self, graph_id, rule_id, instance)	Apply rule from the 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(hierarchy)	Copy the hierarchy object.
copy_graph(self, graph_id, new_graph_id[, …])	Create a copy of a graph in a hierarchy.
find_rule_matching(self, graph_id, rule_id)	Find matching of a rule rule_id form the hierarchy.
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_node_attrs(self, node_id)	Get attributes of a node in the hierarchy.
get_relation(self, left, right)	Get a relation dict associated to the rel ‘left-right’.
get_relation_attrs(self, left, right)	Get attributes of a reltion in the hierarchy.
get_rule(self, rule_id)	Get a rule object associated to the node ‘graph_id’.
get_rule_typing(self, rule_id, graph_id)	Get typing dict of source by target (source is rule).
get_typing(self, source, target)	Get a typing dict associated to the edge ‘source->target’.
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.
is_graph(self, node_id)	Test if a hierarchy node is a graph.
is_rule(self, node_id)	Test if a hierarchy node is a rule.
is_rule_typing(self, s, t)	Test if a hierarchy edge is a rule typing.
is_typing(self, s, t)	Test if a hierarchy edge is a typing.
predecessors(self, node_id)	Return the set of predecessors.
rel_dict_factory	alias of builtins.dict
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.
relations(self[, data])	Return a list of relations.
remove_graph(self, graph_id[, reconnect])	Remove graph from the hierarchy.
remove_node(self, node_id[, reconnect])	Remove node from the hierarchy.
remove_relation(self, left, right)	Remove a relation from the hierarchy.
remove_rule(self, rule_id[, reconnect])	Remove graph from the hierarchy.
remove_typing(self, s, t)	Remove a typing from the hierarchy.
rule_typings(self[, data])	Return a list of rule typing edges in the hierarchy.
rules(self[, data])	Return a list of rules in the hierarchy.
set_graph_attrs(self, node_id, attrs)	Set attributes of a graph in the hierarchy.
set_node_relation(self, left_graph, …)	Set relation to 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])	Convert hierarchy to its json representation.
typings(self[, data])	Return a list of graph typing edges in the hierarchy.

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

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

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

add_rule(self, rule_id, rule, attrs=None)

Add rule to the hierarchy.

Parameters

rule_idhashable

Id of a new node in the hierarchy

ruleregraph.rules.Rule

Rule object corresponding to the new node of the hierarchy

attrsdict

Dictionary containing attributes of the new node

Raises

HierarchyError

If the rule object is defined for directed/undirected graphs while the hierarchy’s parameter directed is False/True (the hierarchy accommodates undirected/directed graphs) or if node with provided id already exists in the hierarchy

add_rule_typing(self, rule_id, graph_id, lhs_mapping, rhs_mapping=None, lhs_total=False, rhs_total=False, attrs=None)

Add typing of a rule.

source

Id of a rule node to type

target

Id of a target graph node of typing

lhs_mappingdict

Dictionary representing a mapping of nodes from the left-hand side of the rule to target’s nodes

rhs_mappingdict

Dictionary representing a mapping of nodes from the right-hand side of the rule to target’s nodes

lhs_totalbool

True if left-hand side typing is total, False otherwise

rhs_totalbool

True if right-hand side typing is total, False otherwise

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

• a source node is not a rule

• a target node is not a graph

• addition of an edge produces paths that do not commute with

some already existing paths

InvalidHomomorphism

If a homomorphisms from the left(right)-hand side to a graph at the target given by lhs(rhs)_mapping is not a valid homomorphism.

add_typing(self, source, target, mapping=None, 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, optional

Dictionary containing attributes of the new typing edge. Empty by default

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.

apply_rule(self, graph_id, rule_id, instance)

Apply rule from the hierarchy.

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

classmethod copy(hierarchy)

Copy the hierarchy object.

copy_graph(self, graph_id, new_graph_id, attach_graphs=None)

Create a copy of a graph in a hierarchy.

find_rule_matching(self, graph_id, rule_id)

Find matching of a rule rule_id form the hierarchy.

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.

graph_idhashable

Id of the graph

get_node_attrs(self, node_id)

Get attributes of a node in the hierarchy.

node_idhashable

Id of the node

get_relation(self, left, right)

Get a relation dict associated to the rel ‘left-right’.

get_relation_attrs(self, left, right)

Get attributes of a reltion in the hierarchy.

lefthashable

Id of the left graph

righthashable

Id of the right graph

get_rule(self, rule_id)

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

get_rule_typing(self, rule_id, graph_id)

Get typing dict of source by target (source is rule).

get_typing(self, source, target)

Get a typing dict associated to the edge ‘source->target’.

get_typing_attrs(self, source, target)

Get attributes of a typing in the hierarchy.

sourcehashable

Id of the source graph

targethashable

Id of the target graph

graphs(self, data=False)

Return a list of graphs in the hierarchy.

is_graph(self, node_id)

Test if a hierarchy node is a graph.

is_rule(self, node_id)

Test if a hierarchy node is a rule.

is_rule_typing(self, s, t)

Test if a hierarchy edge is a rule typing.

is_typing(self, s, t)

Test if a hierarchy edge is a typing.

predecessors(self, node_id)

Return the set of predecessors.

rel_dict_factory

alias of builtins.dict

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

relabel_graph_node(self, graph_id, node, new_name)

Rename a node in a graph of the hierarchy.

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.

relations(self, data=False)

Return a list of relations.

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

graph_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

remove_node(self, node_id, reconnect=False)

Remove node from the hierarchy.

Removes a node 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 node to remove

reconnectbool

Reconnect the descendants of the removed node to its predecessors

Raises

HierarchyError

If node with node_id is not defined in the hierarchy

remove_relation(self, left, right)

Remove a relation from the hierarchy.

remove_rule(self, rule_id, reconnect=False)

Remove graph from the hierarchy.

Removes a rule 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

rule_id

Id of a rule 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

remove_typing(self, s, t)

Remove a typing from the hierarchy.

rule_typings(self, data=True)

Return a list of rule typing edges in the hierarchy.

rules(self, data=True)

Return a list of rules in the hierarchy.

set_graph_attrs(self, node_id, attrs)

Set attributes of a graph in the hierarchy.

graph_idhashable

Id of the graph

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

Set relation to a particular node.

set_relation_attrs(self, left, right, attrs)

Set attributes of a relation in the hierarchy.

lefthashable

Id of the left graph

righthashable

Id of the right graph

set_typing_attrs(self, source, target, attrs)

Set attributes of a typing in the hierarchy.

sourcehashable

Id of the source graph

targethashable

Id of the target graph

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

Convert hierarchy to its json representation.

typings(self, data=False)

Return a list of graph typing edges in the hierarchy.