Forest helpers

This page contains the documentation for various helper classes and functions for manipulating Forest objects. All such classes and functions are in the submodule forest.

Contents

`PathsFromRoots`	Range object for iterating through paths in a `Forest`.
`PathsToRoots`	Range object for iterating through paths in a `Forest`.
`depth`(…)	Returns the depth of a node in the forest, i.e. the distance, in terms of the number of edges, from a root.
`dot`(…)	Overloaded function.
`is_root`(…)	Check if a node is the root of any tree in the `Forest`.
`max_label`(…)	Returns the maximum label of any edge in a `Forest`.
`path_from_root`(…)	Returns a word containing the labels of the edges on the path from a root node to n.
`path_to_root`(…)	Returns a list containing the labels of the edges on the path from node n to a root node.

Full API

This page contains the documentation for various helper classes and functions for manipulating Forest objects. All such classes and functions are contained in the submodule forest.

class forest.PathsFromRoots

Range object for iterating through paths in a Forest.

This class represents a range object that facilitates iterating through the paths from every node to the root of its subtree in a Forest object. These nodes are taken in numerical order, so the first value returned by get is the word to a root from node 0, after next is called, get returns the word to a root from node 1, and so on. The point of this class is to permit more efficient iteration over many paths in a Forest object than path_from_root (and its associated helper functions). path_from_root traverses the Forest from the given node to the root of its tree. If the path from nodes m and n to the root of their tree share a long common suffix, then this suffix will be traversed twice in two calls to path_from_root. PathsFromRoots avoids this by finding the least common ancestor of m and n, so that the suffix is not re-traversed. This works best when the nodes in the Forest are specified in a sensible order (such as via a depth-first or breadth-first traversal).

at_end(self: PathsFromRoots) → bool

Check if the range is exhausted.

This function returns True if there are no more paths in the range, and False otherwise.

Returns:: Whether or not the range is exhausted.
Return type:: bool

copy(self: PathsFromRoots) → PathsFromRoots

Copy a PathsFromRoots object.

Returns:: A copy.
Return type:: PathsFromRoots

count(self: PathsFromRoots) → int

Get the size of the range.

This function returns the number of paths in the range.

Returns:: the number of paths in the range.
Return type:: int

forest(self: PathsFromRoots) → Forest

Returns the underlying Forest object.

This function returns the Forest object used to constructor or initialise self.

Returns:: A Forest object.
Return type:: Forest

get(self: PathsFromRoots) → list[int]

Returns a reference to the current path.

This function returns a const reference to the current path from the root of the tree containing target to target.

Returns:: The current path.
Return type:: list[int]

init(self: PathsFromRoots, f: Forest) → PathsFromRoots

Re-initialize from a Forest.

This function re-initializes self so that its underlying Forest object is f. This puts self back into the same state it would have been in if it had been newly constructed from f.

Parameters:: f (Forest) – the Forest.
Returns:: self
Return type:: PathsFromRoots

next(self: PathsFromRoots) → None

Advance to the next path in the range.

This function advances to the current path in the range. If at_end returns True, then this function does nothing.

Returns:: None
Return type:: None

skip_n(self: PathsFromRoots, n: int) → PathsFromRoots

Skip a number of paths in the range.

This function skips n paths in the range. If n is 1, then this is the same as calling next. If n is 0, then this function does nothing.

Parameters:: n (int) – the number of paths to skip.
Returns:: self.
Return type:: PathsFromRoots

target(self: PathsFromRoots) → int

Get the current target of the path.

This function returns the current target of the path returned by get.

Returns:: The target of the current path.
Return type:: int

class forest.PathsToRoots

Range object for iterating through paths in a Forest.

This class represents a range object that facilitates iterating through the paths from every node to the root of its subtree in a Forest object. These nodes are taken in numerical order, so the first value returned by get is the word to a root from node 0, after next is called, get returns the word to a root from node 1, and so on. The point of this class is to permit more efficient iteration over many paths in a Forest object than path_to_root (and its associated helper functions). path_to_root traverses the Forest from the given node to the root of its tree. If the path from nodes m and n to the root of their tree share a long common suffix, then this suffix will be traversed twice in two calls to path_to_root. PathsToRoots avoids this by finding the least common ancestor of m and n, so that the suffix is not re-traversed. This works best when the nodes in the Forest are specified in a sensible order (such as via a depth-first or breadth-first traversal).

at_end(self: PathsToRoots) → bool

Check if the range is exhausted.

This function returns True if there are no more paths in the range, and False otherwise.

Returns:: Whether or not the range is exhausted.
Return type:: bool

copy(self: PathsToRoots) → PathsToRoots

Copy a PathsToRoots object.

Returns:: A copy.
Return type:: PathsToRoots

count(self: PathsToRoots) → int

Get the size of the range.

This function returns the number of paths in the range.

Returns:: the number of paths in the range.
Return type:: int

forest(self: PathsToRoots) → Forest

Returns the underlying Forest object.

This function returns the Forest object used to constructor or initialise self.

Returns:: A Forest object.
Return type:: Forest

get(self: PathsToRoots) → list[int]

Returns a reference to the current path.

This function returns a const reference to the current path from the root of the tree containing target to target.

Returns:: The current path.
Return type:: list[int]

init(self: PathsToRoots, f: Forest) → PathsToRoots

Re-initialize from a Forest.

This function re-initializes self so that its underlying Forest object is f. This puts self back into the same state it would have been in if it had been newly constructed from f.

Parameters:: f (Forest) – the Forest.
Returns:: self
Return type:: PathsToRoots

next(self: PathsToRoots) → None

Advance to the next path in the range.

This function advances to the current path in the range. If at_end returns True, then this function does nothing.

Returns:: None
Return type:: None

skip_n(self: PathsToRoots, n: int) → PathsToRoots

Skip a number of paths in the range.

This function skips n paths in the range. If n is 1, then this is the same as calling next. If n is 0, then this function does nothing.

Parameters:: n (int) – the number of paths to skip.
Returns:: self.
Return type:: PathsToRoots

target(self: PathsToRoots) → int

Get the current target of the path.

This function returns the current target of the path returned by get.

Returns:: The target of the current path.
Return type:: int

forest.depth(f: Forest, n: int) → int

Returns the depth of a node in the forest, i.e. the distance, in terms of the number of edges, from a root.

This function returns the length of the word returned by path_to_root and path_from_root.

Parameters:

f (Forest) – the Forest.
n (int) – the node.

Returns:

The depth of n.

Return type:

int

Raises:

LibsemigroupsError – if n is out of bounds (i.e. it is greater than or equal to Forest.number_of_nodes).

forest.dot(f: Forest, labels: list[str]) → Dot

Overloaded function.

forest.dot(f: Forest) → Dot

Returns a Dot object representing a Forest.

This function returns a Dot object representing the Forest f.

Parameters:: f (Forest) – the Forest.
Returns:: A Dot object.
Return type:: Dot

forest.dot(f: Forest, labels: list[str]) → Dot

Returns a Dot object representing a Forest.

This function returns a Dot object representing the Forest f. If labels is not empty, then each node is labelled with the path from that node to the root of its tree with each letter replaced by the string in the corresponding position of labels. If labels is empty, then the nodes are not labelled by their paths.

Parameters:

f (Forest) – the Forest.
labels (list[str]) – substitute for each edge label.

Returns:

A Dot object.

Return type:

Dot

Raises:

LibsemigroupsError – if the size of labels is not the same as the max_label plus one.

forest.is_root(f: Forest, n: int) → bool

Check if a node is the root of any tree in the Forest.

This function returns True if the node n in the Forest f is a root node, and False if it is not.

Parameters:

f (Forest) – the Forest.
n (int) – the node.

Returns:

Whether or not n is a root of f.

Return type:

bool

Raises:

LibsemigroupsError – if n is out of bounds (i.e. it is greater than or equal to Forest.number_of_nodes).

forest.max_label(f: Forest) → int | Undefined

Returns the maximum label of any edge in a Forest.

This function returns the maximum label of any edge in the Forest f or UNDEFINED if there are no edges.

Parameters:: f (Forest) – the Forest.
Returns:: The maximum label or UNDEFINED.
Return type:: int | Undefined

forest.path_from_root(f: Forest, n: int) → list[int]

Returns a word containing the labels of the edges on the path from a root node to n.

This function returns a word containing the labels of the edges on the path from a root node to the node n.

Parameters:

f (Forest) – the forest.
n (int) – the node.

Returns:

The word labelling the path from a root node to n.

Return type:

list[int]