lal::generate::_rand_ulab_rooted_trees Class Reference

Uniformly random generation of unlabelled rooted trees. More...

#include <rand_ulab_rooted_trees.hpp>

Inheritance diagram for lal::generate::_rand_ulab_rooted_trees:

Public Member Functions
	_rand_ulab_rooted_trees (uint32_t n, uint32_t seed=0) noexcept
	Constructor with size of tree and seed for the random number generator.
	_rand_ulab_rooted_trees (const _rand_ulab_rooted_trees &Gen)=default
	Copy constructor.
	_rand_ulab_rooted_trees (_rand_ulab_rooted_trees &&Gen)=default
	Move constructor.
virtual	~_rand_ulab_rooted_trees ()=default
	Destructor.
graphs::rooted_tree	get_tree () noexcept
	Generates uniformly at random a free unlabelled tree.
void	clear () noexcept
	Clears the memory occupied.

Protected Member Functions
virtual void	init (uint32_t seed=0) noexcept
	Sets the size of the unlabelled trees to generate.
std::pair< uint32_t, uint32_t >	ranrut (uint32_t n, uint32_t lr, uint32_t nt) noexcept
	Generates uniformly at random a rooted unlabelled tree of n nodes.
void	init_rn () noexcept
	Initialiases m_rn with 31 values from the OEIS (see [33]).
const numeric::integer &	get_rn (uint32_t n) noexcept
	Computes all the values \(t_i\) for \(i \in [1,n]\).
std::pair< uint32_t, uint32_t >	choose_jd_from_T (uint32_t n) noexcept
	Chooses uniformly at random a pair \((j,d)\), according to some probability.

Protected Attributes
const uint32_t	m_n
	Number of nodes of the tree.
std::mt19937	m_gen
	Random number generator.
std::uniform_real_distribution< double >	m_unif
	Distribution of the numbers.
std::vector< numeric::integer >	m_rn
	The number of unlabelled rooted trees.
internal::data_array< uint32_t >	m_head_vector
	The head vector of the tree under construction.

Detailed Description

Uniformly random generation of unlabelled rooted trees.

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

Every call to get_tree generates rooted unlabelled trees uniformly at random using the ranrut procedure (see [27], chapter 29).

Constructor & Destructor Documentation

_rand_ulab_rooted_trees() [1/3]

lal::generate::_rand_ulab_rooted_trees::_rand_ulab_rooted_trees ( uint32_t n, uint32_t seed = 0 )

noexcept

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. If the seed is 0 then a random seed is generated and used.

_rand_ulab_rooted_trees() [2/3]

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

default

Copy constructor.

Parameters

Gen	Random unlabelled rooted tree generator.

_rand_ulab_rooted_trees() [3/3]

lal::generate::_rand_ulab_rooted_trees::_rand_ulab_rooted_trees ( _rand_ulab_rooted_trees && Gen )

default

Move constructor.

Parameters

Gen	Random unlabelled rooted tree generator.

Member Function Documentation

choose_jd_from_T()

std::pair< uint32_t, uint32_t > lal::generate::_rand_ulab_rooted_trees::choose_jd_from_T ( uint32_t n )

protectednoexcept

Chooses uniformly at random a pair \((j,d)\), according to some probability.

Probability of choosing \((j,d)\) is: \(\frac{d \cdot t_{k - jd} \cdot t_d}{(k - 1)t_k}\).

Parameters

n	Number of nodes.

Returns

A pair of integers \((j,d)\) such that \(j \ge 1\), \(jd \le n\) and \(j \ge 1\), \(jd \le n\).

clear()

void lal::generate::_rand_ulab_rooted_trees::clear ( )

noexcept

Clears the memory occupied.

In order to save computation time, this class has been designed to reuse memory when generating trees. For example, since it needs the values of well-known integer sequences (see attribute m_rn) that are costly to compute every time they are needed, they are stored in memory and reused over time.

So, if the user wants to generate trees of 1000 nodes there will be too much memory occupied (and unused) if then this class is used to generate trees of 10 nodes. In cases like this it is recommended to clear the memory occupied.

Postcondition

After calling this method, the contents of the attributes m_rn are cleared. Attribute m_rn is then assigned the same 31 values that it is assigned when creating an object of this class.

get_rn()

const numeric::integer & lal::generate::_rand_ulab_rooted_trees::get_rn ( uint32_t n )

protectednoexcept

Computes all the values \(t_i\) for \(i \in [1,n]\).

Here \(n\) is m_n. In case these values have already been calculated, this method does nothing.

get_tree()

graphs::rooted_tree lal::generate::_rand_ulab_rooted_trees::get_tree ( )

noexcept

Generates uniformly at random a free unlabelled tree.

Returns

An unlabelled rooted tree. The tree is rooted at vertex 0.

init()

virtual void lal::generate::_rand_ulab_rooted_trees::init ( uint32_t seed = 0 )

protectedvirtualnoexcept

Sets the size of the unlabelled trees to generate.

Initialises m_rn with 31 values are extracted from [33].

Initialises the random number generator with seed. When seed is 0, a random seed is used.

Parameters

seed	Integer value used to seed the random number generator.

Reimplemented in lal::generate::_rand_ulab_free_trees.

ranrut()

std::pair< uint32_t, uint32_t > lal::generate::_rand_ulab_rooted_trees::ranrut ( uint32_t n, uint32_t lr, uint32_t nt )

protectednoexcept

Generates uniformly at random a rooted unlabelled tree of n nodes.

The first call to this method should have lr = m_n + 1.

Parameters

n	Number of nodes of the rooted tree to generate.
lr	Pointer to the root of the last tree added. m_head_vector[lr] is the node that the root points to.
nt	Index to m_head_vector where we have to place the new tree.

Returns

Two indices: the index of the root of the last tree generated and where to store the next tree in m_head_vector.

Member Data Documentation

m_head_vector

internal::data_array<uint32_t> lal::generate::_rand_ulab_rooted_trees::m_head_vector

protected

The head vector of the tree under construction.

This list has n values for m_n nodes. The first position contains the root vertex.

Do not use its actual type (lal::head_vector) in an attempt to make memory usage a bit more efficient.

m_rn

std::vector<numeric::integer> lal::generate::_rand_ulab_rooted_trees::m_rn

protected

The number of unlabelled rooted trees.

Contains \(r_n\) for \(n\ge 0\).

---

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

• lal/generate/rand_ulab_rooted_trees.hpp