lal::generate::_rand_ulab_free_trees Class Reference

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

#include <rand_ulab_free_trees.hpp>

Inheritance diagram for lal::generate::_rand_ulab_free_trees:

Public Member Functions
	_rand_ulab_free_trees () noexcept
	Empty constructor.
	_rand_ulab_free_trees (uint64_t n, uint64_t seed=0) noexcept
	Constructor with size of tree and seed for the random number generator. More...
	_rand_ulab_free_trees (const _rand_ulab_free_trees &Gen)=default
	Copy constructor. More...
	_rand_ulab_free_trees (_rand_ulab_free_trees &&Gen)=default
	Move constructor. More...
	~_rand_ulab_free_trees ()=default
	Default destructor.
_rand_ulab_free_trees &	operator= (const _rand_ulab_free_trees &g) noexcept=default
	Copy assignment operator.
_rand_ulab_free_trees &	operator= (_rand_ulab_free_trees &&g) noexcept=default
	Move assignment operator.
void	init (uint64_t n, uint64_t seed=0) noexcept
	Sets the size of the unlabelled trees to generate. More...
void	clear () noexcept
	Clears the memory used. More...
graphs::free_tree	get_tree () noexcept
	Generates uniformly at random a free unlabelled tree. More...

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

Protected Attributes
uint64_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. More...
detail::data_array< uint64_t >	m_head_vector
	The head vector of the tree under construction. More...

Private Member Functions
uint64_t	forest (uint64_t m, uint64_t q, uint64_t nt) noexcept
	Generates uniformly at random a forest of m nodes. More...
void	bicenter (uint64_t n) noexcept
	Generates a tree of n nodes with two centroids.
const numeric::integer &	get_alpha_mq (const uint64_t m, const uint64_t q) noexcept
	Computes and return the value \(\alpha(m,q)\). More...
void	init_fn () noexcept
	Initialiases m_fn with values from the OEIS (see [35]).
const numeric::integer &	get_fn (const uint64_t n) noexcept
	Computes and returns the value \(f_n\). More...
std::pair< uint64_t, uint64_t >	choose_jd_from_alpha (const uint64_t m, const uint64_t q) noexcept
	Chooses uniformly at random a pair \((j,d)\), according to some probability. More...

Private Attributes
std::map< std::pair< uint64_t, uint64_t >, numeric::integer >	m_alpha
	Values \(\alpha_{m,q}\). More...
std::vector< numeric::integer >	m_fn
	The number of free unlabelled trees. More...

Detailed Description

Uniformly random generation of unlabelled free trees.

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

Every call to get_tree generates uniformly at random an unlabelled free tree using the algorithm described in [39]. This algorithm relies on the ranrut procedure (see [30], chapter 29) and runs in about the same time. The implementation of Wilf's paper (see [39]) in functions get_tree, forest, and bicenter includes the correction pointed out in [28] (page 38).

Constructor & Destructor Documentation

_rand_ulab_free_trees() [1/3]

lal::generate::_rand_ulab_free_trees::_rand_ulab_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 number generator. If the seed is 0 then a random seed is generated and used.

_rand_ulab_free_trees() [2/3]

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

default

Copy constructor.

Parameters

Gen	Random unlabelled free tree generator.

_rand_ulab_free_trees() [3/3]

lal::generate::_rand_ulab_free_trees::_rand_ulab_free_trees ( _rand_ulab_free_trees &&  Gen )

default

Move constructor.

Parameters

Gen	Random unlabelled free tree generator.

Member Function Documentation

choose_jd_from_alpha()

std::pair< uint64_t, uint64_t > lal::generate::_rand_ulab_free_trees::choose_jd_from_alpha ( const uint64_t  m, const uint64_t  q  )

privatenoexcept

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

Probability of choosing \((j,d)\) is: \(\frac{d \cdot \alpha_{m - jd, q} \cdot t_d}{m\alpha_{m, q}}\). Here, q is fixed to \((n - 1)/2\) where n is m_n.

Parameters

m	Amount of nodes.
q	Maximum amount of nodes per connected component.

Returns

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

choose_jd_from_T()

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

protectednoexceptinherited

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_free_trees::clear ( )

inlinenoexcept

Clears the memory used.

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 attributes m_rn and m_alpha) 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, m_fn and m_alpha are cleared. Attributes m_rn and m_fn are then assigned the same values that they are assigned when creating an object of this class.

Method init must be called after every call to clear.

forest()

uint64_t lal::generate::_rand_ulab_free_trees::forest ( uint64_t  m, uint64_t  q, uint64_t  nt  )

privatenoexcept

Generates uniformly at random a forest of m nodes.

Makes a random forest of m nodes and stores it in m_head_vector. Each tree in the forest has at most q nodes.

Parameters

m	Integer \(m \ge 0\).
q	Integer \(0 \le q \le m\).
nt	Index to m_head_vector indicating where to store the next tree.

Returns

The position where to store the following trees/forests in m_head_vector.

get_alpha_mq()

const numeric::integer & lal::generate::_rand_ulab_free_trees::get_alpha_mq ( const uint64_t  m, const uint64_t  q  )

privatenoexcept

Computes and return the value \(\alpha(m,q)\).

Stores the calculated value in m_alpha. In case the value has already been calculated, this method does nothing. See [39] for details on \(\alpha(m,q)\).

Parameters

m	Number of nodes of the forest.
q	Maximum number of nodes of each connected component of the forest.

Returns

\(\alpha(m,q)\)

get_fn()

const numeric::integer & lal::generate::_rand_ulab_free_trees::get_fn ( const uint64_t  n )

privatenoexcept

Computes and returns the value \(f_n\).

The value \(f_n\) is the number of unlabelled free trees on \(n\) nodes. The method implements Otter's formula (see [31]).

Parameters

n	Number of nodes of the tree.

Returns

\(f_n\).

get_rn()

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

protectednoexceptinherited

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::free_tree lal::generate::_rand_ulab_free_trees::get_tree ( )

noexcept

Generates uniformly at random a free unlabelled tree.

Includes the correction in Wilf's paper (see [39]), as pointed out in [28].

Returns

An unlabelled free tree.

init()

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

inlinenoexcept

Sets the size of the unlabelled trees to generate.

Initialises m_rn with values extracted from [36]. It also initialises m_fn with values extracted from [35].

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

Parameters

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

ranrut()

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

protectednoexceptinherited

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_alpha

std::map<std::pair<uint64_t, uint64_t>, numeric::integer> lal::generate::_rand_ulab_free_trees::m_alpha

private

Values \(\alpha_{m,q}\).

\(\alpha_{m,q}\) is he number of rooted forests of \(m\) nodes whose trees have at most \(q\) nodes each. See [39].

Since \(m\) and \(q\) are usually calculated as \(m=n-1\) and \(q=(n - 1)/2\) there is only one value of \(q\) for each \(n\), so we do not need a matrix.

m_fn

std::vector<numeric::integer> lal::generate::_rand_ulab_free_trees::m_fn

private

The number of free unlabelled trees.

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

m_head_vector

detail::data_array<uint64_t> lal::generate::_rand_ulab_rooted_trees::m_head_vector

protectedinherited

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

protectedinherited

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