lal::generate Namespace Reference

Generation of different classes of objects. More...

Classes
class	_rand_lab_free_trees
	Uniformly random generation of labelled free trees. More...
class	_rand_lab_rooted_trees
	Uniformly random generation of labelled rooted trees. More...
class	_rand_ulab_free_trees
	Uniformly random generation of unlabelled free trees. More...
class	_rand_ulab_rooted_trees
	Uniformly random generation of unlabelled rooted trees. More...
class	_tree_generator
	Base class for tree generators. More...
class	all_arrangements
	Exhaustive enumeration of arrangements of any graph. More...
class	all_lab_free_trees
	Exhaustive enumeration of labelled free trees. More...
class	all_lab_rooted_trees
	Exhaustive enumeration of labelled rooted trees. More...
class	all_planar_arrangements
	Exhaustive enumeration of planar arrangements of a labeled free tree. More...
class	all_projective_arrangements
	Exhaustive enumeration of projective arrangements of a labeled rooted tree. More...
class	all_ulab_free_trees
	Exhaustive enumeration of unlabelled free trees. More...
class	all_ulab_rooted_trees
	Exhaustive enumeration of unlabelled rooted trees. More...
struct	exhaustive_random_type
	Shorthand to get one of exhaustive_t or random_t. More...
struct	exhaustive_t
	Type for exhasutive enumeration of trees. More...
struct	labelled_t
	Type for labelled tree generation. More...
struct	labelled_unlabelled_type
	Shorthand to get one of labelled_t or unlabelled_t. More...
class	rand_arrangements
	Random generation of arrangements of any graph. More...
class	rand_lab_free_trees
	Uniformly random generation of labelled free trees. More...
class	rand_lab_rooted_trees
	Uniformly random generation of labelled rooted trees. More...
class	rand_planar_arrangements
	Uniformly random generation of planar arrangements of a labeled rooted tree. More...
class	rand_projective_arrangements
	Uniformly random generation of projective arrangements of a labeled rooted tree. More...
class	rand_ulab_free_trees
	Uniformly random generation of unlabelled free trees. More...
class	rand_ulab_rooted_trees
	Uniformly random generation of unlabelled rooted trees. More...
struct	random_t
	Type for random generation of trees. More...
struct	tree_generator_type
	Automatic tree generator type generator. More...
struct	unlabelled_t
	Type for unlabelled tree generation. More...

Typedefs
template<bool is_exhaustive>
using	exhaustive_random_type_t = typename exhaustive_random_type< is_exhaustive >::type
	Shorthand of exhaustive_random_type.
template<bool is_labelled>
using	labelled_unlabelled_type_t = typename labelled_unlabelled_type< is_labelled >::type
	Shorthand of labelled_unlabelled_type.
template<typename exhaustive_random , typename labelled_unlabelled , class tree_t >
using	tree_generator_type_t = typename tree_generator_type< exhaustive_random, labelled_unlabelled, tree_t >::type
	Typedef of tree_generator_type.

Detailed Description

Generation of different classes of objects.

This namespace contains algorithms for the generation of trees and of arrangements.

Generating trees

The classes that generate trees have a self-explanatory format:

1_2_3_trees

The numbers are placeholders for the following:

• 3: rooted/free – Generate rooted or free trees.
• 2: lab/ulab – Generate labelled or unlabelled free/rooted trees.
• 1: rand/all – Indicates whether the generation is to be random (rand) or exhaustive (all). An exhaustive generation will enumerate all lab/ulab rooted/free trees whereas random generation generate trees unformly at random.

Therefore, the class lal::generate::rand_lab_rooted_trees generates random labelled rooted trees uniformly at random, and the class lal::generate::all_ulab_free_trees should be used to enumerate all unlabelled free trees.

All classes for tree generation return trees that are preprocessed. This preprocessing varies depending on whether the tree is rooted or free. The full preprocessing details can be checked in class lal::generate::_tree_generator, from which all these classes inherit.

Using these classes is straightforward. To generate trees uniformly at random:

lal::generate::rand_2_3_trees TreeGen(n);
for (int i = 0; i < 100; ++i) {
    const lal::graphs::3_tree T = TreeGen.get_tree();
    // ...
}

To enumerate all trees:

lal::generate::all_2_3_trees TreeGen(n);
while (not TreeGen.end()) {
    const lal::graphs::3_tree T = TreeGen.get_tree();
    TreeGen.next();
    // ...
}

Alternatively,

for (lal::generate::all_2_3_trees TreeGen(n); not TreeGen.end(); TreeGen.next()) {
    const lal::graphs::3_tree T = TreeGen.get_tree();
    // ...
}

And even,

lal::generate::all_2_3_trees TreeGen(n);
while (not TreeGen.end()) {
    const lal::graphs::3_tree T = TreeGen.yield_tree();
    // ...
}

(remember to replace the numbers in the actual code!).

Remarks

In this documentation you will find 8 classes for random generation of trees. Users should refrain from using those starting with '_' as the trees returned by these classes are not preprocessed. However, if one wishes to know the implementation details (as for algorithms implemented, and the papers cited), please, read the documentation of said classes.

Generating arrangements

This namespace contains classes for the generation of arrangements of a given tree. Depending on the type of arrangements, the given tree should be free or rooted accordingly. Again, the names for these classes are also self-explanatory:

1_2_arrangement

The numbers are placeholders for the following:

• 2: NULL/projective/planar – Indicates whether the generated arrangements should be unconstrained (NULL), projective, or planar. By NULL we mean that the keyword should be omitted (see examples).
• 1: rand/all – As before, this indicates whether the generation is to be random (rand) or exhaustive (all). An exhaustive generation will enumerate all arrangements

Therefore,

• the class lal::generate::rand_projective_arrangements generates random projective arrangements of a tree,
• the class lal::generate::all_projective_arrangements is used to enumerate all projective arrangements of a tree,
• the class lal::generate::rand_planar_arrangements generates random planar arrangements of a tree, and
• the class lal::generate::all_planar_arrangements is used to enumerate all planar arrangements of a tree.

Similary,

• the class lal::generate::rand_arrangements generates unconstrained random arrangements, and
• the class lal::generate::all_arrangements is used to enumerate all unconstrained arrangements of a tree (i.e., all the \(n!\) arrangements).

Using these classes is straightforward. To generate trees uniformly at random:

// given a tree T (of the appropriate type)
lal::generate::rand_2_arrangements ArrGen(T);
for (int i = 0; i < 100; ++i) {
    const lal::linear_arrangement arr = ArrGen.get_arrangement();
    // ...
}

To enumerate all arrangements:

// given a tree T (of the appropriate type -- indicated with the '2')
lal::generate::all_2_arrangements ArrGen(T);
while (not ArrGen.end()) {
    const lal::linear_arrangement arr = ArrGen.get_arrangement();
    ArrGen.next();
    // ...
}

Alternatively,

for (lal::generate::all_2_arrangements ArrGen(n); not ArrGen.end(); ArrGen.next()) {
        const lal::linear_arrangement arr = ArrGen.get_arrangement();
    // ...
}

And even,

// given a tree T (of the appropriate type)
lal::generate::all_2_arrangements ArrGen(T);
while (not ArrGen.end()) {
    const lal::linear_arrangement arr = ArrGen.yield_arrangement();
    // ...
}

(remember to replace the numbers in the actual code!).

Remarks

In all cases, the arrangements generated are considered to be labelled, i.e., there are no symmetries taken into account when it comes to enumerating or generating uniformly at random said arrangements. For example, for any \(n\)-vertex star tree, the class lal::generate::all_projective_arrangements will enumerate \(n!\) arrangements.