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 Member Functions
	all_ulab_free_trees () noexcept
	Empty constructor.
	all_ulab_free_trees (const uint64_t n) noexcept
	Constructor with number of nodes.
	all_ulab_free_trees (const all_ulab_free_trees &Gen) noexcept=default
	Copy constructor.
	all_ulab_free_trees (all_ulab_free_trees &&Gen) noexcept=default
	Move constructor.
	~all_ulab_free_trees () noexcept=default
	Default destructor.
all_ulab_free_trees &	operator= (const all_ulab_free_trees &g) noexcept=default
	Copy assignment operator.
all_ulab_free_trees &	operator= (all_ulab_free_trees &&g) noexcept=default
	Move assignment operator.
void	init (const uint64_t n) noexcept
	Initializes the generator with a given number of vertices.
void	clear () noexcept
	Clears the memory used.
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.
graphs::free_tree	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_normalize_tree (const bool v) noexcept
	Should trees be normalized?
void	set_calculate_size_subtrees (const bool v) noexcept
	Should the size of the subtrees be calculated?
void	set_calculate_tree_type (const 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
uint64_t	m_n
	Number of vertices.
bool	m_normalize_tree
	Normalize 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
detail::array< uint64_t >	m_L
	Canonical level sequence of the tree.
detail::array< uint64_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\).
uint64_t	m_p
	Largest integer such that \(l_p \neq 2\).
uint64_t	m_q
	Largest integer such that \(q < p, \; l_q = l_p - 1\).
uint64_t	m_h1
	Maximum level number in the first principal subsequence.
uint64_t	m_h2
	Maximum level number in the second principal subsequence.
uint64_t	m_c
	An index to the first element of \(L_2\).
uint64_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?

Static Private Attributes
static constexpr bool	is_free
	Helpful Boolean value to compact 'if constexpr' expressions.

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 [49]. 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:

lal::generate::all_ulab_free_trees Gen(n);
while (not Gen.end()) {
    const lal::graphs::free_tree t = Gen.get_tree();
    // ...
    Gen.next();
}

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

for (lal::generate::all_ulab_free_trees Gen(n); not Gen.end(); Gen.next()) {
    const lal::graphs::free_tree t = Gen.get_tree();
    // ...
}

Equivalently,

lal::generate::all_ulab_free_trees Gen(n);
while (not Gen.end()) {
    const lal::graphs::free_tree t = Gen.yield_tree();
    // ...
}

Constructor & Destructor Documentation

all_ulab_free_trees() [1/3]

lal::generate::all_ulab_free_trees::all_ulab_free_trees ( const uint64_t n )

inlinenoexcept

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 )

defaultnoexcept

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 )

defaultnoexcept

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 ( )

nodiscardprotectedvirtualnoexcept

Constructs the current tree.

Returns

The tree generated with method next().

Precondition

The generator must have been initialized.

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, >::activate_all_postprocessing_actions ( )

inlinenoexceptinherited

Activates all postprocessing actions.

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

clear()

void lal::generate::all_ulab_free_trees::clear ( )

inlinenoexcept

Clears the memory used.

Postcondition

Method init must be called after every call to clear.

deactivate_all_postprocessing_actions()

void lal::generate::_tree_generator< 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()

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

inlinenodiscardnoexceptinherited

Retrieve the generated tree.

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

• set_normalize_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.

init()

void lal::generate::all_ulab_free_trees::init ( const uint64_t n )

inlinenoexcept

Initializes the generator with a given number of vertices.

Parameters

n	Number of vertices.

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 initialized.

set_calculate_size_subtrees()

void lal::generate::_tree_generator< graphs::free_tree, >::set_calculate_size_subtrees ( const 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, >::set_calculate_tree_type ( const 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_normalize_tree()

void lal::generate::_tree_generator< graphs::free_tree, >::set_normalize_tree ( const bool v )

inlinenoexceptinherited

Should trees be normalized?

Parameters

v	Boolean value.

yield_tree()

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

inlinenodiscardvirtualnoexcept

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.

Postcondition

The generator advances to the next tree.

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

Member Data Documentation

m_c

uint64_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

uint64_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