libsemigroups::forest Namespace Reference

This page contains the documentation of some helper functions for the Forest class.

Classes
class	PathsFromRoots
	Range for iterating through paths in a Forest. More...
class	PathsToRoots
	Range for iterating through paths in a Forest. More...

Functions
size_t	depth (Forest const &f, Forest::node_type n)
	Returns the depth of a node in the forest, i.e. the distance, in terms of the number of edges, from a root.
size_t	depth_no_checks (Forest const &f, Forest::node_type n)
	Returns the depth of a node in the forest, n.e. the distance, in terms of the number of edges, from a root.
Dot	dot (Forest const &f)
	Returns a Dot object representing a Forest.
Dot	dot (Forest const &f, std::vector< std::string > const &labels)
	Returns a Dot object representing a Forest.
bool	is_forest (Forest const &f)
	Check whether a Forest object is well-defined.
bool	is_root (Forest const &f, Forest::node_type n)
	Check if a node is the root of any tree in the Forest.
bool	is_root_no_checks (Forest const &f, Forest::node_type n)
	Check if a node is the root of any tree in the Forest.
Forest::label_type	max_label (Forest const &f)
	Returns the maximum label of any edge in a Forest.
word_type	path_from_root (Forest const &f, Forest::node_type n)
	Returns a word containing the labels of the edges on the path from a root node to n.
void	path_from_root (Forest const &f, word_type &w, Forest::node_type n)
	Modifies w to contain the labels of the edges on the path from a root node to n.
word_type	path_from_root_no_checks (Forest const &f, Forest::node_type n)
	Returns a word containing the labels of the edges on the path from a root node to n.
void	path_from_root_no_checks (Forest const &f, word_type &w, Forest::node_type n)
	Modifies w to contain the labels of the edges on the path from a root node to n.
word_type	path_to_root (Forest const &f, Forest::node_type n)
	Returns a word containing the labels of the edges on the path to a root node from n.
void	path_to_root (Forest const &f, word_type &w, Forest::node_type n)
	Modifies w to contain the labels of the edges on the path to a root node from n.
word_type	path_to_root_no_checks (Forest const &f, Forest::node_type n)
	Returns a word containing the labels of the edges on the path to a root node from n.
void	path_to_root_no_checks (Forest const &f, word_type &w, Forest::node_type n)
	Modifies w to contain the labels of the edges on the path to a root node from n.

Function Documentation

depth()

size_t depth ( Forest const & f, Forest::node_type n )

inlinenodiscard

This function returns the length of the word returned by path_to_root_no_checks and path_from_root_no_checks.

Parameters

f	the Forest.
n	the node.

Returns

The depth of n.

Exceptions

LibsemigroupsException

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

depth_no_checks()

size_t depth_no_checks ( Forest const & f, Forest::node_type n )

nodiscard

This function returns the length of the word returned by path_to_root_no_checks and path_from_root_no_checks.

Parameters

f	the Forest.
n	the node.

Returns

The depth of n.

Warning

No checks are performed on the arguments of this function.

dot() [1/2]

Dot dot ( Forest const & f )

nodiscard

This function returns a Dot object representing the Forest f.

Parameters

f	the Forest.

Returns

A Dot object.

dot() [2/2]

Dot dot	(	Forest const &	f,
		std::vector< std::string > const &	labels )

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	the Forest.
labels	substitute for each edge label.

Returns

A Dot object.

Exceptions

LibsemigroupsException

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

is_forest()

bool is_forest ( Forest const & f )

nodiscard

This function returns true if the Forest f is well-defined, meaning that it contains no cycles. It is not possible to create a Forest with cycles using set_parent_and_label (which will throw if such a cycle is introduced), but it is possible using Forest with cycles using set_parent_and_label_no_checks.

Parameters

f	the Forest

Returns

Whether or not f is valid.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

See also

Forest::throw_if_not_acyclic

is_root()

bool is_root ( Forest const & f, Forest::node_type n )

inlinenodiscard

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

Parameters

f	the Forest.
n	the node.

Returns

Whether or not n is a root of f.

Exceptions

LibsemigroupsException

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

is_root_no_checks()

bool is_root_no_checks ( Forest const & f, Forest::node_type n )

inlinenodiscard

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

Parameters

f	the Forest.
n	the node.

Returns

Whether or not n is a root of f.

Warning

No checks are performed on the arguments of this function. In particular it is not checked whether or not n is a node of f.

max_label()

Forest::label_type max_label ( Forest const & f )

nodiscard

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

Parameters

f	the Forest.

Returns

The maximum label or UNDEFINED.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

path_from_root() [1/2]

word_type path_from_root ( Forest const & f, Forest::node_type n )

nodiscard

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

Parameters

f	the forest.
n	the node.

Returns

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

Exceptions

LibsemigroupsException

if n is greater than or equal to number_of_nodes.

See also

PathsFromRoots

path_from_root() [2/2]

void path_from_root	(	Forest const &	f,
		word_type &	w,
		Forest::node_type	n )

This function modifies its first argument w in-place to contain the labels of the edges on the path from a root node to the node n.

Parameters

f	the forest.
w	value to contain the result.
n	the node.

Exceptions

LibsemigroupsException

if n is greater than or equal to number_of_nodes.

See also

PathsFromRoots

path_from_root_no_checks() [1/2]

word_type path_from_root_no_checks ( Forest const & f, Forest::node_type n )

nodiscard

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

Parameters

f	the forest.
n	the node.

Returns

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

Warning

No checks are performed on the arguments of this function.

See also

PathsFromRoots

path_from_root_no_checks() [2/2]

void path_from_root_no_checks	(	Forest const &	f,
		word_type &	w,
		Forest::node_type	n )

This function modifies its first argument w in-place to contain the labels of the edges on the path from a root node to the node n.

Parameters

f	the forest.
w	value to contain the result.
n	the node.

Warning

No checks are performed on the arguments of this function.

See also

PathsFromRoots

path_to_root() [1/2]

word_type path_to_root ( Forest const & f, Forest::node_type n )

nodiscard

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

Parameters

f	the forest.
n	the node.

Returns

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

Exceptions

LibsemigroupsException

if n is greater than or equal to number_of_nodes.

See also

PathsToRoots

path_to_root() [2/2]

void path_to_root	(	Forest const &	f,
		word_type &	w,
		Forest::node_type	n )

This function modifies its first argument w in-place to contain the labels of the edges on the path to a root node from node n.

Parameters

f	the forest.
w	value to contain the result.
n	the node.

Exceptions

LibsemigroupsException

if n is greater than or equal to number_of_nodes.

See also

PathsToRoots

path_to_root_no_checks() [1/2]

word_type path_to_root_no_checks ( Forest const & f, Forest::node_type n )

nodiscard

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

Parameters

f	the forest.
n	the node.

Returns

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

Warning

No checks are performed on the arguments of this function.

See also

PathsToRoots

path_to_root_no_checks() [2/2]

void path_to_root_no_checks	(	Forest const &	f,
		word_type &	w,
		Forest::node_type	n )

This function modifies its first argument w in-place to contain the labels of the edges on the path to a root node from node n.

Parameters

f	the forest.
w	value to contain the result.
n	the node.

Warning

No checks are performed on the arguments of this function.