Graph grammar

Node

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_unique_blueprint_array() → list[list[UniqueBlueprint]]

Returns a 2-d array of paths from root to each leaf

Raises:

Exception: Graph contain non-terminal elements

Returns:

list[list[WrapperTuple]]:

closest_node_to_root(list_ids: list[int]) → int

Find closest node to root from list_ids

Args:

list_ids (list[int]):

Returns:

int: id of closest Node

find_nodes(match: Node) → list[int]

Args:

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

Returns:

list[int]: Id of matched nodes

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

Returns:

list[int]:

get_root_based_paths()

Form the paths of node ids from root to each leaf

Raises:

Exception: the number of paths reached the limit

Returns:

list[list[int]]: list of paths, each path is a list of node ids

get_root_id() → int

Returns:

int: root id

get_sorted_root_based_paths()

Sort root based paths by lengh and same lengths lexicographically.

get_uniq_representation() → list[list[str]]

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

Returns:

list[list[str]]: dfs branches

graph_partition_dfs() → list[list[int]]

2D list

Row is branch of graph Collum is id node

Returns:

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

class rostok.graph_grammar.node.Node(label: str = '*', is_terminal: bool = False, block_blueprint: TransformBlueprint | RevolveJointBlueprint | PrimitiveBodyBlueprint | EnvironmentBodyBlueprint | None = None)

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

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.

class rostok.graph_grammar.node.UniqueBlueprint(id: int, block_blueprint: TransformBlueprint | RevolveJointBlueprint | PrimitiveBodyBlueprint | EnvironmentBodyBlueprint)

The return type is used to build the Robot. Id - from the generated graph

Graph-grammar explorer

rostok.graph_grammar.graphgrammar_explorer.create_graph_from_seq(seq: list[Rule]) → GraphGrammar

Applies the rules from the list in direct order

Parameters:

seq (list[Rule] list of rules)

Returns:

graph

Return type:

GraphGrammar

rostok.graph_grammar.graphgrammar_explorer.number_of_non_terminal_rules(seq: list[Rule]) → int

Calculate number of nonterminal rules by using is_terminal method from class graph_grammar.Rule

Parameters:

seq (list[Rule]) – list of rules

Returns:

number of nonterminal rules in list

Return type:

int

rostok.graph_grammar.graphgrammar_explorer.random_search_mechs_n_branch(rule_vocabul: RuleVocabulary, numbers_of_rules=[5, 6], category_size=10, desired_branch=1, max_tries=10000, is_terminal=True)

Randomly applies rules until it gets candidates with desired_branch or reaches max_tries

Args:

rule_vocabul (RuleVocabulary): numbers_of_rules (list, optional): Defaults to [5, 6]. category_size (int, optional): Defaults to 10. desired_branch (int, optional): Defaults to 1. max_tries (int, optional): Defaults to 10000. is_terminal (bool, optional): Defaults to True.

Returns:

list[GraphGrammar]:

rostok.graph_grammar.graphgrammar_explorer.ruleset_explorer(limit_non_terminal: int, rule_vocab: RuleVocabulary) → Tuple[set[GraphGrammar], int]

Recursive iterate over all posible graph in rule_vocab with limitation on non-terminal rules. Counts all non-uniq graphs

Parameters:

• limit_non_terminal (int)

• rule_vocab (RuleVocabulary)

Parameters:

• limit_non_terminal (int)

• rule_vocab (RuleVocabulary)

Returns:

first is set of uniq graphs last is counter of uniq graphs

Return type:

Tuple[set[GraphGrammar], int]

Node Vocabulary

class rostok.graph_grammar.node_vocabulary.NodeVocabulary

The class contains dictionary of nodes and methods to manipulate with it.

This is a class to manage a dictionary of nodes. The keys are labels of the nodes and the values are Node objects. User can create or add nodes to vocabulary, get individual nodes or list of nodes.

Attributes:

node_dict (List[Node]): dictionary of all nodes. terminal_node_dict (List[Node]): dictionary of only terminal nodes. non-terminal_node_dict (List[Node]): dictionary of only non-terminal nodes.

add_node(node: Node)

Add an already created node to the vocabulary.

Args:

node (Node): node to be added to vocabulary.

Raises:

Exception: Attempt to add a Node with a label that is already in dictionary!

check_node(label: str) → bool

Check if the label is in the vocabulary.

Args:

label(str): the label of the node that should be checked.

Returns:

bool: True is the label is in dictionary, False otherwise.

create_node(label: str, is_terminal: bool = False, block_blueprint: TransformBlueprint | RevolveJointBlueprint | PrimitiveBodyBlueprint | EnvironmentBodyBlueprint | None = None)

Create a node and add it to the vocabulary.

Args:

label (str): the label of the new node. is_terminal (bool, optional): defines if the new node is a terminal node. Default

is False.

block_blueprint (BlockBlueprint, optional): the object that contains physical properties

of the node. Default is None.

Raises:

Exception: Attempt to add a Node with a label that is already in dictionary!

get_list_of_nodes(nodes: list[str]) → list[Node]

Returns list of Node objects corresponding to list of labels.

Args:

nodes (list[str]): list of labels to construct a list of Node objects.

Returns:

list of Node objects corresponding to the list of passed labels.

get_node(label: str) → Node

Return a node corresponding to the label.

Args:

label(str): the label of the node that should be returned.

Returns:

A requested node as a Node class object.

Raises

Exception: Node with given label not found!

Rule Vocabulary

class rostok.graph_grammar.rule_vocabulary.RuleVocabulary(node_vocab: ~rostok.graph_grammar.node_vocabulary.NodeVocabulary = <rostok.graph_grammar.node_vocabulary.NodeVocabulary object>)

The class that contains the rules for building the rostok.graph_grammar.node.GraphGrammar object.

All rules for mechanism generation should be created with an instance of rostok.graph_grammar.rule_vocabulary.RuleVocabulary. This class provides utility methods for the rules.

Attributes:

node_vocab (NodeVocabulary): the node vocabulary that should contain all the nodes used in

the rules.

rule_dict (dict[str, Rule]): the dictionary of all rules with the rule names as keys.

nonterminal_rule_dict (dict[str, Rule]): the dictionary of only non-terminal rules. terminal_rule_dict (dict[str, Rule]): the dictionary of only terminal rules. rules_nonterminal_node_set (set(str)): the set of node labels that are used as the new nodes

in the non-terminal rules. These are nodes that can appear in the final graph.

rules_terminal_node_set (set(str)): the set of node labels that are used as the new nodes

in the terminal rules. These are nodes that can appear in the final graph.

terminal_dict (dict[str, list[str]]): the dictionary that contains the list of terminal

states for all non-terminal nodes.

check_rules()

Check set of rules itself, without any graph.

Check the rules for having at least one terminal rule for every node that appears in the end graph of a nonterminal rule.

create_rule(name: str, current_nodes: list[str], new_nodes: list[str], current_in_edges: int, current_out_edges: int, new_edges: list[tuple[int, int]] = [], current_links: list[tuple[int, int]] = [])

Create a rule and add it to the dictionary.

The method checks the created rule. There is no method to add already created rule to the vocabulary.

Args:

name (str): name of the new rule. current_nodes (list[str]): list of the nodes to be replaced. new_nodes (list[str]): list of the new nodes that to be inserted in the graph. current_in_edges (int):the node to link the in edges of the replaced node. current_out_edges (int): the node to link the out edges of the replaced node. new_edges (list[(int, int)]):the edges of the inserting subgraph.

Raises:

Exception: this name is already in the rule vocabulary! Exception: prohibited length of the current_nodes list, should be 1. Exception: the node vocabulary dose not include the replacing node or the new nodes. Exception: the edge contains node idx out of graph length or the edge is a loop. Exception: attempt to link in or out edges of the replaced node to the node idx out of

new subgraph length.

get_list_of_applicable_nonterminal_rules(grammar: GraphGrammar)

Return the list of non-terminal applicable rules for the current graph.

Args:

grammar (GraphGrammar): a rostok.graph_grammar.node.GraphGrammar object analyze.

Returns:

list of rule names for non-terminal rules that can be applied for the graph.

get_list_of_applicable_rules(grammar: GraphGrammar)

Return the total list of applicable rules for the current graph.

Args:

grammar (GraphGrammar): a rostok.graph_grammar.node.GraphGrammar object analyze.

Returns:

list of rule names for rules that can be applied for the graph.

get_list_of_applicable_terminal_rules(grammar: GraphGrammar)

Return the list of terminal applicable rules for the current graph.

Args:

grammar (GraphGrammar): a rostok.graph_grammar.node.GraphGrammar object analyze.

Returns:

list of rule names for terminal rules that can be applied for the graph.

get_rule(name: str) → Rule

Return a rule with the corresponding name.

Args:

name (str): the name of the rule to be returned.

make_graph_terminal(grammar: GraphGrammar)

Converts a graph into a graph with only terminal nodes.

For each non-terminal node the function apply a random rule that make it terminal.

Args:

grammar (GraphGrammar): rostok.graph_grammar.node.GraphGrammar object that should become terminal.

rule_vis(name: str)

Visualize the rule.

Args:

name (str): name of the rule to visualize

terminal_rules_for_node(node_name: str)

Return a list of the terminal rules for the node

Args:

node_name (str): a node label for which function returns the list of the terminal rules.

Returns:

The list of rule names for rules that can be applied to make a node terminal.

Random graph

rostok.graph_grammar.make_random_graph.make_random_graph(n_iter: int, rule_vocab: RuleVocabulary, use_nonterminal_only: bool = True)

Return random graph made with n_iter rules

At each step applied a random rule from a list of rules appliable for the current grahp. If use_nonterminal_only is True all applied rules are True, if it is Flase, first half of rules will be nonterminal and the second half will be random terminal and nonterminal.