# usainboltz.sage_examples.cayley_tree¶

## Cayley trees¶

Cayley trees are non-ordered labeled trees. We can use SageMath LabelledRootedTree # noqa to build them. We describe here how to write a grammar for Cayley trees in UsainBoltz and how to generated sage objects.

The grammar of Cayley trees of size given by their number of vertices, can be written as follows:

>>> from usainboltz import *
>>> from usainboltz.generator import rng_seed
>>> import warnings; warnings.filterwarnings("ignore", category=UserWarning, module='cvxpy.problems.problem')

>>> z = Atom()
>>> C = RuleName("C")
>>> grammar = Grammar({C: z * Set(C)}, labelled=True)
>>> grammar
{
C : Product(z, Set(C))
}


To obtain a generator for this grammar, one must write:

>>> generator = Generator(grammar, C, singular=True)


But by default, UsainBoltz generates tuples:

>>> res = generator.sample((10, 20))
>>> res.obj
(1, [(8, [(0, [(7, [(5, [])])])]), (4, [(3, [(6, [])]), (9, [(2, [])])])])


Even if the default data structure generated use list it should be interpreted as unordered.

Sage LabelledRootedTree can be obtained using the builders feature: we must tell the generator how to build C objects:

>>> from sage.combinat.rooted_tree import LabelledRootedTree


A Cayley tree is a labeled root whose children are Cayley trees

>>> def build_tree(tupl):
...     z, sub_trees = tupl
...     return LabelledRootedTree(sub_trees, label=z)
>>> generator.set_builder(C, build_tree)


Now, the generator directly generates LabelledRootedTree objects:

>>> res = generator.sample((10, 20))
>>> tree = res.obj
>>> tree.parent()
Labelled rooted trees

>>> from sage.all import ascii_art
>>> ascii_art(tree)
7
|
0
|
6
|
4
|
10
|
2_
/ /
3 9
| |
8 5
|
1