Ordered Rooted Trees

AUTHORS:

• Florent Hivert (2010-2011): initial revision

• Frédéric Chapoton (2010): contributed some methods

class sage.combinat.ordered_tree.LabelledOrderedTree(parent, children, label=None, check=True)

Bases: AbstractLabelledClonableTree, OrderedTree

Labelled ordered trees.

A labelled ordered tree is an ordered tree with a label attached at each node.

INPUT:

• children – a list or tuple or more generally any iterable of trees or object convertible to trees

• label – any Sage object (default: None)

EXAMPLES:

sage: x = LabelledOrderedTree([], label = 3); x
3[]
sage: LabelledOrderedTree([x, x, x], label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree((x, x, x), label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree([[],[[], []]], label = 3)
3[None[], None[None[], None[]]]

left_right_symmetry()

Return the symmetric tree of self.

The symmetric tree \(s(T)\) of a labelled ordered tree \(T\) is defined as follows: If \(T\) is a labelled ordered tree with children \(C_1, C_2, \ldots, C_k\) (listed from left to right), then the symmetric tree \(s(T)\) of \(T\) is a labelled ordered tree with children \(s(C_k), s(C_{k-1}), \ldots, s(C_1)\) (from left to right), and with the same root label as \(T\).

Note

If you have a subclass of LabelledOrderedTree() which also inherits from another subclass of OrderedTree() which does not come with a labelling, then (depending on the method resolution order) it might happen that this method gets overridden by an implementation from that other subclass, and thus forgets about the labels. In this case you need to manually override this method on your subclass.

EXAMPLES:

sage: L2 = LabelledOrderedTree([], label=2)
sage: L3 = LabelledOrderedTree([], label=3)
sage: T23 = LabelledOrderedTree([L2, L3], label=4)
sage: T23.left_right_symmetry()
4[3[], 2[]]
sage: T223 = LabelledOrderedTree([L2, T23], label=17)
sage: T223.left_right_symmetry()
17[4[3[], 2[]], 2[]]
sage: T223.left_right_symmetry().left_right_symmetry() == T223
True

sort_key()

Return a tuple of nonnegative integers encoding the labelled 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 the concatenation of the tuples associated to these children (we view the children of a tree as trees themselves) from left to right.

This tuple characterizes the labelled tree uniquely, and can be used to sort the labelled ordered trees provided that the labels belong to a type which is totally ordered.

Warning

This method overrides OrderedTree.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 of LabelledOrderedTree; under some circumstances they could inherit it from another superclass instead of from OrderedTree, which would cause the method to forget the labelling. See the docstring of OrderedTree.sort_key().

EXAMPLES:

sage: L2 = LabelledOrderedTree([], label=2)
sage: L3 = LabelledOrderedTree([], label=3)
sage: T23 = LabelledOrderedTree([L2, L3], label=4)
sage: T23.sort_key()
((2, 4), (0, 2), (0, 3))
sage: T32 = LabelledOrderedTree([L3, L2], label=5)
sage: T32.sort_key()
((2, 5), (0, 3), (0, 2))
sage: T23322 = LabelledOrderedTree([T23, T32, L2], label=14)
sage: T23322.sort_key()
((3, 14), (2, 4), (0, 2), (0, 3), (2, 5), (0, 3), (0, 2), (0, 2))

class sage.combinat.ordered_tree.LabelledOrderedTrees(category=None)

Bases: UniqueRepresentation, Parent

This is a parent stub to serve as a factory class for trees with various label constraints.

EXAMPLES:

sage: LOT = LabelledOrderedTrees(); LOT
Labelled ordered trees
sage: x = LOT([], label = 3); x
3[]
sage: x.parent() is LOT
True
sage: y = LOT([x, x, x], label = 2); y
2[3[], 3[], 3[]]
sage: y.parent() is LOT
True

Element

alias of LabelledOrderedTree

cardinality()

Return the cardinality of self.

EXAMPLES:

sage: LabelledOrderedTrees().cardinality()
+Infinity

labelled_trees()

Return the set of labelled trees associated to self.

This is precisely self, because self already is the set of labelled ordered trees.

EXAMPLES:

sage: LabelledOrderedTrees().labelled_trees()
Labelled ordered trees
sage: LOT = LabelledOrderedTrees()
sage: x = LOT([], label = 3)
sage: y = LOT([x, x, x], label = 2)
sage: y.canonical_labelling()
1[2[], 3[], 4[]]

unlabelled_trees()

Return the set of unlabelled trees associated to self.

This is the set of ordered trees, since self is the set of labelled ordered trees.

EXAMPLES:

sage: LabelledOrderedTrees().unlabelled_trees()
Ordered trees

class sage.combinat.ordered_tree.OrderedTree(parent=None, children=None, check=True)

Bases: AbstractClonableTree, ClonableList

The class of (ordered rooted) trees.

An ordered tree is constructed from a node, called the root, on which one has grafted a possibly empty list of trees. There is a total order on the children of a node which is given by the order of the elements in the list. Note that there is no empty ordered tree (so the smallest ordered tree consists of just one node).

INPUT:

One can create a tree from any list (or more generally iterable) of trees or objects convertible to a tree. Alternatively a string is also accepted. The syntax is the same as for printing: children are grouped by square brackets.

EXAMPLES:

sage: x = OrderedTree([])
sage: x1 = OrderedTree([x,x])
sage: x2 = OrderedTree([[],[]])
sage: x1 == x2
True
sage: tt1 = OrderedTree([x,x1,x2])
sage: tt2 = OrderedTree([[], [[], []], x2])
sage: tt1 == tt2
True

sage: OrderedTree([]) == OrderedTree()
True

is_empty()

Return if self is the empty tree.

For ordered trees, this always returns False.

Note

this is different from bool(t) which returns whether t has some child or not.

EXAMPLES:

sage: t = OrderedTrees(4)([[],[[]]])
sage: t.is_empty()
False
sage: bool(t)
True

left_right_symmetry()

Return the symmetric tree of self.

The symmetric tree \(s(T)\) of an ordered tree \(T\) is defined as follows: If \(T\) is an ordered tree with children \(C_1, C_2, \ldots, C_k\) (listed from left to right), then the symmetric tree \(s(T)\) of \(T\) is the ordered tree with children \(s(C_k), s(C_{k-1}), \ldots, s(C_1)\) (from left to right).

EXAMPLES:

sage: T = OrderedTree([[],[[]]])
sage: T.left_right_symmetry()
[[[]], []]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.left_right_symmetry()
[[[[]], []], [[], []], []]

normalize(inplace=False)

Return the normalized tree of self.

INPUT:

• inplace – boolean, (default False) if True, then self is modified and nothing returned. Otherwise the normalized tree is returned.

The normalization of an ordered tree \(t\) is an ordered tree \(s\) which has the property that \(t\) and \(s\) are isomorphic as unordered rooted trees, and that if two ordered trees \(t\) and \(t'\) are isomorphic as unordered rooted trees, then the normalizations of \(t\) and \(t'\) are identical. In other words, normalization is a map from the set of ordered trees to itself which picks a representative from every equivalence class with respect to the relation of “being isomorphic as unordered trees”, and maps every ordered tree to the representative chosen from its class.

This map proceeds recursively by first normalizing every subtree, and then sorting the subtrees according to the value of the sort_key() method.

Consider the quotient map \(\pi\) that sends a planar rooted tree to the associated unordered rooted tree. Normalization is the composite \(s \circ \pi\), where \(s\) is a section of \(\pi\).

EXAMPLES:

sage: OT = OrderedTree
sage: ta = OT([[],[[]]])
sage: tb = OT([[[]],[]])
sage: ta.normalize() == tb.normalize()
True
sage: ta == tb
False

An example with inplace normalization:

sage: OT = OrderedTree
sage: ta = OT([[],[[]]])
sage: tb = OT([[[]],[]])
sage: ta.normalize(inplace=True); ta
[[], [[]]]
sage: tb.normalize(inplace=True); tb
[[], [[]]]

plot()

Plot the tree self.

Warning

For a labelled tree, this will fail unless all labels are distinct. For unlabelled trees, some arbitrary labels are chosen. Use _latex_(), view, _ascii_art_() or pretty_print for more faithful representations of the data of the tree.

EXAMPLES:

sage: p = OrderedTree([[[]],[],[]])
sage: ascii_art(p)
  _o__
 / / /
o o o
|
o
sage: p.plot()                                                              # needs sage.plot
Graphics object consisting of 10 graphics primitives

Now a labelled example:

sage: g = OrderedTree([[],[[]],[]]).canonical_labelling()
sage: ascii_art(g)
  _1__
 / / /
2 3 5
  |
  4
sage: g.plot()                                                              # needs sage.plot
Graphics object consisting of 10 graphics primitives

sort_key()

Return a tuple of nonnegative integers encoding the ordered tree self.

The first entry of the tuple is the number of children of the root. Then the rest of the tuple is the concatenation of the tuples associated to these children (we view the children of a tree as trees themselves) from left to right.

This tuple characterizes the tree uniquely, and can be used to sort the ordered trees.

Note

By default, this method does not encode any extra structure that self might have – e.g., if you were to define a class EdgeColoredOrderedTree which implements edge-colored trees and which inherits from OrderedTree, then the sort_key() method it would inherit would forget about the colors of the edges (and thus would not characterize edge-colored trees uniquely). If you want to preserve extra data, you need to override this method or use a new method. For instance, on the LabelledOrderedTree subclass, this method is overridden by a slightly different method, which encodes not only the numbers of children of the nodes of self, but also their labels. Be careful with using overridden methods, however: If you have (say) a class BalancedTree which inherits from OrderedTree and which encodes balanced trees, and if you have another class BalancedLabelledOrderedTree which inherits both from BalancedOrderedTree and from LabelledOrderedTree, then (depending on the MRO) the default sort_key() method on BalancedLabelledOrderedTree (unless manually overridden) will be taken either from BalancedTree or from LabelledOrderedTree, and in the former case will ignore the labelling!

EXAMPLES:

sage: RT = OrderedTree
sage: RT([[],[[]]]).sort_key()
(2, 0, 1, 0)
sage: RT([[[]],[]]).sort_key()
(2, 1, 0, 0)

to_binary_tree_left_branch()

Return a binary tree of size \(n-1\) (where \(n\) is the size of \(t\), and where \(t\) is self) obtained from \(t\) by the following recursive rule:

• if \(x\) is the left brother of \(y\) in \(t\), then \(x\) becomes the left child of \(y\);

• if \(x\) is the last child of \(y\) in \(t\), then \(x\) becomes the right child of \(y\),

and removing the root of \(t\).

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_left_branch()
[[., .], .]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_left_branch()
[[[., .], [[., .], .]], [[., .], [., .]]]

to_binary_tree_right_branch()

Return a binary tree of size \(n-1\) (where \(n\) is the size of \(t\), and where \(t\) is self) obtained from \(t\) by the following recursive rule:

• if \(x\) is the right brother of \(y\) in \(t\), then`x` becomes the right child of \(y\);

• if \(x\) is the first child of \(y\) in \(t\), then \(x\) becomes the left child of \(y\),

and removing the root of \(t\).

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_right_branch()
[., [., .]]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_right_branch()
[., [[., [., .]], [[., [[., .], .]], .]]]

to_dyck_word()

Return the Dyck path corresponding to self where the maximal height of the Dyck path is the depth of self .

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 0]
sage: T = OrderedTree([[],[[]]])
sage: T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 1, 0, 0]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]

to_parallelogram_polyomino(bijection=None)

Return a polyomino parallelogram.

INPUT:

• bijection – (default: 'Boussicault-Socci') is the name of the bijection to use. Possible values are 'Boussicault-Socci', 'via dyck and Delest-Viennot'.

EXAMPLES:

sage: # needs sage.combinat sage.modules
sage: T = OrderedTree([[[], [[], [[]]]], [], [[[],[]]], [], []])
sage: T.to_parallelogram_polyomino(bijection='Boussicault-Socci')
[[0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
 [1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0]]
sage: T = OrderedTree( [] )
sage: T.to_parallelogram_polyomino()
[[1], [1]]
sage: T = OrderedTree( [[]] )
sage: T.to_parallelogram_polyomino()
[[0, 1], [1, 0]]
sage: T = OrderedTree( [[],[]] )
sage: T.to_parallelogram_polyomino()
[[0, 1, 1], [1, 1, 0]]
sage: T = OrderedTree( [[[]]] )
sage: T.to_parallelogram_polyomino()
[[0, 0, 1], [1, 0, 0]]

to_poset(root_to_leaf=False)

Return the poset obtained by interpreting the tree as a Hasse diagram. The default orientation is from leaves to root but you can pass root_to_leaf=True to obtain the inverse orientation.

INPUT:

• root_to_leaf – boolean, true if the poset orientation should be from root to leaves. It is false by default.

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_poset()
Finite poset containing 1 elements
sage: p = OrderedTree([[[]],[],[]]).to_poset()
sage: p.height(), p.width()                                                 # needs networkx
(3, 3)

If the tree is labelled, we use its labelling to label the poset. Otherwise, we use the poset canonical labelling:

sage: t = OrderedTree([[[]],[],[]]).canonical_labelling().to_poset()
sage: t.height(), t.width()                                                 # needs networkx
(3, 3)

to_undirected_graph()

Return the undirected graph obtained from the tree nodes and edges.

The graph is endowed with an embedding, so that it will be displayed correctly.

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_undirected_graph()
Graph on 1 vertex
sage: t = OrderedTree([[[]],[],[]])
sage: t.to_undirected_graph()
Graph on 5 vertices

If the tree is labelled, we use its labelling to label the graph. This will fail if the labels are not all distinct. Otherwise, we use the graph canonical labelling which means that two different trees can have the same graph.

EXAMPLES:

sage: t = OrderedTree([[[]],[],[]])
sage: t.canonical_labelling().to_undirected_graph()
Graph on 5 vertices

class sage.combinat.ordered_tree.OrderedTrees

Bases: UniqueRepresentation, Parent

Factory for ordered trees

INPUT:

• size – (optional) an integer

OUTPUT:

• the set of all ordered trees (of the given size if specified)

EXAMPLES:

sage: OrderedTrees()
Ordered trees

sage: OrderedTrees(2)
Ordered trees of size 2

Note

this is a factory class whose constructor returns instances of subclasses.

Note

the fact that OrderedTrees is a class instead of a simple callable is an implementation detail. It could be changed in the future and one should not rely on it.

leaf()

Return a leaf tree with self as parent

EXAMPLES:

sage: OrderedTrees().leaf()
[]

class sage.combinat.ordered_tree.OrderedTrees_all

Bases: DisjointUnionEnumeratedSets, OrderedTrees

The set of all ordered trees.

EXAMPLES:

sage: OT = OrderedTrees(); OT
Ordered trees
sage: OT.cardinality()
+Infinity

Element

alias of OrderedTree

labelled_trees()

Return the set of labelled trees associated to self

EXAMPLES:

sage: OrderedTrees().labelled_trees()
Labelled ordered trees

unlabelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: OrderedTrees().unlabelled_trees()
Ordered trees

class sage.combinat.ordered_tree.OrderedTrees_size(size)

Bases: OrderedTrees

The enumerated sets of binary trees of a given size

EXAMPLES:

sage: S = OrderedTrees(3); S
Ordered trees of size 3
sage: S.cardinality()
2
sage: S.list()
[[[], []], [[[]]]]

cardinality()

The cardinality of self

This is a Catalan number.

element_class()

The class of the element of self

EXAMPLES:

sage: from sage.combinat.ordered_tree import OrderedTrees_size, OrderedTrees_all
sage: S = OrderedTrees_size(3)
sage: S.element_class is OrderedTrees().element_class
True
sage: S.first().__class__ == OrderedTrees_all().first().__class__
True

random_element()

Return a random OrderedTree with uniform probability.

This method generates a random DyckWord and then uses a bijection between Dyck words and ordered trees.

EXAMPLES:

sage: OrderedTrees(5).random_element()  # random                            # needs sage.combinat
[[[], []], []]
sage: OrderedTrees(0).random_element()
Traceback (most recent call last):
...
EmptySetError: there are no ordered trees of size 0
sage: OrderedTrees(1).random_element()                                      # needs sage.combinat
[]