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