Abstract Recursive Trees¶

The purpose of this class is to help implement trees with a specific structure on the children of each node. For instance, one could want to define a tree in which each node sees its children as linearly (see the Ordered Trees module) or cyclically ordered.

Tree structures

Conceptually, one can define a tree structure from any object that can contain others. Indeed, a list can contain lists which contain lists which contain lists, and thus define a tree ... The same can be done with sets, or any kind of iterable objects.

While any iterable is sufficient to encode trees, it can prove useful to have other methods available like isomorphism tests (see next section), conversions to DiGraphs objects (see as_digraph()) or computation of the number of automorphisms constrained by the structure on children. Providing such methods is the whole purpose of the AbstractTree class.

As a result, the AbstractTree class is not meant to be instantiated, but extended. It is expected that classes extending this one may also inherit from classes representing iterables, for instance ClonableArray or ClonableList

Constrained Trees

The tree built from a specific container will reflect the properties of the container. Indeed, if A is an iterable class whose elements are linearly ordered, a class B extending both of AbstractTree and A will be such that the children of a node will be linearly ordered. If A behaves like a set (i.e. if there is no order on the elements it contains), then two trees will be considered as equal if one can be obtained from the other through permutations between the children of a same node (see next section).

Paths and ID

It is expected that each element of a set of children should be identified by its index in the container. This way, any node of the tree can be identified by a word describing a path from the root node.

Canonical labellings

Equality between instances of classes extending both of AbstractTree and A is entirely defined by the equality defined on the elements of A. A canonical labelling of such a tree however, should be such that two trees a and b satisfying a == b should have the same canonical labellings. On the other hand, the canonical labellings of trees a and b satisfying a != b are expected to be different.

For this reason, the values returned by the canonical_labelling method heavily depend on the data structure used for a node’s children and should be overridden by most of the classes extending AbstractTree if it is incoherent with the data structure.

Authors

• Florent Hivert (2010-2011): initial revision
• Frédéric Chapoton (2011): contributed some methods
class sage.combinat.abstract_tree.AbstractClonableTree

Abstract Clonable Tree

An abstract class for trees with clone protocol (see list_clone). It is expected that classes extending this one may also inherit from classes like ClonableArray or ClonableList depending wether one wants to build trees where adding a child is allowed.

Note

Due to the limitation of Cython inheritance, one cannot inherit here from ClonableElement, because it would prevent us to inherit later from ClonableArray or ClonableList.

How should this class be extended ?

A class extending AbstractTree should the following assumptions:

check()

Check that self is a correct tree

This method does nothing. It is implemented here because many extensions of AbstractTree also extend sage.structure.list_clone.ClonableElement, which requires it.

It should be overriden in subclass in order to check that the invariant of the kind of tree holds (eg: two children for binary trees).

EXAMPLES:

sage: OrderedTree([[],[[]]]).check()
sage: BinaryTree([[],[[],[]]]).check()

class sage.combinat.abstract_tree.AbstractLabelledClonableTree(parent, children, label=None, check=True)

Abstract Labelled Clonable Tree

This class takes care of modification for the label by the clone protocol.

Note

Due to the limitation of Cython inheritance, one cannot inherit here from ClonableArray, because it would prevent us to inherit later from ClonableList.

map_labels(f)

Applies the function $$f$$ to the labels of self

This method returns a copy of self on which the function $$f$$ has been applied on all labels (a label $$x$$ is replaced by $$f(x)$$).

EXAMPLES:

sage: LT = LabelledOrderedTree
sage: t = LT([LT([],label=1),LT([],label=7)],label=3); t
3[1[], 7[]]
sage: t.map_labels(lambda z:z+1)
4[2[], 8[]]

sage: LBT = LabelledBinaryTree
sage: bt = LBT([LBT([],label=1),LBT([],label=4)],label=2); bt
2[1[., .], 4[., .]]
sage: bt.map_labels(lambda z:z+1)
3[2[., .], 5[., .]]

set_label(path, label)

Changes the label of subtree indexed by path to label

INPUT:

• pathNone (default) or a path (list or tuple of children

index in the tree)

• label – any sage object

OUPUT: Nothing, self is modified in place

Note

self must be in a mutable state. See sage.structure.list_clone for more details about mutability.

EXAMPLES:

sage: t = LabelledOrderedTree([[],[[],[]]])
sage: t.set_label((0,), 4)
Traceback (most recent call last):
...
sage: with t.clone() as t:
...    t.set_label((0,), 4)
sage: t
None[4[], None[None[], None[]]]
sage: with t.clone() as t:
...    t.set_label((1,0), label = 42)
sage: t
None[4[], None[42[], None[]]]


Todo

Do we want to implement the following syntactic sugar:

with t.clone() as tt:
tt.labels[1,2] = 3 ?
set_root_label(label)

Sets the label of the root of self

INPUT: label – any Sage object

OUPUT: None, self is modified in place

Note

self must be in a mutable state. See sage.structure.list_clone for more details about mutability.

EXAMPLES:

sage: t = LabelledOrderedTree([[],[[],[]]])
sage: t.set_root_label(3)
Traceback (most recent call last):
...
sage: with t.clone() as t:
...    t.set_root_label(3)
sage: t.label()
3
sage: t
3[None[], None[None[], None[]]]


This also works for binary trees:

sage: bt = LabelledBinaryTree([[],[]])
sage: bt.set_root_label(3)
Traceback (most recent call last):
...
sage: with bt.clone() as bt:
...    bt.set_root_label(3)
sage: bt.label()
3
sage: bt
3[None[., .], None[., .]]


TESTS:

sage: with t.clone() as t:
...    t[0] = LabelledOrderedTree(t[0], label = 4)
sage: t
3[4[], None[None[], None[]]]
sage: with t.clone() as t:
...    t[1,0] = LabelledOrderedTree(t[1,0], label = 42)
sage: t
3[4[], None[42[], None[]]]

class sage.combinat.abstract_tree.AbstractLabelledTree(parent, children, label=None, check=True)

Abstract Labelled Tree

Typically a class for labelled tree is contructed by inheriting from a class for unlabelled trees and AbstractLabelledTree

How should this class be extended ?

A class extending AbstractLabelledTree should respect the following assumptions:

• For a labelled tree T the call T.parent().unlabelled_trees() should return a parent for labelled trees of the same kind: for example,
• if T is a binary labelled tree, T.parent() is LabelledBinaryTrees() and T.parent().unlabelled_trees() is BinaryTrees()
• if T is an ordered labelled tree, T.parent() is LabelledOrderedTrees() and T.parent().unlabelled_trees() is OrderedTrees()
• In the same vein, the class of T should contain an attribute _Unlabelled which should be the class for the corresponding unlabelled trees.

AbstractTree

as_digraph()

Returns a directed graph version of self.

Warning

At this time, the output makes sense only if self is a labelled binary tree with no repeated labels and no None labels.

EXAMPLES:

sage: LT = LabelledOrderedTrees()
sage: t1 = LT([LT([],label=6),LT([],label=1)],label=9)
sage: t1.as_digraph()
Digraph on 3 vertices

sage: t = BinaryTree([[None, None],[[],None]]);
sage: lt = t.canonical_labelling()
sage: lt.as_digraph()
Digraph on 4 vertices

label(path=None)

Returns the label of self

INPUT:

• path – None (default) or a path (list or tuple of children index

in the tree)

OUTPUT: the label of the subtree indexed by path

EXAMPLES:

sage: t = LabelledOrderedTree([[],[]], label = 3)
sage: t.label()
3
sage: t[0].label()
sage: t = LabelledOrderedTree([LabelledOrderedTree([], 5),[]], label = 3)
sage: t.label()
3
sage: t[0].label()
5
sage: t[1].label()
sage: t.label([0])
5

labels()

Returns the list of labels of self

EXAMPLES:

sage: LT = LabelledOrderedTree
sage: t = LT([LT([],label='b'),LT([],label='c')],label='a')
sage: t.labels()
['a', 'b', 'c']

sage: LBT = LabelledBinaryTree
sage: LBT([LBT([],label=1),LBT([],label=4)],label=2).labels()
[2, 1, 4]

leaf_labels()

Returns the list of labels of the leaves of self

EXAMPLES:

sage: LT = LabelledOrderedTree
sage: t = LT([LT([],label='b'),LT([],label='c')],label='a')
sage: t.leaf_labels()
['b', 'c']

sage: LBT = LabelledBinaryTree
sage: bt = LBT([LBT([],label='b'),LBT([],label='c')],label='a')
sage: bt.leaf_labels()
['b', 'c']
sage: LBT([], label='1').leaf_labels()
['1']
sage: LBT(None).leaf_labels()
[]

shape()

Returns the unlabelled tree associated to self

EXAMPLES:

sage: t = LabelledOrderedTree([[],[[]]], label = 25).shape(); t
[[], [[]]]

sage: LabelledBinaryTree([[],[[],[]]], label = 25).shape()
[[., .], [[., .], [., .]]]


TESTS:

sage: t.parent()
Ordered trees
sage: type(t)
<class 'sage.combinat.ordered_tree.OrderedTrees_all_with_category.element_class'>

class sage.combinat.abstract_tree.AbstractTree

Bases: object

Abstract Tree

There is no data structure defined here, as this class is meant to be extended, not instantiated.

How should this class be extended ?

A class extending AbstractTree should respect several assumptions:

• For a tree T, the call iter(T) should return an iterator on the children of the root T.
• The canonical_labelling method should return the same value for trees that are considered equal (see the “canonical labellings” section in the documentation of the AbstractTree module).
• For a tree T the call T.parent().labelled_trees() should return a parent for labelled trees of the same kind: for example,
• if T is a binary tree, T.parent() is BinaryTrees() and T.parent().labelled_trees() is LabelledBinaryTrees()
• if T is an ordered tree, T.parent() is OrderedTrees() and T.parent().labelled_trees() is LabelledOrderedTrees()

TESTS:

sage: TestSuite(OrderedTree()).run()
sage: TestSuite(BinaryTree()).run()

canonical_labelling(shift=1)

Returns a labelled version of self

The actual canonical labelling is currently unspecified. However, it is guaranteed to have labels in $$1...n$$ where $$n$$ is the number of nodes of the tree. Moreover, two (unlabelled) trees compare as equal if and only if their canonical labelled trees compare as equal.

EXAMPLES:

sage: t = OrderedTree([[], [[], [[], []], [[], []]], [[], []]])
sage: t.canonical_labelling()
1[2[], 3[4[], 5[6[], 7[]], 8[9[], 10[]]], 11[12[], 13[]]]

sage: BinaryTree([]).canonical_labelling()
1[., .]
sage: BinaryTree([[],[[],[]]]).canonical_labelling()
2[1[., .], 4[3[., .], 5[., .]]]


TESTS:

sage: BinaryTree().canonical_labelling()
.

depth()

The depth of self

EXAMPLES:

sage: OrderedTree().depth()
1
sage: OrderedTree([]).depth()
1
sage: OrderedTree([[],[]]).depth()
2
sage: OrderedTree([[],[[]]]).depth()
3
sage: OrderedTree([[], [[], [[], []], [[], []]], [[], []]]).depth()
4

sage: BinaryTree().depth()
0
sage: BinaryTree([[],[[],[]]]).depth()
3

node_number()

The number of nodes of self

EXAMPLES:

sage: OrderedTree().node_number()
1
sage: OrderedTree([]).node_number()
1
sage: OrderedTree([[],[]]).node_number()
3
sage: OrderedTree([[],[[]]]).node_number()
4
sage: OrderedTree([[], [[], [[], []], [[], []]], [[], []]]).node_number()
13


EXAMPLE:

sage: BinaryTree(None).node_number()
0
sage: BinaryTree([]).node_number()
1
sage: BinaryTree([[], None]).node_number()
2
sage: BinaryTree([[None, [[], []]], None]).node_number()
5

paths()

Returns a generator for all paths to nodes of self

OUTPUT:

This method returns a list of sequences of integers. Each of these sequences represents a path from the root node to another one : $$(1, 3, 2, 5, 3)$$ represents the node obtained by chosing the 1st children of the root node (in the ordering returned by iter), then the 3rd of its children, then the 2nd of this element, etc.

The root element is represented by the empty tuple ().

EXAMPLES:

sage: list(OrderedTree([]).paths())
[()]
sage: list(OrderedTree([[],[[]]]).paths())
[(), (0,), (1,), (1, 0)]

sage: list(BinaryTree([[],[[],[]]]).paths())
[(), (0,), (1,), (1, 0), (1, 1)]


TESTS:

sage: t = OrderedTree([[], [[], [[], []], [[], []]], [[], []]])
sage: t.node_number() == len(list(t.paths()))
True
sage: list(BinaryTree().paths())
[]
sage: bt = BinaryTree([[],[[],[]]])
sage: bt.node_number() == len(list(bt.paths()))
True

subtrees()

Returns a generator for all subtrees of self

The number of subtrees of a tree is its number of elements.

EXAMPLES:

sage: list(OrderedTree([]).subtrees())
[[]]
sage: list(OrderedTree([[],[[]]]).subtrees())
[[[], [[]]], [], [[]], []]

sage: list(BinaryTree([[],[[],[]]]).subtrees())
[[[., .], [[., .], [., .]]], [., .], [[., .], [., .]], [., .], [., .]]


TESTS:

sage: t = OrderedTree([[], [[], [[], []], [[], []]], [[], []]])
sage: t.node_number() == len(list(t.subtrees()))
True
sage: list(BinaryTree().subtrees())
[]
sage: bt = BinaryTree([[],[[],[]]])
sage: bt.node_number() == len(list(bt.subtrees()))
True

to_hexacode()

Transform a tree into an hexadecimal string.

The definition of the hexacode is recursive. The first letter is the valence of the root as an hexadecimal (up to 15), followed by the concatenation of the hexacodes of the subtrees.

This method only works for trees where every vertex has valency at most 15.

See from_hexacode() for the reverse transformation.

EXAMPLES:

sage: from sage.combinat.abstract_tree import from_hexacode
sage: LT = LabelledOrderedTrees()
sage: from_hexacode('2010', LT).to_hexacode()
'2010'
sage: LT.an_element().to_hexacode()
'3020010'
sage: t = from_hexacode('a0000000000000000', LT)
sage: t.to_hexacode()
'a0000000000'

sage: OrderedTrees(6).an_element().to_hexacode()
'500000'


TESTS:

sage: one = LT([], label='@')
sage: LT([one for _ in range(15)], label='@').to_hexacode()
'f000000000000000'
sage: LT([one for _ in range(16)], label='@').to_hexacode()
Traceback (most recent call last):
...
ValueError: the width of the tree is too large

tree_factorial()

Returns the tree-factorial of self

Definition:

The tree-factorial $$T!$$ of a tree $$T$$ is the product $$\prod_{v\in T}\#\mbox{children}(v)$$.

EXAMPLES:

sage: LT = LabelledOrderedTrees()
sage: t = LT([LT([],label=6),LT([],label=1)],label=9)
sage: t.tree_factorial()
3

sage: BinaryTree([[],[[],[]]]).tree_factorial()
15


TESTS:

sage: BinaryTree().tree_factorial()
1

sage.combinat.abstract_tree.from_hexacode(ch, parent=None, label='@')

Transform an hexadecimal string into a tree.

INPUT:

• ch – an hexadecimal string
• parent – kind of trees to be produced. If None, this will be LabelledOrderedTrees
• label – a label (default: '@') to be used for every vertex of the tree

See AbstractTree.to_hexacode() for the description of the encoding

See _from_hexacode_aux() for the actual code

EXAMPLES:

sage: from sage.combinat.abstract_tree import from_hexacode
sage: from_hexacode('12000', LabelledOrderedTrees())
@[@[@[], @[]]]

sage: from_hexacode('1200', LabelledOrderedTrees())
@[@[@[], @[]]]


It can happen that only a prefix of the word is used:

sage: from_hexacode('a'+14*'0', LabelledOrderedTrees())
@[@[], @[], @[], @[], @[], @[], @[], @[], @[], @[]]


One can choose the label:

sage: from_hexacode('1200', LabelledOrderedTrees(), label='o')
o[o[o[], o[]]]


One can also create other kinds of trees:

sage: from_hexacode('1200', OrderedTrees())
[[[], []]]


Set Partitions

Next topic

Ordered Rooted Trees