lal::generate::_rand_lab_free_trees Class Reference

Uniformly random generation of labelled free trees. More...

#include <rand_lab_free_trees.hpp>

Inheritance diagram for lal::generate::_rand_lab_free_trees:

Public Member Functions
	_rand_lab_free_trees () noexcept
	Default constructor.
	_rand_lab_free_trees (uint64_t n, uint64_t seed=0) noexcept
	Constructor with size of tree and seed for the random number generator. More...
	_rand_lab_free_trees (const _rand_lab_free_trees &Gen)=default
	Copy constructor. More...
	_rand_lab_free_trees (_rand_lab_free_trees &&Gen)=default
	Move constructor. More...
	~_rand_lab_free_trees ()=default
	Default destructor.
_rand_lab_free_trees &	operator= (const _rand_lab_free_trees &g) noexcept=default
	Copy assignment operator.
_rand_lab_free_trees &	operator= (_rand_lab_free_trees &&g) noexcept=default
	Move assignment operator.
void	init (uint64_t n, uint64_t seed=0) noexcept
	Initializes the generator with the number of nodes and a seed. More...
void	clear () noexcept
	Clears the memory used. More...
graphs::free_tree	get_tree () noexcept
	Returns a labelled free tree chosen uniformly at random.

Protected Attributes
uint64_t	m_n
	Number of nodes of the tree.
std::mt19937	m_gen
	Random number generator.
std::uniform_int_distribution< uint64_t >	m_unif
	Distribution of the numbers.
detail::data_array< uint64_t >	m_Prufer_seq
	Prüfer sequence.

Detailed Description

Uniformly random generation of labelled free trees.

Users should refrain from using this class. The generation of random labelled trees should be done using the wrapper class rand_lab_free_trees. This class, however, contains the actual code to generate labelled free trees uniformly at random.

This class implements an algorithm that uses uniformly random Prüfer sequences (see [32]). The construction of the free labelled tree is done in \(O(n)\).

Constructor & Destructor Documentation

_rand_lab_free_trees() [1/3]

lal::generate::_rand_lab_free_trees::_rand_lab_free_trees ( uint64_t  n, uint64_t  seed = 0  )

inlinenoexcept

Constructor with size of tree and seed for the random number generator.

In case the seed given is '0', a random seed will be generated.

Parameters

n	Number of nodes.
seed	The seed used for the random generator.

_rand_lab_free_trees() [2/3]

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

default

Copy constructor.

Parameters

Gen	Random labelled free tree generator.

_rand_lab_free_trees() [3/3]

lal::generate::_rand_lab_free_trees::_rand_lab_free_trees ( _rand_lab_free_trees &&  Gen )

default

Move constructor.

Parameters

Gen	Random labelled free tree generator.

Member Function Documentation

clear()

void lal::generate::_rand_lab_free_trees::clear ( )

inlinenoexcept

Clears the memory used.

Postcondition

Method init must be called after every call to clear.

init()

void lal::generate::_rand_lab_free_trees::init ( uint64_t  n, uint64_t  seed = 0  )

inlinenoexcept

Initializes the generator with the number of nodes and a seed.

Parameters

n	Number of nodes.
seed	The seed used for the random generator. If the seed is 0 then a random seed is generated and used.

---

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

• lal/generate/rand_lab_free_trees.hpp