lal::generate::rand_planar_arrangements Class Reference

Uniformly random selection of planar arrangements of a free tree. More...

#include <rand_planar_arrangements.hpp>

Public Member Functions
	rand_planar_arrangements (const graphs::free_tree &T, const uint64_t seed=0) noexcept
	Constructor with a constant reference to a free tree.
	rand_planar_arrangements (const graphs::rooted_tree &T, const uint64_t seed=0) noexcept
	Constructor with rooted tree.
	rand_planar_arrangements (const rand_planar_arrangements &Gen) noexcept=default
	Default copy constructor.
	rand_planar_arrangements (rand_planar_arrangements &&Gen) noexcept=default
	Default move constructor.
	~rand_planar_arrangements ()=default
	Default destructor.
linear_arrangement	get_arrangement () noexcept
	Make a random planar arrangement of a rooted tree.
linear_arrangement	yield_arrangement () noexcept
	Returns a random planar arrangement.

Private Attributes
graphs::free_tree	m_T_copy
	A copy of a free tree.
const graphs::free_tree &	m_T
detail::array< std::vector< node > >	m_rdata
	The random data for all vertices.
node	m_previous_root
std::mt19937	m_gen
	Random number generator.

Detailed Description

Uniformly random selection of planar arrangements of a free tree.

This class does not take into account the symmetries between arrangements produced by swapping leaves of the tree connected to the same parent. That is, the arrangements are select from the can be seen as arrangements of labelled trees. Therefore, this class will select u.a.r. one of the \(n!\) arrangements for a star tree of \(n\) vertices.

See Types of arrangements for the definition of planar arrangements.

An example of usage of this class is

// given a rooted tree T
lal::generate::rand_planar_arrgements Gen(T);
for (int i = 0; i < 100; ++i) {
    const lal::linear_arrangement& arr = Gen.get_arrangement();
    // ...
}

Equivalently,

// given a rooted tree T
lal::generate::rand_planar_arrangements Gen(T);
for (int i = 0; i < 100; ++i) {
    const lal::linear_arrangement& arr = Gen.yield_arrangement();
    // ...
}

Constructor & Destructor Documentation

rand_planar_arrangements() [1/4]

lal::generate::rand_planar_arrangements::rand_planar_arrangements ( const graphs::free_tree & T, const uint64_t seed = 0 )

noexcept

Constructor with a constant reference to a free tree.

Parameters

T	Input free tree
seed	The seed used for the random generator. If the seed is 0 then a random seed is generated and used.

Precondition

The object t must be a tree (see lal::graphs::free_tree::is_tree).

rand_planar_arrangements() [2/4]

lal::generate::rand_planar_arrangements::rand_planar_arrangements ( const graphs::rooted_tree & T, const uint64_t seed = 0 )

noexcept

Constructor with rooted tree.

This constructor transforms the input rooted tree into a free tree.

Parameters

T	Input rooted tree.
seed	The seed used for the random generator. If the seed is 0 then a random seed is generated and used.

Precondition

The object t must be a tree (see lal::graphs::free_tree::is_tree).

rand_planar_arrangements() [3/4]

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

defaultnoexcept

Default copy constructor.

Parameters

Gen	Random planar arrangement generator.

rand_planar_arrangements() [4/4]

lal::generate::rand_planar_arrangements::rand_planar_arrangements ( rand_planar_arrangements && Gen )

defaultnoexcept

Default move constructor.

Parameters

Gen	Random planar arrangement generator.

Member Function Documentation

get_arrangement()

linear_arrangement lal::generate::rand_planar_arrangements::get_arrangement ( )

nodiscardnoexcept

Make a random planar arrangement of a rooted tree.

Returns

A planar arrangement chosen uniformly at random chosen amongst all planar arrangements of t.

Member Data Documentation

m_previous_root

node lal::generate::rand_planar_arrangements::m_previous_root

private

The root chosen in the previous call to get_arrangement or yield_arrangement.

m_rdata

detail::array<std::vector<node> > lal::generate::rand_planar_arrangements::m_rdata

private

The random data for all vertices.

This is a member of the class to avoid its initialisation at every call to get_arrangement.

m_T

const graphs::free_tree& lal::generate::rand_planar_arrangements::m_T

private

The free tree of which we are making planar arrangements uniformly at random.

m_T_copy

graphs::free_tree lal::generate::rand_planar_arrangements::m_T_copy

private

A copy of a free tree.

Used only when this class is constructed with a rooted tree.

---

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

• lal/generate/rand_planar_arrangements.hpp