Rooted (Unordered) Trees#
AUTHORS:
Florent Hivert (2011): initial version
- class sage.combinat.rooted_tree.LabelledRootedTree(parent, children, label=None, check=True)[source]#
Bases:
AbstractLabelledClonableTree
,RootedTree
Labelled rooted trees.
A labelled rooted tree is a rooted tree with a label attached at each node.
More formally: The labelled rooted trees are an inductive datatype defined as follows: A labelled rooted tree is a multiset of labelled rooted trees, endowed with a label (which can be any object, including
None
). The trees that belong to this multiset are said to be the children of the tree. (Notice that the labels of these children may and may not be of the same type as the label of the tree). A labelled rooted tree which has no children (so the only information it carries is its label) is said to be a leaf.Every labelled rooted tree gives rise to an unlabelled rooted tree (
RootedTree
) by forgetting the labels. (This is implemented as a conversion.)INPUT:
children
– a list or tuple or more generally any iterable of trees or objects convertible to treeslabel
– any hashable Sage object (default isNone
)
Note
It is required that all labels are comparable.
EXAMPLES:
sage: x = LabelledRootedTree([], label = 3); x 3[] sage: LabelledRootedTree([x, x, x], label = 2) 2[3[], 3[], 3[]] sage: LabelledRootedTree((x, x, x), label = 2) 2[3[], 3[], 3[]] sage: LabelledRootedTree([[],[[], []]], label = 3) 3[None[], None[None[], None[]]]
>>> from sage.all import * >>> x = LabelledRootedTree([], label = Integer(3)); x 3[] >>> LabelledRootedTree([x, x, x], label = Integer(2)) 2[3[], 3[], 3[]] >>> LabelledRootedTree((x, x, x), label = Integer(2)) 2[3[], 3[], 3[]] >>> LabelledRootedTree([[],[[], []]], label = Integer(3)) 3[None[], None[None[], None[]]]
Children are reordered using the value of the
sort_key()
method:sage: y = LabelledRootedTree([], label = 5); y 5[] sage: xyy2 = LabelledRootedTree((x, y, y), label = 2); xyy2 2[3[], 5[], 5[]] sage: yxy2 = LabelledRootedTree((y, x, y), label = 2); yxy2 2[3[], 5[], 5[]] sage: xyy2 == yxy2 True
>>> from sage.all import * >>> y = LabelledRootedTree([], label = Integer(5)); y 5[] >>> xyy2 = LabelledRootedTree((x, y, y), label = Integer(2)); xyy2 2[3[], 5[], 5[]] >>> yxy2 = LabelledRootedTree((y, x, y), label = Integer(2)); yxy2 2[3[], 5[], 5[]] >>> xyy2 == yxy2 True
Converting labelled into unlabelled rooted trees by forgetting the labels, and back (the labels are initialized as
None
):sage: yxy2crude = RootedTree(yxy2); yxy2crude [[], [], []] sage: LabelledRootedTree(yxy2crude) None[None[], None[], None[]]
>>> from sage.all import * >>> yxy2crude = RootedTree(yxy2); yxy2crude [[], [], []] >>> LabelledRootedTree(yxy2crude) None[None[], None[], None[]]
- sort_key()[source]#
Return a tuple of nonnegative integers encoding the labelled rooted tree
self
.The first entry of the tuple is a pair consisting of the number of children of the root and the label of the root. Then the rest of the tuple is obtained as follows: List the tuples corresponding to all children (we are regarding the children themselves as trees). Order this list (not the tuples!) in lexicographically increasing order, and flatten it into a single tuple.
This tuple characterizes the labelled rooted tree uniquely, and can be used to sort the labelled rooted trees provided that the labels belong to a type which is totally ordered.
Note
The tree
self
must be normalized before calling this method (seenormalize()
). This does not matter unless you are inside theclone()
context manager, because outside of it every rooted tree is already normalized.Note
This method overrides
RootedTree.sort_key()
and returns a result different from what the latter would return, as it wants to encode the whole labelled tree including its labelling rather than just the unlabelled tree. Therefore, be careful with using this method on subclasses ofRootedOrderedTree
; under some circumstances they could inherit it from another superclass instead of fromRootedTree
, which would cause the method to forget the labelling. See the docstrings ofRootedTree.sort_key()
andsage.combinat.ordered_tree.OrderedTree.sort_key()
.EXAMPLES:
sage: LRT = LabelledRootedTrees(); LRT Labelled rooted trees sage: x = LRT([], label = 3); x 3[] sage: x.sort_key() ((0, 3),) sage: y = LRT([x, x, x], label = 2); y 2[3[], 3[], 3[]] sage: y.sort_key() ((3, 2), (0, 3), (0, 3), (0, 3)) sage: LRT.an_element().sort_key() ((3, 'alpha'), (0, 3), (1, 5), (0, None), (2, 42), (0, 3), (0, 3)) sage: lb = RootedTrees()([[],[[], []]]).canonical_labelling() sage: lb.sort_key() ((2, 1), (0, 2), (2, 3), (0, 4), (0, 5))
>>> from sage.all import * >>> LRT = LabelledRootedTrees(); LRT Labelled rooted trees >>> x = LRT([], label = Integer(3)); x 3[] >>> x.sort_key() ((0, 3),) >>> y = LRT([x, x, x], label = Integer(2)); y 2[3[], 3[], 3[]] >>> y.sort_key() ((3, 2), (0, 3), (0, 3), (0, 3)) >>> LRT.an_element().sort_key() ((3, 'alpha'), (0, 3), (1, 5), (0, None), (2, 42), (0, 3), (0, 3)) >>> lb = RootedTrees()([[],[[], []]]).canonical_labelling() >>> lb.sort_key() ((2, 1), (0, 2), (2, 3), (0, 4), (0, 5))
- class sage.combinat.rooted_tree.LabelledRootedTrees[source]#
Bases:
UniqueRepresentation
,Parent
This is a parent stub to serve as a factory class for labelled rooted trees.
EXAMPLES:
sage: LRT = LabelledRootedTrees(); LRT Labelled rooted trees sage: x = LRT([], label = 3); x 3[] sage: x.parent() is LRT True sage: y = LRT([x, x, x], label = 2); y 2[3[], 3[], 3[]] sage: y.parent() is LRT True
>>> from sage.all import * >>> LRT = LabelledRootedTrees(); LRT Labelled rooted trees >>> x = LRT([], label = Integer(3)); x 3[] >>> x.parent() is LRT True >>> y = LRT([x, x, x], label = Integer(2)); y 2[3[], 3[], 3[]] >>> y.parent() is LRT True
Todo
Add the possibility to restrict the labels to a fixed set.
- class sage.combinat.rooted_tree.LabelledRootedTrees_all(category=None)[source]#
Bases:
LabelledRootedTrees
Class of all (unordered) labelled rooted trees.
See
LabelledRootedTree
for a definition.- Element[source]#
alias of
LabelledRootedTree
- class sage.combinat.rooted_tree.RootedTree(parent=None, children=[], check=True)[source]#
Bases:
AbstractClonableTree
,NormalizedClonableList
The class for unordered rooted trees.
The unordered rooted trees are an inductive datatype defined as follows: An unordered rooted tree is a multiset of unordered rooted trees. The trees that belong to this multiset are said to be the children of the tree. The tree that has no children is called a leaf.
The labelled rooted trees (
LabelledRootedTree
) form a subclass of this class; they carry additional data.One can create a tree from any list (or more generally iterable) of trees or objects convertible to a tree.
EXAMPLES:
sage: RootedTree([]) [] sage: RootedTree([[], [[]]]) [[], [[]]] sage: RootedTree([[[]], []]) [[], [[]]] sage: O = OrderedTree([[[]], []]); O [[[]], []] sage: RootedTree(O) # this is O with the ordering forgotten [[], [[]]]
>>> from sage.all import * >>> RootedTree([]) [] >>> RootedTree([[], [[]]]) [[], [[]]] >>> RootedTree([[[]], []]) [[], [[]]] >>> O = OrderedTree([[[]], []]); O [[[]], []] >>> RootedTree(O) # this is O with the ordering forgotten [[], [[]]]
One can also enter any small rooted tree (“small” meaning that no vertex has more than \(15\) children) by using a simple numerical encoding of rooted trees, namely, the
from_hexacode()
function. (This function actually parametrizes ordered trees, and here we make it parametrize unordered trees by forgetting the ordering.)sage: from sage.combinat.abstract_tree import from_hexacode sage: RT = RootedTrees() sage: from_hexacode('32001010', RT) [[[]], [[]], [[], []]]
>>> from sage.all import * >>> from sage.combinat.abstract_tree import from_hexacode >>> RT = RootedTrees() >>> from_hexacode('32001010', RT) [[[]], [[]], [[], []]]
Note
Unlike an ordered tree, an (unordered) rooted tree is a multiset (rather than a list) of children. That is, two ordered trees which differ from each other by switching the order of children are equal to each other as (unordered) rooted trees. Internally, rooted trees are encoded as
sage.structure.list_clone.NormalizedClonableList
instances, and instead of storing their children as an actual multiset, they store their children as a list which is sorted according to theirsort_key()
value. This is as good as storing them as multisets, since thesort_key()
values are sortable and distinguish different (unordered) trees. However, if you wish to define a subclass ofRootedTree
which implements rooted trees with extra structure (say, a class of edge-colored rooted trees, or a class of rooted trees with a cyclic order on the list of children), then the inheritedsort_key()
method will no longer distinguish different trees (and, as a consequence, equal trees will be regarded as distinct). Thus, you will have to override the method by one that does distinguish different trees.- graft_list(other)[source]#
Return the list of trees obtained by grafting
other
onself
.Here grafting means that one takes the disjoint union of
self
andother
, chooses a node ofself
, and adds the root ofother
to the list of children of this node. The root of the resulting tree is the root ofself
. (This can be done for each node ofself
; this method returns the list of all results.)This is useful for free pre-Lie algebras.
EXAMPLES:
sage: RT = RootedTree sage: x = RT([]) sage: y = RT([x, x]) sage: x.graft_list(x) [[[]]] sage: l = y.graft_list(x); l [[[], [], []], [[], [[]]], [[], [[]]]] sage: [parent(i) for i in l] [Rooted trees, Rooted trees, Rooted trees]
>>> from sage.all import * >>> RT = RootedTree >>> x = RT([]) >>> y = RT([x, x]) >>> x.graft_list(x) [[[]]] >>> l = y.graft_list(x); l [[[], [], []], [[], [[]]], [[], [[]]]] >>> [parent(i) for i in l] [Rooted trees, Rooted trees, Rooted trees]
- graft_on_root(other)[source]#
Return the tree obtained by grafting
other
on the root ofself
.Here grafting means that one takes the disjoint union of
self
andother
, and adds the root ofother
to the list of children ofself
. The root of the resulting tree is the root ofself
.This is useful for free Nap algebras.
EXAMPLES:
sage: RT = RootedTree sage: x = RT([]) sage: y = RT([x, x]) sage: x.graft_on_root(x) [[]] sage: y.graft_on_root(x) [[], [], []] sage: x.graft_on_root(y) [[[], []]]
>>> from sage.all import * >>> RT = RootedTree >>> x = RT([]) >>> y = RT([x, x]) >>> x.graft_on_root(x) [[]] >>> y.graft_on_root(x) [[], [], []] >>> x.graft_on_root(y) [[[], []]]
- is_empty()[source]#
Return if
self
is the empty tree.For rooted trees, this always returns
False
.Note
This is not the same as
bool(t)
, which returns whethert
has some child or not.EXAMPLES:
sage: t = RootedTrees(4)([[],[[]]]) sage: t.is_empty() False sage: bool(t) True sage: t = RootedTrees(1)([]) sage: t.is_empty() False sage: bool(t) False
>>> from sage.all import * >>> t = RootedTrees(Integer(4))([[],[[]]]) >>> t.is_empty() False >>> bool(t) True >>> t = RootedTrees(Integer(1))([]) >>> t.is_empty() False >>> bool(t) False
- normalize()[source]#
Normalize
self
.This function is at the core of the implementation of rooted (unordered) trees. The underlying structure is provided by ordered rooted trees. Every rooted tree is represented by a normalized element in the set of its planar embeddings.
There should be no need to call
normalize
directly as it is called automatically upon creation and cloning or modification (byNormalizedClonableList
).The normalization has a recursive definition. It means first that every sub-tree is itself normalized, and also that sub-trees are sorted. Here the sort is performed according to the values of the
sort_key()
method.EXAMPLES:
sage: RT = RootedTree sage: RT([[],[[]]]) == RT([[[]],[]]) # indirect doctest True sage: rt1 = RT([[],[[]]]) sage: rt2 = RT([[[]],[]]) sage: rt1 is rt2 False sage: rt1 == rt2 True sage: rt1._get_list() == rt2._get_list() True
>>> from sage.all import * >>> RT = RootedTree >>> RT([[],[[]]]) == RT([[[]],[]]) # indirect doctest True >>> rt1 = RT([[],[[]]]) >>> rt2 = RT([[[]],[]]) >>> rt1 is rt2 False >>> rt1 == rt2 True >>> rt1._get_list() == rt2._get_list() True
- single_graft(x, grafting_function, path_prefix=())[source]#
Graft subtrees of \(x\) on
self
using the given function.Let \(x_1, x_2, \ldots, x_p\) be the children of the root of \(x\). For each \(i\), the subtree of \(x\) comprising all descendants of \(x_i\) is joined by a new edge to the vertex of
self
specified by the \(i\)-th path in the grafting function (i.e., by the pathgrafting_function[i]
).The number of vertices of the result is the sum of the numbers of vertices of
self
and \(x\) minus one, because the root of \(x\) is not used.This is used to define the product of the Grossman-Larson algebras.
INPUT:
\(x\) – a rooted tree
grafting_function
– a list of paths inself
path_prefix
– optional tuple (default()
)
The
path_prefix
argument is only used for internal recursion.EXAMPLES:
sage: LT = LabelledRootedTrees() sage: y = LT([LT([],label='b')], label='a') sage: x = LT([LT([],label='d')], label='c') sage: y.single_graft(x,[(0,)]) a[b[d[]]] sage: t = LT([LT([],label='b'),LT([],label='c')], label='a') sage: s = LT([LT([],label='d'),LT([],label='e')], label='f') sage: t.single_graft(s,[(0,),(1,)]) a[b[d[]], c[e[]]]
>>> from sage.all import * >>> LT = LabelledRootedTrees() >>> y = LT([LT([],label='b')], label='a') >>> x = LT([LT([],label='d')], label='c') >>> y.single_graft(x,[(Integer(0),)]) a[b[d[]]] >>> t = LT([LT([],label='b'),LT([],label='c')], label='a') >>> s = LT([LT([],label='d'),LT([],label='e')], label='f') >>> t.single_graft(s,[(Integer(0),),(Integer(1),)]) a[b[d[]], c[e[]]]
- sort_key()[source]#
Return a tuple of nonnegative integers encoding the rooted tree
self
.The first entry of the tuple is the number of children of the root. Then the rest of the tuple is obtained as follows: List the tuples corresponding to all children (we are regarding the children themselves as trees). Order this list (not the tuples!) in lexicographically increasing order, and flatten it into a single tuple.
This tuple characterizes the rooted tree uniquely, and can be used to sort the rooted trees.
Note
The tree
self
must be normalized before calling this method (seenormalize()
). This does not matter unless you are inside theclone()
context manager, because outside of it every rooted tree is already normalized.Note
By default, this method does not encode any extra structure that
self
might have. If you have a subclass inheriting fromRootedTree
which allows for some extra structure, you need to overridesort_key()
in order to preserve this structure (for example, theLabelledRootedTree
class does this inLabelledRootedTree.sort_key()
). See the note in the docstring ofsage.combinat.ordered_tree.OrderedTree.sort_key()
for a pitfall.EXAMPLES:
sage: RT = RootedTree sage: RT([[],[[]]]).sort_key() (2, 0, 1, 0) sage: RT([[[]],[]]).sort_key() (2, 0, 1, 0)
>>> from sage.all import * >>> RT = RootedTree >>> RT([[],[[]]]).sort_key() (2, 0, 1, 0) >>> RT([[[]],[]]).sort_key() (2, 0, 1, 0)
- class sage.combinat.rooted_tree.RootedTrees[source]#
Bases:
UniqueRepresentation
,Parent
Factory class for rooted trees.
INPUT:
size
– (optional) an integer
OUTPUT:
the set of all rooted trees (of the given size
size
if specified)EXAMPLES:
sage: RootedTrees() Rooted trees sage: RootedTrees(2) Rooted trees with 2 nodes
>>> from sage.all import * >>> RootedTrees() Rooted trees >>> RootedTrees(Integer(2)) Rooted trees with 2 nodes
- class sage.combinat.rooted_tree.RootedTrees_all[source]#
Bases:
DisjointUnionEnumeratedSets
,RootedTrees
Class of all (unordered, unlabelled) rooted trees.
See
RootedTree
for a definition.- Element[source]#
alias of
RootedTree
- labelled_trees()[source]#
Return the set of labelled trees associated to
self
.EXAMPLES:
sage: RootedTrees().labelled_trees() Labelled rooted trees
>>> from sage.all import * >>> RootedTrees().labelled_trees() Labelled rooted trees
As a consequence:
sage: lb = RootedTrees()([[],[[], []]]).canonical_labelling() sage: lb 1[2[], 3[4[], 5[]]] sage: lb.__class__ <class 'sage.combinat.rooted_tree.LabelledRootedTrees_all_with_category.element_class'> sage: lb.parent() Labelled rooted trees
>>> from sage.all import * >>> lb = RootedTrees()([[],[[], []]]).canonical_labelling() >>> lb 1[2[], 3[4[], 5[]]] >>> lb.__class__ <class 'sage.combinat.rooted_tree.LabelledRootedTrees_all_with_category.element_class'> >>> lb.parent() Labelled rooted trees
- class sage.combinat.rooted_tree.RootedTrees_size(n)[source]#
Bases:
RootedTrees
The enumerated set of rooted trees with a given number of nodes.
The number of nodes of a rooted tree is defined recursively: The number of nodes of a rooted tree with \(a\) children is \(a\) plus the sum of the number of nodes of each of these children.
- cardinality()[source]#
Return the cardinality of
self
.EXAMPLES:
sage: RootedTrees(1).cardinality() 1 sage: RootedTrees(3).cardinality() 2
>>> from sage.all import * >>> RootedTrees(Integer(1)).cardinality() 1 >>> RootedTrees(Integer(3)).cardinality() 2
- check_element(el, check=True)[source]#
Check that a given tree actually belongs to
self
.This just checks the number of vertices.
EXAMPLES:
sage: RT3 = RootedTrees(3) sage: RT3([[],[]]) # indirect doctest [[], []] sage: RT3([[],[],[]]) # indirect doctest Traceback (most recent call last): ... ValueError: wrong number of nodes
>>> from sage.all import * >>> RT3 = RootedTrees(Integer(3)) >>> RT3([[],[]]) # indirect doctest [[], []] >>> RT3([[],[],[]]) # indirect doctest Traceback (most recent call last): ... ValueError: wrong number of nodes
- sage.combinat.rooted_tree.number_of_rooted_trees()[source]#
Return the number of rooted trees with \(n\) nodes.
Compute the number \(a(n)\) of rooted trees with \(n\) nodes using the recursive formula ([SL000081]):
\[a(n+1) = \frac{1}{n} \sum_{k=1}^{n} \left( \sum_{d|k} d a(d) \right) a(n-k+1)\]EXAMPLES:
sage: from sage.combinat.rooted_tree import number_of_rooted_trees sage: [number_of_rooted_trees(i) for i in range(10)] [0, 1, 1, 2, 4, 9, 20, 48, 115, 286]
>>> from sage.all import * >>> from sage.combinat.rooted_tree import number_of_rooted_trees >>> [number_of_rooted_trees(i) for i in range(Integer(10))] [0, 1, 1, 2, 4, 9, 20, 48, 115, 286]
REFERENCES:
[SL000081]Sloane’s OEIS sequence A000081