lal::generate::_rand_ulab_free_trees Class Reference

Uniformly random selection 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 (const uint64_t n, const uint64_t seed=0) noexcept
	Constructor with size of tree and seed for the random number generator.
	_rand_ulab_free_trees (const _rand_ulab_free_trees &Gen) noexcept=default
	Copy constructor.
	_rand_ulab_free_trees (_rand_ulab_free_trees &&Gen) noexcept=default
	Move constructor.
	~_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 (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::free_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.

Private Member Functions
uint64_t	forest (const uint64_t m, const uint64_t q, uint64_t nt) noexcept
	Generates uniformly at random a forest of m nodes.
void	bicenter (const 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)\).
void	init_fn () noexcept
	Initialiases m_fn with values from the OEIS (see [44]).
const numeric::integer &	get_fn (const uint64_t n) noexcept
	Computes and returns the value \(f_n\).
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.

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

Detailed Description

Uniformly random selection 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 [48]. This algorithm relies on the ranrut procedure (see [38], chapter 29) and runs in about the same time. The implementation of Wilf's paper (see [48]) in functions get_tree, forest, and bicenter includes the correction pointed out in [36] (page 38).

Constructor & Destructor Documentation

_rand_ulab_free_trees() [1/3]

lal::generate::_rand_ulab_free_trees::_rand_ulab_free_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_free_trees() [2/3]

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

defaultnoexcept

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 )

defaultnoexcept

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 )

nodiscardprivatenoexcept

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 ( const uint64_t n )

nodiscardprotectednoexceptinherited

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 ( const uint64_t m, const uint64_t q, uint64_t nt )

nodiscardprivatenoexcept

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 )

nodiscardprivatenoexcept

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 [48] 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 )

nodiscardprivatenoexcept

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 [40]).

Parameters

n	Number of nodes of the tree.

Returns

\(f_n\).

get_rn()

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

nodiscardprotectednoexceptinherited

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

nodiscardnoexcept

Generates uniformly at random a free unlabelled tree.

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

Returns

An unlabelled free tree.

init()

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

inlinenoexcept

Sets the size of the unlabelled trees to generate.

Initializes m_rn with values extracted from [45]. It also initializes m_fn with values extracted from [44].

Initializes 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 ( const uint64_t n, const uint64_t lr, uint64_t nt )

nodiscardprotectednoexceptinherited

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 [48].

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

head_vector lal::generate::_rand_ulab_rooted_trees::m_head_vector

protectedinherited

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

protectedinherited

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

protectedinherited

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

protectedinherited

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