lal::generate::all_ulab_free_trees Class Reference

Exhaustive enumeration of unlabelled free trees. More...

#include <all_ulab_free_trees.hpp>

Inheritance diagram for lal::generate::all_ulab_free_trees:

Public Types
typedef std::conditional_t< std::is_base_of_v< graphs::free_tree, graphs::free_tree >, graphs::free_tree, graphs::rooted_tree >	tree_type_t
	Shorthand for the type of tree this class returns.

Public Member Functions
	all_ulab_free_trees (uint32_t n) noexcept
	Constructor with number of nodes.
	all_ulab_free_trees (const all_ulab_free_trees &Gen)=default
	Copy constructor.
	all_ulab_free_trees (all_ulab_free_trees &&Gen)=default
	Move constructor.
	~all_ulab_free_trees () noexcept=default
	Default destructor.
bool	end () const noexcept
	Returns true if the end of the iteration was reached.
void	next () noexcept
	Generates next tree.
void	reset () noexcept
	Sets the generator to its initial state.
graphs::free_tree	yield_tree () noexcept
	Yields a tree, advancing the generator if necessary.
tree_type_t	get_tree () noexcept
	Retrieve the generated tree.
void	activate_all_postprocessing_actions () noexcept
	Activates all postprocessing actions.
void	deactivate_all_postprocessing_actions () noexcept
	Deactivates all postprocessing actions.
void	set_normalise_tree (bool v) noexcept
	Should trees be normalised?
void	set_calculate_size_subtrees (bool v) noexcept
	Should the size of the subtrees be calculated?
void	set_calculate_tree_type (bool v) noexcept
	Should the tree be classified into types?

Protected Member Functions
graphs::free_tree	__get_tree () noexcept
	Constructs the current tree.
void	__reset () noexcept
	Sets the generator to its initial state.

Protected Attributes
const uint32_t	m_n
	Number of vertices.
bool	m_normalise_tree
	Normalise the generated tree.
bool	m_calculate_size_subtrees
	Calculate the size of the subtrees of the generated rooted tree.
bool	m_calculate_tree_type
	Calculate the type of tree of the generated tree.

Private Attributes
internal::data_array< uint32_t >	m_L
	Canonical level sequence of the tree.
internal::data_array< uint32_t >	m_W
	\(W_i\) is the subscript of the level number in \(L\) corresponding to the parent of the node corresponding to \(l_i\).
uint32_t	m_p
	Largest integer such that \(l_p \neq 2\).
uint32_t	m_q
	Largest integer such that \(q < p, \; l_q = l_p - 1\).
uint32_t	m_h1
	Maximum level number in the first principal subsequence.
uint32_t	m_h2
	Maximum level number in the second principal subsequence.
uint32_t	m_c
	An index to the first element of \(L_2\).
uint32_t	m_r
	Exactly \(m - 1\).
bool	m_is_last = false
	Was the last tree generated?
bool	m_first_it = true
	First time calling next().
bool	m_reached_end = false
	Has the end of the generation been reached?

Detailed Description

Exhaustive enumeration of unlabelled free trees.

Generates all the unlabelled free trees of a given number of nodes. The algorithm implemented can be found in [35]. The definition of the public and private members of this class follow the notation in this work.

In order to use this class, users must provide the size \(n\) of the tree (number of nodes) in the constructor. Trees are generated internally, i.e., trees are encoded in the internal state of the generator. Said state is updated using method next(), which updates it to encode the next tree in the generation. In order to retrieve the tree, use method get_tree(). Upon initialisation, the generator encodes the first tree, which has to be retrieved using method get_tree().

All the unlabelled free trees will have been generated when method end() returns true. At this point, method get_tree() will always construct the last tree in the enumeration, whichever tree it is. In order to restart the generation of these trees, call method reset(). It is allowed to call this method at any time.

A possible usage of this class is the following:

all_ulab_free_trees Gen(n);
while (not Gen.end()) {
    const auto t = Gen.get_tree();
    // ...
    Gen.next();
}

Alternatively, this class can be used in a for loop:

for (all_ulab_free_trees Gen(n); not Gen.end(); Gen.next()) {
    const auto t = Gen.get_tree();
    // ...
}

Equivalently,

all_ulab_free_trees Gen(n);
while (not Gen.end()) {
    const auto t = Gen.yield_tree();
    // ...
}

Constructor & Destructor Documentation

all_ulab_free_trees() [1/3]

lal::generate::all_ulab_free_trees::all_ulab_free_trees ( uint32_t n )

noexcept

Constructor with number of nodes.

Parameters

n	Number of nodes.

all_ulab_free_trees() [2/3]

lal::generate::all_ulab_free_trees::all_ulab_free_trees ( const all_ulab_free_trees & Gen )

default

Copy constructor.

Parameters

Gen	Exhaustive unlabelled free tree generator..

all_ulab_free_trees() [3/3]

lal::generate::all_ulab_free_trees::all_ulab_free_trees ( all_ulab_free_trees && Gen )

default

Move constructor.

Parameters

Gen	Exhaustive unlabelled free tree generator..

Member Function Documentation

__get_tree()

graphs::free_tree lal::generate::all_ulab_free_trees::__get_tree ( )

protectedvirtualnoexcept

Constructs the current tree.

Returns

The tree generated with method next().

Precondition

The generator must have been initialised.

Method next must have been called at least once.

Implements lal::generate::_tree_generator< graphs::free_tree >.

activate_all_postprocessing_actions()

void lal::generate::_tree_generator< graphs::free_tree, std::is_base_of_v<graphs::free_tree, graphs::free_tree>, >::activate_all_postprocessing_actions ( )

inlinenoexceptinherited

Activates all postprocessing actions.

The full list of postprocessing actions can be found in the documentation of this class.

deactivate_all_postprocessing_actions()

void lal::generate::_tree_generator< graphs::free_tree, std::is_base_of_v<graphs::free_tree, graphs::free_tree>, >::deactivate_all_postprocessing_actions ( )

inlinenoexceptinherited

Deactivates all postprocessing actions.

The full list of postprocessing actions can be found in the documentation of this class.

get_tree()

tree_type_t lal::generate::_tree_generator< graphs::free_tree, std::is_base_of_v<graphs::free_tree, graphs::free_tree>, >::get_tree ( )

inlinenoexceptinherited

Retrieve the generated tree.

This function first calls __get_tree and then modifies the generated tree according to the values:

• set_normalise_tree
• set_calculate_size_subtrees
• set_calculate_tree_type

Returns

A free/rooted tree depending on the type of the class inheriting from this. The type of generation of tree differs from one type of class to another.

next()

void lal::generate::all_ulab_free_trees::next ( )

noexcept

Generates next tree.

Modifies the internal state so that the next tree can be retrieved using method get_tree.

Precondition

The generator must have been initialised.

set_calculate_size_subtrees()

void lal::generate::_tree_generator< graphs::free_tree, std::is_base_of_v<graphs::free_tree, graphs::free_tree>, >::set_calculate_size_subtrees ( bool v )

inlinenoexceptinherited

Should the size of the subtrees be calculated?

Parameters

v	Boolean value.

set_calculate_tree_type()

void lal::generate::_tree_generator< graphs::free_tree, std::is_base_of_v<graphs::free_tree, graphs::free_tree>, >::set_calculate_tree_type ( bool v )

inlinenoexceptinherited

Should the tree be classified into types?

See lal::graphs::tree_type for details on the classification.

Parameters

v	Boolean value.

set_normalise_tree()

void lal::generate::_tree_generator< graphs::free_tree, std::is_base_of_v<graphs::free_tree, graphs::free_tree>, >::set_normalise_tree ( bool v )

inlinenoexceptinherited

Should trees be normalised?

Parameters

v	Boolean value.

yield_tree()

graphs::free_tree lal::generate::all_ulab_free_trees::yield_tree ( )

inlinevirtualnoexcept

Yields a tree, advancing the generator if necessary.

In case the class that inherits from this one is exhaustive then this function also moves the generator forward with its appropriate method. If the class is random, then it just calls get_tree().

Returns

A free/rooted tree depending on the type of the class inheriting from this. The type of generation of tree differs from one type of class to another.

Implements lal::generate::_tree_generator< graphs::free_tree >.

Member Data Documentation

m_c

uint32_t lal::generate::all_ulab_free_trees::m_c

private

An index to the first element of \(L_2\).

\(L_2\) is the second principal subsequence of \(L\).

m_r

uint32_t lal::generate::all_ulab_free_trees::m_r

private

Exactly \(m - 1\).

Read the paper: page 542, first paragraph.

---

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

• lal/generate/all_ulab_free_trees.hpp