lal::generate::all_lab_rooted_trees Class Reference

Exhaustive enumeration of labelled rooted trees. More...

#include <all_lab_rooted_trees.hpp>

Inheritance diagram for lal::generate::all_lab_rooted_trees:

Public Member Functions
	all_lab_rooted_trees () noexcept
	Empty constructor.
	all_lab_rooted_trees (uint64_t n) noexcept
	Constructor with number of nodes. More...
	all_lab_rooted_trees (const all_lab_rooted_trees &Gen)=default
	Copy constructor. More...
	all_lab_rooted_trees (all_lab_rooted_trees &&Gen)=default
	Move constructor. More...
	~all_lab_rooted_trees ()=default
	Default destructor.
all_lab_rooted_trees &	operator= (const all_lab_rooted_trees &g) noexcept=default
	Copy assignment operator.
all_lab_rooted_trees &	operator= (all_lab_rooted_trees &&g) noexcept=default
	Move assignment operator.
void	init (uint64_t n) noexcept
	Initializes the generator with a given number of vertices. More...
void	clear () noexcept
	Clears the memory used. More...
bool	end () const noexcept
	Returns true if the end of the iteration was reached.
node	get_current_root () const noexcept
	Returns the current root.
void	next () noexcept
	Generates next tree. More...
void	reset () noexcept
	Sets the generator to its initial state.
bool	has_next () const noexcept
	Returns whether there are more trees to generate.
graphs::rooted_tree	yield_tree () noexcept
	Yields a tree, advancing the generator if necessary. More...
graphs::rooted_tree	get_tree () noexcept
	Retrieve the generated tree. More...
void	activate_all_postprocessing_actions () noexcept
	Activates all postprocessing actions. More...
void	deactivate_all_postprocessing_actions () noexcept
	Deactivates all postprocessing actions. More...
void	set_normalise_tree (bool v) noexcept
	Should trees be normalised? More...
void	set_calculate_size_subtrees (bool v) noexcept
	Should the size of the subtrees be calculated? More...
void	set_calculate_tree_type (bool v) noexcept
	Should the tree be classified into types? More...

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

Protected Attributes
uint64_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
all_lab_free_trees	m_gen_lab_free_tree
	Labelled free tree generator.
graphs::free_tree	m_cur_ftree
	Current labelled free tree.
node	m_cur_root
	Current root.
bool	m_reached_end = false
	Has the end of the generation been reached?

Detailed Description

Exhaustive enumeration of labelled rooted trees.

This class enumerates all labelled rooted trees of a given number of vertices. It is based on the labelled free trees generator (see all_lab_free_trees).

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 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:

all_lab_rooted_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_lab_rooted_trees Gen(n); not Gen.end(); Gen.next()) {
    const auto t = Gen.get_tree();
    // ...
}

Equivalently,

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

Constructor & Destructor Documentation

all_lab_rooted_trees() [1/3]

lal::generate::all_lab_rooted_trees::all_lab_rooted_trees ( uint64_t  n )

inlinenoexcept

Constructor with number of nodes.

Parameters

n	Number of nodes.

all_lab_rooted_trees() [2/3]

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

default

Copy constructor.

Parameters

Gen	Exhaustive labelled rooted tree generator..

all_lab_rooted_trees() [3/3]

lal::generate::all_lab_rooted_trees::all_lab_rooted_trees ( all_lab_rooted_trees &&  Gen )

default

Move constructor.

Parameters

Gen	Generator of the same type.

Member Function Documentation

__get_tree()

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

inlineprotectedvirtualnoexcept

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

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.

init()

void lal::generate::all_lab_rooted_trees::init ( uint64_t  n )

inlinenoexcept

Initializes the generator with a given number of vertices.

Parameters

n	Number of vertices.

next()

void lal::generate::all_lab_rooted_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 initialised.

set_calculate_size_subtrees()

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

inlinenoexceptinherited

Should trees be normalised?

Parameters

v	Boolean value.

yield_tree()

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

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_lab_rooted_trees.hpp