Defined in forest.hpp.

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

Public Types
using	label_type = uint32_t
	Alias for the type of edge labels in a forest.

using	node_type = uint32_t
	Alias for the type of nodes in a forest.

Public Member Functions
	Forest (Forest &&)=default
	Default move constructor.

	Forest (Forest const &)=default
	Default copy constructor.

	Forest (size_t n=0)
	Constructs a forest with `n` nodes.

Forest &	add_nodes (size_t n)
	Add nodes to the Forest.

const_iterator_path	cbegin_path_to_root (node_type n) const
	Returns a const iterator pointing at the first letter of a word from a given node to its root.

const_iterator_path	cbegin_path_to_root_no_checks (node_type n) const noexcept
	Returns a const iterator pointing at the first letter of a word from a given node to its root.

const_iterator_path	cend_path_to_root (node_type n) const
	Returns a const iterator pointing one beyond the last letter in a word from a given node to its root.

const_iterator_path	cend_path_to_root_no_checks (node_type n) const noexcept
	Returns a const iterator pointing one beyond the last letter in a word from a given node to its root.

bool	empty () const noexcept
	Check if there are any nodes in the forest.

Forest &	init (size_t n=0)
	Reinitialize an existing Forest object.

label_type	label (node_type i) const
	Returns the label of the edge from a node to its parent.

label_type	label_no_checks (node_type i) const
	Returns the label of the edge from a node to its parent.

std::vector< label_type > const &	labels () const noexcept
	Returns a const reference to the vector of edge labels.

size_t	number_of_nodes () const noexcept
	Returns the number of nodes in the forest.

bool	operator!= (Forest const &that) const
	Compare Forest objects for inequality.

Forest &	operator= (Forest &&)=default
	Default move assignment constructor.

Forest &	operator= (Forest const &)=default
	Default copy assignment constructor.

bool	operator== (Forest const &that) const
	Compare Forest objects for equality.

node_type	parent (node_type i) const
	Returns the parent of a node.

node_type	parent_no_checks (node_type i) const
	Returns the parent of a node.

std::vector< node_type > const &	parents () const noexcept
	Returns a const reference to the vector of parents.

template<typename Iterator>
Iterator	path_from_root_no_checks (Iterator d_first, node_type i) const
	Store the labels of the edges on the path from a root node to a given node.

template<typename Iterator>
Iterator	path_to_root_no_checks (Iterator d_first, node_type i) const
	Store the labels of the edges on the path to a root node from a given node.

Forest &	set_parent_and_label (node_type node, node_type parent, label_type gen)
	Set the parent and edge label for a node.

Forest &	set_parent_and_label_no_checks (node_type node, node_type parent, label_type gen)
	Set the parent and edge label for a node.

void	throw_if_node_out_of_bounds (node_type v) const
	Throw an exception if a node is out of bound.

Related Symbols
(Note that these are not member symbols.)
std::string	to_human_readable_repr (Forest const &f)
	Return a human readable representation of a Forest object.

Constructor & Destructor Documentation

◆ Forest()

Forest ( size_t n = 0 )

inlineexplicit

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

Parameters

n	the number of nodes, defaults to `0`.

Member Function Documentation

◆ add_nodes()

Forest & add_nodes ( size_t n )

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

Parameters

n	the number of nodes to add.

Exceptions: This function guarantees not to throw a LibsemigroupsException. If an exception is thrown, this is guaranteed not to be modified (strong exception guarantee).

Complexity: At most linear in number_of_nodes() + n.

Iterator validity: This function modifies the object defined by this, any iterators, pointers or references pointing into this may be invalidated by a call to this function.

◆ cbegin_path_to_root()

const_iterator_path cbegin_path_to_root ( node_type n ) const

inlinenodiscard

This function returns a const iterator point at the first letter of the word from the node n to the root of the subtree of the Forest object containing n. The letters in this word correspond to labels of edges in the Forest, and not nodes.

Parameters

n the node.

Returns: A const iterator.

Exceptions

LibsemigroupsException if n is greater than or equal to number_of_nodes.

◆ cbegin_path_to_root_no_checks()

const_iterator_path cbegin_path_to_root_no_checks ( node_type n ) const

inlinenodiscardnoexcept

This function returns a const iterator point at the first letter of the word from the node n to the root of the subtree of the Forest object containing n. The letters in this word correspond to labels of edges in the Forest, and not nodes.

Parameters

n the node.

Returns: A const iterator.

Exceptions: This function is noexcept and is guaranteed never to throw.

Warning: No checks are performed on the arguments of this function. In particular, it is not checked whether or not n is less than number_of_nodes.

◆ cend_path_to_root()

const_iterator_path cend_path_to_root ( node_type n ) const

inlinenodiscard

This function returns a const iterator point at one beyond the last letter of the word from the node n to the root of the subtree of the Forest object containing n. The letters in this word correspond to labels of edges in the Forest, and not nodes.

Parameters

n the node.

Returns: A const iterator.

Exceptions

LibsemigroupsException if n is greater than or equal to number_of_nodes.

◆ cend_path_to_root_no_checks()

const_iterator_path cend_path_to_root_no_checks ( node_type n ) const

inlinenodiscardnoexcept

This function returns a const iterator point at one beyond the last letter of the word from the node n to the root of the subtree of the Forest object containing n. The letters in this word correspond to labels of edges in the Forest, and not nodes.

Parameters

n the node.

Returns: A const iterator.

Exceptions: This function is noexcept and is guaranteed never to throw.

Warning: No checks are performed on the arguments of this function. In particular, it is not checked whether or not n is less than number_of_nodes.

◆ empty()

bool empty ( ) const

inlinenodiscardnoexcept

This function returns true if there are 0 nodes in the forest, and false otherwise.

Returns: A value of type bool.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant

◆ init()

Forest & init ( size_t n = 0 )

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	the number of nodes, defaults to `0`.

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ label()

label_type label ( node_type i ) const

inlinenodiscard

This function returns the label of the edge from the parent of i to the node i. The value UNDEFINED is returned if i has no parent, i.e. when i is a root node.

Parameters

i	the node whose label is sought.

Returns: A label_type.

Exceptions

LibsemigroupsException if i exceeds number_of_nodes().

Complexity: Constant

◆ label_no_checks()

label_type label_no_checks ( node_type i ) const

inlinenodiscard

This function returns the label of the edge from the parent of i to the node i. The value UNDEFINED is returned if i has no parent, i.e. when i is a root node.

Parameters

i	the node whose label is sought.

Returns: A label_type.

Complexity: Constant

Warning: No checks are performed on the arguments of this function.

◆ labels()

std::vector< label_type > const & labels ( ) const

inlinenodiscardnoexcept

Returns a const reference to the vector of edge labels in the Forest. The value in position i of this vector 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: A std::vector<label_type>.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ number_of_nodes()

size_t number_of_nodes ( ) const

inlinenodiscardnoexcept

Returns the number of nodes in the forest.

Returns: A size_t.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant

◆ operator!=()

bool operator!= ( Forest const & that ) const

inlinenodiscard

This function returns the negation of operator==(that)

Parameters

that	the Forest for comparison.

Returns: whether or not the Forest objects are not equal.

◆ operator==()

bool operator== ( Forest const & that ) const

inlinenodiscard

This function returns true if and only if the parent and label of every node in this coincides with the parent and label in that.

Parameters

that	the Forest for comparison.

Returns: whether or not the Forest objects are equal.

◆ parent()

node_type parent ( node_type i ) const

inlinenodiscard

This function returns the parent of the node i in the forest. The value UNDEFINED is returned if i has no parent, i.e. when i is a root node.

Parameters

i	the node whose parent is sought.

Returns: A node_type.

Exceptions

LibsemigroupsException if i exceeds number_of_nodes().

Complexity: Constant

◆ parent_no_checks()

node_type parent_no_checks ( node_type i ) const

inlinenodiscard

This function returns the parent of the node i in the forest. The value UNDEFINED is returned if i has no parent, i.e. when i is a root node.

Parameters

i	the node whose parent is sought.

Returns: A node_type.

Complexity: Constant

Warning: No checks are performed on the arguments of this function.

◆ parents()

std::vector< node_type > const & parents ( ) const

inlinenodiscardnoexcept

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

Returns: A std::vector<node_type>.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ path_from_root_no_checks()

template<typename Iterator>

Iterator path_from_root_no_checks	(	Iterator	d_first,
		node_type	i ) const

This function writes labels of the edges on the path from a root node to node i to the iterator d_first.

Template Parameters

Iterator The type of the parameter, and the return type.

Parameters

d_first	the output iterator.
i	the node.

Returns: An Iterator pointing one beyond the last letter inserted into d_first.

Warning: No checks are performed on the arguments of this function.

◆ path_to_root_no_checks()

template<typename Iterator>

Iterator path_to_root_no_checks	(	Iterator	d_first,
		node_type	i ) const

This function writes labels of the edges on the path to a root node from node i to the iterator d_first.

Template Parameters

Iterator The type of the parameter, and the return type.

Parameters

d_first	the output iterator.
i	the node.

Returns: An Iterator pointing one beyond the last letter inserted into d_first.

Warning: No checks are performed on the arguments of this function.

◆ set_parent_and_label()

Forest & set_parent_and_label	(	node_type	node,
		node_type	parent,
		label_type	gen )

inline

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

Parameters

node	the node whose parent and label to set.
parent	the parent node.
gen	the label of the edge from `parent` to `node`.

Returns: A reference to *this.

Exceptions

LibsemigroupsException if node or parent exceeds number_of_nodes().

Complexity: Constant

Note: The value of gen can be arbitrary, and so this argument is never checked.

◆ set_parent_and_label_no_checks()

Forest & set_parent_and_label_no_checks	(	node_type	node,
		node_type	parent,
		label_type	gen )

inline

This function defines the parent and the label of the edge from that parent to the node node to be parent and gen respectively.

Parameters

node	the node whose parent and label to set.
parent	the parent node.
gen	the label of the edge from `parent` to `node`.

Exceptions

LibsemigroupsException if node or parent exceeds number_of_nodes().

Complexity: Constant

Note: The value of gen can be arbitrary, and so this argument is never checked.

Warning: No checks are performed on the arguments of this function. In particular, if node or parent is greater than or equal to number_of_nodes, then bad things may happen.

◆ throw_if_node_out_of_bounds()

void throw_if_node_out_of_bounds ( node_type v ) const

This function throws an exception if the node v is out of points.

Parameters

v the node.

Friends And Related Symbol Documentation

◆ to_human_readable_repr()

std::string to_human_readable_repr ( Forest const & f )

Return a human readable representation of a Forest object.

Parameters

f	the Forest.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

The documentation for this class was generated from the following file:

/Users/jdm3/libsemigroups/include/libsemigroups/forest.hpp

Public Types

Public Member Functions

Related Symbols

Constructor & Destructor Documentation

◆ Forest()

Member Function Documentation

◆ add_nodes()

◆ cbegin_path_to_root()

◆ cbegin_path_to_root_no_checks()

◆ cend_path_to_root()

◆ cend_path_to_root_no_checks()

◆ empty()

◆ init()

◆ label()

◆ label_no_checks()

◆ labels()

◆ number_of_nodes()

◆ operator!=()

◆ operator==()

◆ parent()

◆ parent_no_checks()

◆ parents()

◆ path_from_root_no_checks()

◆ path_to_root_no_checks()

◆ set_parent_and_label()

◆ set_parent_and_label_no_checks()

◆ throw_if_node_out_of_bounds()

Friends And Related Symbol Documentation

◆ to_human_readable_repr()