Generates ordered unlabelled trees uniformly at random. More...

#include <RandomTree.h>

Public Member Functions
	RandomTreeGenerator (RNG &gen)

void	selectionSampling (vector< bool > &result, const int n, const int N)

void	randomBalancedParenthesisBitstring (vector< bool > &result, const int numNodes)

template<typename TreeType >
void	generateTree (TreeType &tree, const int numEdges, const bool verbose=false)

Static Protected Member Functions
template<typename T , typename TreeType >
static T::const_iterator	createTree (typename T::const_iterator begin, typename T::const_iterator end, const int parentId, TreeType &tree)

template<typename T >
static T::iterator	phi (typename T::const_iterator begin, typename T::const_iterator end, typename T::iterator outIt)

static bool	isBalanced (vector< bool >::const_iterator begin, vector< bool >::const_iterator end)

template<typename T >
static bool	isWellFormed (typename T::const_iterator begin, typename T::const_iterator end)
	is [begin, end) well-formed? More...

template<typename T >
static T::const_iterator	reducibleIndex (typename T::const_iterator begin, typename T::const_iterator end)

Protected Attributes
RNG &	generator

std::uniform_real_distribution< double >	distribution

Detailed Description

template<typename RNG>
class RandomTreeGenerator< RNG >

Generates ordered unlabelled trees uniformly at random.

Definition at line 15 of file RandomTree.h.

Constructor & Destructor Documentation

template<typename RNG>

RandomTreeGenerator< RNG >::RandomTreeGenerator ( RNG & gen )

inline

Create a random tree generator

Parameters

gen	the random generator to use

Definition at line 19 of file RandomTree.h.

Member Function Documentation

template<typename RNG>

template<typename T , typename TreeType >

static T::const_iterator RandomTreeGenerator< RNG >::createTree	(	typename T::const_iterator	begin,
		typename T::const_iterator	end,
		const int	parentId,
		TreeType &	tree
	)

inlinestaticprotected

Recursively create a tree from a parenthesis bitstring

Parameters

begin	iterator to the beginning of the bitstring
end	iterator past the end of the bistring
parentId	parent node of the node to add
tree	the output tree – node parentId needs to exist before calling this

Definition at line 79 of file RandomTree.h.

template<typename RNG>

template<typename TreeType >

void RandomTreeGenerator< RNG >::generateTree	(	TreeType &	tree,
		const int	numEdges,
		const bool	verbose = `false`
	)

inline

Generate an unlabelled ordered tree uniformly at random

Parameters

tree	a bool-vector for the output tree
numEdges	the number of edges that the tree shall have
verbose	whether to print the bitstring to stdout

Definition at line 54 of file RandomTree.h.

template<typename RNG>

static bool RandomTreeGenerator< RNG >::isBalanced	(	vector< bool >::const_iterator	begin,
		vector< bool >::const_iterator	end
	)

inlinestaticprotected

check wether [begin, end) balanced, i.e. has same number of opening and closing parentheses

Parameters

begin	defines the beginning of the sequence to check
end	defines the item past the end of the sequence to check

Returns: true iff [begin, end) is balanced

Definition at line 134 of file RandomTree.h.

template<typename RNG>

template<typename T >

static bool RandomTreeGenerator< RNG >::isWellFormed	(	typename T::const_iterator	begin,
		typename T::const_iterator	end
	)

inlinestaticprotected

is [begin, end) well-formed?

Definition at line 148 of file RandomTree.h.

template<typename RNG>

template<typename T >

static T::iterator RandomTreeGenerator< RNG >::phi	(	typename T::const_iterator	begin,
		typename T::const_iterator	end,
		typename T::iterator	outIt
	)

inlinestaticprotected

transform a balanced word into a well-formed balanced word. Algorithm from Atkinson, Michael D., and J-R. Sack. "Generating binary trees at random." Information Processing Letters 41.1 (1992): 21-23.

Definition at line 101 of file RandomTree.h.

template<typename RNG>

void RandomTreeGenerator< RNG >::randomBalancedParenthesisBitstring	(	vector< bool > &	result,
		const int	numNodes
	)

inline

Generate a uniformly random balanced parenthesis bitstring, which defines a tree

Parameters

result	a bool-vector for the output tree
numNodes	the number of nodes that the tree shall have

Definition at line 39 of file RandomTree.h.

template<typename RNG>

template<typename T >

static T::const_iterator RandomTreeGenerator< RNG >::reducibleIndex	(	typename T::const_iterator	begin,
		typename T::const_iterator	end
	)

inlinestaticprotected

separate [begin, end) into [begin, result) (irreducible) and [result, end) so that [begin, end) is balanced

Definition at line 160 of file RandomTree.h.

template<typename RNG>

void RandomTreeGenerator< RNG >::selectionSampling	(	vector< bool > &	result,
		const int	n,
		const int	N
	)

inline

Definition at line 23 of file RandomTree.h.

Member Data Documentation

template<typename RNG>

std::uniform_real_distribution<double> RandomTreeGenerator< RNG >::distribution

protected

Definition at line 172 of file RandomTree.h.

template<typename RNG>

RNG& RandomTreeGenerator< RNG >::generator

protected

Definition at line 171 of file RandomTree.h.

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

RandomTree.h

Public Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

template<typename RNG> class RandomTreeGenerator< RNG >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename RNG>
class RandomTreeGenerator< RNG >