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')
>>> rng_seed(0xDEADBEEF) # For reproducibility
>>> 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