Graph grammar

Node and rule classes

class Node

class rostok.graph_grammar.node.Node(label: str = '*', is_terminal: bool = False, block_wrapper: BlockWrapper | None = None)

Contains information about the label and BlockWrapper, which is the physical representation of the node in the simulator

class Rule

class rostok.graph_grammar.node.Rule

The class contains a graph object for substitution into the generated graph and the target node which will be replaced by Rule.graph_insert. The feature of the rule’s terminality is automatically determined. Id’s mean V from graph theory, do not intersect with V from generated graph.

Graph grammar class

class GraphGrammar

class rostok.graph_grammar.node.GraphGrammar(**attr)

A class for using generative rules (similar to L grammar) and manipulating the construction graph. The mechanism for assignment a unique Id, each added node using GraphGrammar.rule_apply() will increase the counter. Supports methods from networkx.DiGraph ancestor class

build_terminal_wrapper_array() list[list[rostok.graph_grammar.node.WrapperTuple]]

Returns a 2-d array of the shape dfs_partition

Raises:

Exception – Graph contain non-terminal elements

Return type:

list[list[WrapperTuple]]

closest_node_to_root(list_ids: list[int]) int

Find closest node to root from list_ids

Parameters:

list_ids (list[int]) –

Returns:

id of closest Node

Return type:

int

find_nodes(match: Node) list[int]
Parameters:

match (Node) – Node for find, matched by label

Returns:

Id of matched nodes

Return type:

list[int]

get_ids_in_dfs_order() list[int]

Iterate in deep first order over node ids One of the options to present the graph in a flat form

Return type:

list[int]

get_root_id() int
Returns:

root id

Return type:

int

get_uniq_representation() list[list[str]]

Returns dfs partition node labels. Where branches is sorted by lexicographic order

Returns:

dfs branches

Return type:

list[list[str]]

graph_partition_dfs() list[list[int]]
2D list

Row is branch of graph Collum is id node

Return type:

list[list[int]]

node_levels_bfs() list[list[int]]

Divide nodes into levels.

Return a list of lists of nodes where each inner list is a level in respect to the ‘root’, which is the node with no in edges. This function should be reviewed once we start to use graphs with cycles and not just trees