lal::generate::_rand_ulab_rooted_trees Class Reference

Uniformly random selection 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 () noexcept
	Empty constructor.
	_rand_ulab_rooted_trees (const uint64_t n, const uint64_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.
_rand_ulab_rooted_trees &	operator= (const _rand_ulab_rooted_trees &g) noexcept=default
	Copy assignment operator.
_rand_ulab_rooted_trees &	operator= (_rand_ulab_rooted_trees &&g) noexcept=default
	Move assignment operator.
void	init (const uint64_t n, const uint64_t seed=0) noexcept
	Sets the size of the unlabelled trees to generate.
void	clear () noexcept
	Clears the memory used.
graphs::rooted_tree	get_tree () noexcept
	Generates uniformly at random a free unlabelled tree.

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

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.
std::vector< numeric::integer >	m_rn_times_n
	The number of unlabelled rooted trees times number of vertices.
std::vector< numeric::integer >	m_rn_times_n_minus_1
	The number of unlabelled rooted trees times number of vertices minus 1.
head_vector	m_head_vector
	The head vector of the tree under construction.

Detailed Description

Uniformly random selection 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 [38], chapter 29).

Constructor & Destructor Documentation

_rand_ulab_rooted_trees() [1/3]

lal::generate::_rand_ulab_rooted_trees::_rand_ulab_rooted_trees ( const uint64_t n, const 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_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< uint64_t, uint64_t > lal::generate::_rand_ulab_rooted_trees::choose_jd_from_T ( const uint64_t n )

nodiscardprotectednoexcept

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

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 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 values that it is assigned when creating an object of this class.

Method init must be called after every call to clear.

get_rn()

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

nodiscardprotectednoexcept

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

nodiscardnoexcept

Generates uniformly at random a free unlabelled tree.

Returns

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

init()

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

inlinenoexcept

Sets the size of the unlabelled trees to generate.

Adds the remaining necessary values to m_rn..

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

Parameters

n	Number of vertices.
seed	Integer value used to seed the random number generator.

ranrut()

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

nodiscardprotectednoexcept

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

head_vector lal::generate::_rand_ulab_rooted_trees::m_head_vector

protected

The head vector of the tree under construction.

The first position always contains the root vertex. The parent of vertex u is located at m_head_vector[u], but the value is an index from 0 to \(n - 1\), both included.

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\).

m_rn_times_n

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

protected

The number of unlabelled rooted trees times number of vertices.

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

m_rn_times_n_minus_1

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

protected

The number of unlabelled rooted trees times number of vertices minus 1.

Contains \(r_n \cdot (n - 1)\) for \(n\ge 0\).

---

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

• lal/generate/rand_ulab_rooted_trees.hpp