The Forest class

This class represents the collection of spanning trees of the strongly connected components of a word graph.

Contents

`Forest`	This class represents the collection of spanning trees of the strongly connected components of a word graph.
`Forest.add_nodes`(…)	Add nodes to the `Forest`.
`Forest.copy`(…)	Copy a `Forest` object.
`Forest.empty`(…)	Check if there are any nodes in the forest.
`Forest.init`(…)	Reinitialize an existing `Forest` object.
`Forest.label`(…)	Returns the label of the edge from a node to its parent.
`Forest.labels`(…)	Returns a copy of the list of edge labels in the `Forest`.
`Forest.number_of_nodes`(…)	Returns the number of nodes in the forest.
`Forest.parent`(…)	Returns the parent of a node.
`Forest.parents`(…)	Returns a list of parents in the `Forest`.
`Forest.path_to_root`(…)	Returns a list containing the labels of the edges on the path from a root node to i.
`Forest.set_parent_and_label`(…)	Set the parent and edge label for a node.

Full API

class Forest

__init__(*args, **kwargs)

Overloaded function.

__init__(self: Forest, n: int = 0) → None

Constructs a forest with n nodes.

Constructs a forest with n nodes, that is initialised so that the Forest.parent and Forest.label of every node is UNDEFINED.

Parameters:: n (int) – the number of nodes, defaults to 0.

__init__(self: Forest, parents: list[int | Undefined], labels: list[int | Undefined]) → None

Construct a Forest from list of parents and labels.

Parameters:

parents (list[int | Undefined]) – the list of parents of nodes.
labels (list[int | Undefined]) – the list of edge labels.

Raises:

LibsemigroupsError – if parent and labels have different sizes;
LibsemigroupsError – parent and labels do not have the value UNDEFINED in the same positions (these values indicate where the roots of the trees in the forest are located and so must coincide).
LibsemigroupsError – set_parent_and_label throws for parent[i] and edge_labels[i] for any value of i.

add_nodes(self: Forest, n: int) → None

Add nodes to the Forest.

This function adds n nodes to the forest, but no edges.

Parameters:: n (int) – the number of nodes to add.
Complexity:: At most linear in number_of_nodes() + n.

copy(self: Forest) → Forest

Copy a Forest object.

Returns:: A copy.
Return type:: Forest

empty(self: Forest) → bool

Check if there are any nodes in the forest. This function returns True if there are 0 nodes in the forest, and False otherwise.

Returns:: Whether or not the forest is empty.
Return type:: bool
Complexity:: Constant.

init(self: Forest, n: int) → Forest

Reinitialize an existing Forest object.

This function reinitializes an existing Forest object so that it is in the same state as if it had just be constructed as Forest(n).

Parameters:: n (int) – the number of nodes, defaults to 0.
Returns:: self.
Return type:: Forest

label(self: Forest, i: int) → int | Undefined

Returns the label of the edge from a node to its parent.

Parameters:: i (int) – the node whose label is sought.
Returns:: The label of the edge from the parent of i to i.
Return type:: int | Undefined
Raises:: LibsemigroupsError – if i exceeds number_of_nodes().
Complexity:: Constant.

labels(self: Forest) → list[int | Undefined]

Returns a copy of the list of edge labels in the Forest. The value in position i of this list is the label of the edge from the parent of node i to i. If the parent equals UNDEFINED, then node i is a root node.

Returns:: The edge labels of the forest.
Return type:: list[int | Undefined]
Complexity:: Constant.

number_of_nodes(self: Forest) → int

Returns the number of nodes in the forest. Returns the number of nodes in the forest.

Returns:: The number of nodes in the forest.
Return type:: int
Complexity:: Constant.

parent(self: Forest, i: int) → int | Undefined

Returns the parent of a node.

Parameters:: i (int) – the node whose parent is sought.
Returns:: The parent of i.
Return type:: int | Undefined
Raises:: LibsemigroupsError – if i exceeds number_of_nodes().
Complexity:: Constant

parents(self: Forest) → list[int | Undefined]

Returns a list of parents in the Forest. The value in position i of this list is the parent of node i. If the parent equals UNDEFINED, then node i is a root node.

Returns:: The parents of the nodes in the forest.
Return type:: list[int | Undefined]
Complexity:: Constant.

path_to_root(self: Forest, i: int) → list[int]

Returns a list containing the labels of the edges on the path from a root node to i.

Parameters:: i (int) – the node.
Returns:: The word labelling the path from the root to i.
Return type:: list[int]
Raises:: LibsemigroupsError – if i is greater than or equal to number_of_nodes.

set_parent_and_label(self: Forest, node: int, parent: int, gen: int) → Forest

Set the parent and edge label for a node. This function sets the parent of node to be parent, and the associated edge-label to be gen.

Parameters:

node (int) – the node whose parent and label to set.
parent (int) – the parent node
gen (int) – the label of the edge from parent to node.

Returns:

self

Return type:

Forest

Raises:

LibsemigroupsError – if node or parent exceeds number_of_nodes().

Complexity:

Constant.