AUTHORS:
Bases: sage.combinat.abstract_tree.AbstractLabelledClonableTree, sage.combinat.ordered_tree.OrderedTree
Labelled ordered trees.
A labelled ordered tree is an ordered tree with a label attached at each node.
INPUT:
of trees or object convertible to trees
label – any Sage object default to 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[]]]
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.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
alias of LabelledOrderedTree
Return the cardinality of \(self\).
EXAMPLE:
sage: LabelledOrderedTrees().cardinality()
+Infinity
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[]]
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
Bases: sage.combinat.abstract_tree.AbstractClonableTree, sage.structure.list_clone.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
TESTS:
sage: x1.__hash__() == x2.__hash__()
True
sage: tt1.__hash__() == tt2.__hash__()
True
Trees are usually immutable. However they inherit from sage.structure.list_clone.ClonableList, so that they can be modified using the clone protocol. Let us now see what this means.
Trying to modify a non-mutable tree raises an error:
sage: tt1[1] = tt2
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
Here is the correct way to do it:
sage: with tt2.clone() as tt2:
....: tt2[1] = tt1
sage: tt2
[[], [[], [[], []], [[], []]], [[], []]]
It is also possible to append a child to a tree:
sage: with tt2.clone() as tt3:
....: tt3.append(OrderedTree([]))
sage: tt3
[[], [[], [[], []], [[], []]], [[], []], []]
Or to insert a child in a tree:
sage: with tt2.clone() as tt3:
....: tt3.insert(2, OrderedTree([]))
sage: tt3
[[], [[], [[], []], [[], []]], [], [[], []]]
We check that tt1 is not modified and that everything is correct with respect to equality:
sage: tt1
[[], [[], []], [[], []]]
sage: tt1 == tt2
False
sage: tt1.__hash__() == tt2.__hash__()
False
TESTS:
sage: tt1bis = OrderedTree(tt1)
sage: with tt1.clone() as tt1:
....: tt1[1] = tt1bis
sage: tt1
[[], [[], [[], []], [[], []]], [[], []]]
sage: tt1 == tt2
True
sage: tt1.__hash__() == tt2.__hash__()
True
sage: len(tt1)
3
sage: tt1[2]
[[], []]
sage: tt1[3]
Traceback (most recent call last):
...
IndexError: list index out of range
sage: tt1[1:2]
[[[], [[], []], [[], []]]]
Various tests involving construction, equality and hashing:
sage: OrderedTree() == OrderedTree()
True
sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[],[[]]])
sage: t1 == t2
True
sage: t2 = OrderedTree(t1)
sage: t1 == t2
True
sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[[]],[]])
sage: t1 == t2
False
sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[],[[]]])
sage: t1.__hash__() == t2.__hash__()
True
sage: t2 = OrderedTree([[[]],[]])
sage: t1.__hash__() == t2.__hash__()
False
sage: OrderedTree().__hash__() == OrderedTree([]).__hash__()
True
sage: tt1 = OrderedTree([t1,t2,t1])
sage: tt2 = OrderedTree([t1, [[[]],[]], t1])
sage: tt1.__hash__() == tt2.__hash__()
True
Check that the hash value is correctly updated after modification:
sage: with tt2.clone() as tt2:
....: tt2[1,1] = tt1
sage: tt1.__hash__() == tt2.__hash__()
False
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
Return the symmetric tree of self
EXAMPLES:
sage: T = OrderedTree([[],[[]]])
sage: T.left_right_symmetry()
[[[]], []]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.left_right_symmetry()
[[[[]], []], [[], []], []]
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:
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()
[[[., .], [[., .], .]], [[., .], [., .]]]
TESTS:
sage: T = OrderedTree([[],[]])
sage: T == T.to_binary_tree_left_branch().to_ordered_tree_left_branch()
True
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T == T.to_binary_tree_left_branch().to_ordered_tree_left_branch()
True
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:
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()
[., [[., [., .]], [[., [[., .], .]], .]]]
TESTS:
sage: T = OrderedTree([[],[]])
sage: T == T.to_binary_tree_right_branch().to_ordered_tree_right_branch()
True
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T == T.to_binary_tree_right_branch().to_ordered_tree_right_branch()
True
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()
[1, 0, 1, 0]
sage: T = OrderedTree([[],[[]]])
sage: T.to_dyck_word()
[1, 0, 1, 1, 0, 0]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_dyck_word()
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
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:
EXAMPLES:
sage: t = OrderedTree([])
sage: t.to_poset()
Finite poset containing 1 elements
sage: p = OrderedTree([[[]],[],[]]).to_poset()
sage: p.cover_relations()
[[0, 4], [1, 4], [2, 3], [3, 4]]
sage: p = OrderedTree([[[]],[],[]]).to_poset(root_to_leaf=True)
sage: p.cover_relations()
[[0, 2], [0, 3], [0, 4], [4, 1]]
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()
sage: t
1[2[3[]], 4[], 5[]]
sage: t.to_poset().cover_relations()
[[5, 1], [4, 1], [3, 2], [2, 1]]
Return the undirected graph obtained from the tree nodes and edges.
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. 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
sage: t.canonical_labelling().to_undirected_graph() == t.to_undirected_graph()
False
sage: OrderedTree([[],[]]).to_undirected_graph() == OrderedTree([[[]]]).to_undirected_graph()
True
sage: OrderedTree([[],[],[]]).to_undirected_graph() == OrderedTree([[[[]]]]).to_undirected_graph()
False
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
Factory for ordered trees
INPUT:
OUPUT:
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.
Return a leaf tree with self as parent
EXAMPLES:
sage: OrderedTrees().leaf()
[]
TEST:
sage: (OrderedTrees().leaf() is
....: sage.combinat.ordered_tree.OrderedTrees_all().leaf())
True
Bases: sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets, sage.combinat.ordered_tree.OrderedTrees
The set of all ordered trees.
EXAMPLES:
sage: OT = OrderedTrees(); OT
Ordered trees
sage: OT.cardinality()
+Infinity
alias of OrderedTree
Return the set of unlabelled trees associated to self
EXAMPLES:
sage: OrderedTrees().labelled_trees()
Labelled ordered trees
Return the set of unlabelled trees associated to self
EXAMPLES:
sage: OrderedTrees().unlabelled_trees()
Ordered trees
Bases: sage.combinat.ordered_tree.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()
[[[], []], [[[]]]]
The cardinality of self
This is a Catalan number.
TESTS:
sage: OrderedTrees(0).cardinality()
0
sage: OrderedTrees(1).cardinality()
1
sage: OrderedTrees(6).cardinality()
42
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