Tree

class Tree(list_repr: tuple | list | None = None)[source]

A single non-planar (un)labelled rooted tree, initialised by its list representation. For example, the unlabelled cherry tree has the list representation [[],[]]. Noting that every list corresponds to a node, we can apply a labelling/coloring by setting the last element of the list to be a non-negative integer. For example, [[2], [1], 0] corresponds to the cherry tree, with the root node labelled by 0, the left leaf labelled by 2 and the right leaf labelled by 1. If a label is left out, it will default to 0.

Parameters:: list_repr – The nested list representation of the tree

t1 = kr.Tree([[[]],[]]) # An unlabelled tree
t2 = kr.Tree([[[3],1],[2],0]) # A labelled tree
t3 = kr.Tree([[[3],1],[2]]) # This is the same as t2, since the missing label defaults to 0
kr.display(t1, t2, t3)

__add__(other: int | float | Tree | CommutativeForest | ForestSum) → ForestSum[source]

Adds a tree to a scalar, Tree, Forest or ForestSum.

Parameters:: other – A scalar, Tree, Forest or ForestSum
Return type:: ForestSum

Example usage:

t = 2 + Tree([[]]) + CommutativeForest([Tree([]), Tree([[],[]])])
kr.display(t)

__eq__(other: Tree | CommutativeForest | ForestSum) → bool[source]

Compares the tree with another object and returns true if they represent the same tree, regardless of class type (Tree, Forest or ForestSum) or possible reorderings of the same tree.

Parameters:: other – Tree, Forest or ForestSum
Return type:: bool

Example usage:

print(Tree([[],[]]) == Tree([[],[]]).as_forest())
print(Tree([[],[]]) == Tree([[],[]]).as_forest_sum())
print(Tree([[[]],[]]) == Tree([[],[[]]]))

True
True
True

__matmul__(other: int | float | Tree | CommutativeForest | ForestSum) → TensorProductSum[source]

Returns the tensor product of a Tree and a scalar, Tree, Forest or ForestSum.

Parameters:: other (int | float | Tree | Forest | ForestSum) – Other
Returns:: Tensor product
Return type:: TensorProductSum

Example usage:

t = Tree([]) @ (Tree([[]]) + Tree([]) * Tree([[],[]]))
kr.display(t)

Multiplies a tree by a:

scalar, returning a ForestSum
Tree, returning a Forest,
Forest, returning a Forest,
ForestSum, returning a ForestSum.

Parameters:: other – A scalar, Tree, Forest or ForestSum

Example usage:

t = 2 * Tree([[]]) * CommutativeForest([Tree([]), Tree([[],[]])])
kr.display(t)

__next__() → Tree[source]

Generates the next tree with respect to the lexicographic order. If the tree is labelled, the labelling will be ignored.

Returns:: Next tree
Return type:: Tree

Example usage:

t = Tree([[],[]])
kr.display(t, '→', next(t))

__pow__(n: int) → CommutativeForest[source]

Returns the \(n^{th}\) power of a tree for a positive integer \(n\), given by a forest with \(n\) copies of the tree.

Parameters:: n – Exponent, a positive integer

Example usage:

t = Tree([[]]) ** 3
kr.display(t)

alpha() → int[source]

For a tree \(t\) with \(n\) nodes, computes the number of distinct ways of labelling the nodes of the tree with symbols \(\{1, 2, \ldots, n\}\), such that:

Each vertex receives one and only one label,
Labellings that are equivalent under the symmetry group are counted only once,
If \((i,j)\) is a labelled edge, then \(i<j\).

This number is typically denoted by \(\alpha(t)\) and given by

\[\alpha(t) = \frac{n!}{t! \sigma(t)}\]

Returns:: \(\alpha(t)\)
Return type:: int

Example usage:

t = Tree([[[]],[]])
print(t.alpha())

as_forest() → CommutativeForest[source]

Returns the tree t as a forest. Equivalent to CommutativeForest([t]).

Returns:: Tree as a forest
Return type:: CommutativeForest

Example usage:

>>> Tree([[],[[]]]).as_forest()

as_forest_sum() → ForestSum[source]

Returns the tree t as a forest sum. Equivalent to ForestSum([CommutativeForest([t])]).

Returns:: Tree as a forest sum
Return type:: ForestSum

Example usage:

>>> Tree([[],[[]]]).as_forest_sum()

beta() → int[source]

For a tree \(t\) with \(n\) nodes, computes the number of distinct ways of labelling the nodes of the tree with symbols \(\{1, 2, \ldots, n\}\), such that:

Each vertex receives one and only one label,
Labellings that are equivalent under the symmetry group are counted only once.

This number is typically denoted by \(\beta(t)\) and given by

\[\beta(t) = \frac{n!}{\sigma(t)}\]

Returns:: \(\beta(t)\)
Return type:: int

Example usage:

t = Tree([[[]],[]])
print(t.beta())

color_sequence()[source]: Returns the color (label) sequence of the tree in pre-order.

colors() → int[source]

Returns the number of colors/labels in a labelled tree. Since the labels are indexed starting from 0, this is equivalent to one more than the maximum label.

Returns:: Number of colors
Return type:: int

Example usage:

print(Tree([]).colors())
print(Tree([0]).colors())
print(Tree([[9],1]).colors())

1
1
10

density() → float[source]

Density of the tree, \(t! / |t|!\).

Returns:: Density, \(t! / |t|!\)
Return type:: float

Example usage:

t = Tree([[[]],[]])
print(t.density())

0.3333333333333333

equals(other_tree)[source]: Two trees are equal iff their sorted (canonical) list representations match.

factorial() → int[source]

Compute the tree factorial, \(t!\)

Returns:: Tree factorial, \(t!\)
Return type:: int

Example usage:

t = Tree([[[]],[]])
print(t.factorial())

height() → int[source]

Returns the height of a tree, given by the number of nodes in the longest walk from the root to a leaf.

Returns:: Height
Return type:: int

Example usage:

t = Tree([[[]],[]])
print(t.height())

level_sequence() → list[source]

Returns the level sequence of the tree, defined as the list \({\ell_1, \ell_2, \cdots, \ell_n}\), where \(\ell_i\) is the level of the \(i^{th}\) node when the nodes are ordered lexicographically.

Returns:: Level sequence
Return type:: list

Example usage:

t = Tree([[[]],[]])
print(t.level_sequence())

[0, 1, 2, 1]

nodes() → int[source]

Returns the number of nodes in a tree, \(|t|\)

Returns:: Number of nodes, \(|t|\)
Return type:: int

Example usage:

t = Tree([[[]],[]])
print(t.nodes())

sigma() → int[source]

Computes the symmetry factor \(\sigma(t)\), the order of the symmetric group of the tree. For a tree \(t = [t_1^{m_1} t_2^{m_2} \cdots t_k^{m_k}]\), the symmetry factor satisfies the recursion

\[\sigma(t) = \prod_{i=1}^k m_i! \sigma(t_i)^{m_i}.\]

Returns:: Symmetry factor, \(\sigma(t)\)
Return type:: int

Example usage:

t = Tree([[[]],[]])
print(t.sigma())

sign() → ForestSum[source]

Returns the tree signed by the number of nodes, \((-1)^{|t|} t\).

Returns:: Signed tree, \((-1)^{|t|} t\)
Return type:: ForestSum

sorted() → Tree[source]

Returns the sorted tree, where the heaviest branches are rotated to the left.

Returns:: Sorted tree
Return type:: Tree

Example usage:

t = Tree([[],[[]]])
kr.display(t, '→', t.sorted())

sorted_list_repr() → list[source]

Returns the list representation of the sorted tree, where the heaviest branches are rotated to the left.

Returns:: Sorted list representation
Return type:: list

Example usage:

t = Tree([[],[[]]])
print(t.sorted_list_repr())

(((0,), 0), (0,), 0)

unjoin() → CommutativeForest[source]

For a tree \(t = [t_1, t_2, ..., t_k]\), returns the forest \(t_1 t_2 \cdots t_k\). In [CK99], this map is denoted by \(B_-\).

Returns:: \(t_1 t_2 \cdots t_k\)
Return type:: CommutativeForest

Example usage:

t = Tree([[[]],[]])
kr.display(t, '→', t.unjoin())

unlabelled()[source]

Returns the unlabelled version of the tree.

Example usage:

t = Tree([[[3],1],[2],0])
kr.display(t, '→', t.unlabelled())