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 () noexcept
	Empty constructor.
	_rand_ulab_rooted_trees (uint64_t n, uint64_t seed=0) noexcept
	Constructor with size of tree and seed for the random number generator. More...
	_rand_ulab_rooted_trees (const _rand_ulab_rooted_trees &Gen)=default
	Copy constructor. More...
	_rand_ulab_rooted_trees (_rand_ulab_rooted_trees &&Gen)=default
	Move constructor. More...
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 (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::rooted_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...

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 [30], chapter 29).

Constructor & Destructor Documentation

_rand_ulab_rooted_trees() [1/3]

lal::generate::_rand_ulab_rooted_trees::_rand_ulab_rooted_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_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 ( uint64_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 ( )

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

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

inlinenoexcept

Sets the size of the unlabelled trees to generate.

Adds the remaining necessary values to m_rn..

Initialises 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 ( uint64_t  n, uint64_t  lr, uint64_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

detail::data_array<uint64_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