lal::generate::all_ulab_rooted_trees Class Reference

Exhaustive enumeration of unlabelled rooted trees. More...

#include <all_ulab_rooted_trees.hpp>

Inheritance diagram for lal::generate::all_ulab_rooted_trees:

Public Member Functions
	all_ulab_rooted_trees () noexcept
	Empty constructor.
	all_ulab_rooted_trees (const uint64_t n) noexcept
	Constructor with number of nodes.
	all_ulab_rooted_trees (const all_ulab_rooted_trees &Gen) noexcept=default
	Copy constructor.
	all_ulab_rooted_trees (all_ulab_rooted_trees &&Gen) noexcept=default
	Move constructor.
	~all_ulab_rooted_trees () noexcept=default
	Default destructor.
all_ulab_rooted_trees &	operator= (const all_ulab_rooted_trees &g) noexcept=default
	Copy assignment operator.
all_ulab_rooted_trees &	operator= (all_ulab_rooted_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 the next tree.
void	reset () noexcept
	Sets the generator to its initial state.
graphs::rooted_tree	yield_tree () noexcept
	Yields a tree, advancing the generator if necessary.
graphs::rooted_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::rooted_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
bool	m_is_last = false
	Is the current tree the last tree to be generated?
bool	m_is_first = false
	Is the current tree the first tree to be generated?
bool	m_reached_end = false
	Has the end of the generation been reached?
uint64_t	m_p = 0
	Pointer as in the paper.
detail::array< node >	m_save
	Sequence SAVE.
detail::array< node >	m_prev
	Sequence PREV.
detail::array< node >	m_L
	Level sequence of the tree.

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

Detailed Description

Exhaustive enumeration of unlabelled rooted trees.

Generates all the unlabelled rooted trees of a given number of nodes. The algorithm implemented can be found in [14]. 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 rooted 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_rooted_trees Gen(n);
while (not Gen.end()) {
    const lal::graphs::rooted_tree t = Gen.get_tree();
    // ...
    Gen.next();
}

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

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

Equivalently,

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

Constructor & Destructor Documentation

all_ulab_rooted_trees() [1/3]

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

inlinenoexcept

Constructor with number of nodes.

Parameters

n	Number of nodes.

all_ulab_rooted_trees() [2/3]

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

defaultnoexcept

Copy constructor.

Parameters

Gen	Exhaustive unlabelled rooted tree generator.

all_ulab_rooted_trees() [3/3]

lal::generate::all_ulab_rooted_trees::all_ulab_rooted_trees ( all_ulab_rooted_trees && Gen )

defaultnoexcept

Move constructor.

Parameters

Gen	Exhaustive unlabelled rooted tree generator.

Member Function Documentation

__get_tree()

graphs::rooted_tree lal::generate::all_ulab_rooted_trees::__get_tree ( )

nodiscardprotectedvirtualnoexcept

Constructs the current tree.

Returns

The tree generated with method next(). The tree is rooted at vertex 0.

Precondition

The generator must have been initialized.

Method next must have been called at least once.

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

activate_all_postprocessing_actions()

void lal::generate::_tree_generator< graphs::rooted_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_rooted_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::rooted_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::rooted_tree lal::generate::_tree_generator< graphs::rooted_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_rooted_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_rooted_trees::next ( )

noexcept

Generates the 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.

reset()

void lal::generate::all_ulab_rooted_trees::reset ( )

inlinenoexcept

Sets the generator to its initial state.

Postprocessing actions are not modified.

set_calculate_size_subtrees()

void lal::generate::_tree_generator< graphs::rooted_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::rooted_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::rooted_tree, >::set_normalize_tree ( const bool v )

inlinenoexceptinherited

Should trees be normalized?

Parameters

v	Boolean value.

yield_tree()

graphs::rooted_tree lal::generate::all_ulab_rooted_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::rooted_tree >.

---

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

• lal/generate/all_ulab_rooted_trees.hpp