lal::generate::all_lab_free_trees Class Reference

Exhaustive enumeration of labelled free trees. More...

#include <all_lab_free_trees.hpp>

Inheritance diagram for lal::generate::all_lab_free_trees:

Public Member Functions
	all_lab_free_trees () noexcept
	Empty constructor.
	all_lab_free_trees (const uint64_t n) noexcept
	Constructor with number of nodes.
	all_lab_free_trees (const all_lab_free_trees &Gen) noexcept=default
	Copy constructor.
	all_lab_free_trees (all_lab_free_trees &&Gen) noexcept=default
	Move constructor.
	~all_lab_free_trees ()=default
	Default destructor.
all_lab_free_trees &	operator= (const all_lab_free_trees &g) noexcept=default
	Copy assignment operator.
all_lab_free_trees &	operator= (all_lab_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.
bool	has_next () const noexcept
	Returns whether there are more trees to generate.

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
uint64_t	m_it
	Iterator on the sequence.
uint64_t	m_L
	Left-most position with value \(n-1\).
detail::array< uint64_t >	m_Prufer_seq
	Prüfer sequence.
detail::array< char >	m_sm
	If sm[i] = true iff sm[0..i-1] = true and seq[0..i] = n-2.
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 labelled free trees.

Generates all the labelled free trees of a given number of nodes. The algorithm implemented uses Prüfer sequences (see [41]) and decodes them in \(O(n)\).

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 labelled 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_lab_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_lab_free_trees Gen(n); not Gen.end(); Gen.next()) {
    const lal::graphs::free_tree t = Gen.get_tree();
    // ...
}

Equivalently,

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

Constructor & Destructor Documentation

all_lab_free_trees() [1/3]

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

inlinenoexcept

Constructor with number of nodes.

Parameters

n	Number of nodes.

all_lab_free_trees() [2/3]

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

defaultnoexcept

Copy constructor.

Parameters

Gen	Exhaustive labelled free tree generator.

all_lab_free_trees() [3/3]

lal::generate::all_lab_free_trees::all_lab_free_trees ( all_lab_free_trees && Gen )

defaultnoexcept

Move constructor.

Parameters

Gen	Exhaustive labelled free tree generator.

Member Function Documentation

__get_tree()

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

protectedvirtualnoexcept

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_lab_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_lab_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_lab_free_trees::next ( )

inlinenoexcept

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

---

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

• lal/generate/all_lab_free_trees.hpp