CommutativeForest

Forest is an alias for CommutativeForest.

class CommutativeForest(tree_list: tuple | list = (), count: Counter = None, hash_: int = None)

A commutative product of trees.

Parameters:

tree_list – A list of trees contained in the forest

Example usage:

t1 = Tree([])
t2 = Tree([[]])
t3 = Tree([[[]],[]])
f = CommutativeForest([t1,t2,t3])
kr.display(f)

__add__(other: int | float | Tree | CommutativeForest | ForestSum) → ForestSum

Adds a forest 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: CommutativeForest | ForestSum) → bool

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

Parameters:

other – Forest or ForestSum

Return type:

bool

Example usage:

t1 = Tree([])
t2 = Tree([[]])
t3 = Tree([[[]],[]])
t4 = Tree([[],[[]]])
print(t1 * t2 == t2 * t1)
print(t1 * t2 == (t1 * t2).as_forest_sum())
print(t1 * t3 == t1 * t4)

True
True
True

__matmul__(other: int | float | Tree | CommutativeForest | ForestSum) → TensorProductSum

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

Parameters:

other (int | float | Tree | Forest | ForestSum) – Other

Returns:

Tensor product

Return type:

TensorProductSum

Example usage:

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

__mul__(other: int | float | Tree | CommutativeForest | ForestSum) → CommutativeForest | ForestSum

Multiplies a forest 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)

__pow__(n: int) → CommutativeForest

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

Parameters:

n – Exponent, a positive integer

Example usage:

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

as_forest_sum() → ForestSum

Returns the forest f as a forest sum. Equivalent to ForestSum([f]).

Returns:

CommutativeForest as a forest sum

Return type:

ForestSum

Example usage:

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

colors() → int

Returns the number of colors/labels in the forest. 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([[9],0]) * Tree([3])).colors())

10

equals(other_forest)

Two forests are equal iff they contain the same trees with the same multiplicities.

factorial() → int

Apply the tree factorial to the forest as a multiplicative map. For a forest \(t_1 t_2 \cdots t_k\), returns \(\prod_{i=1}^k t_i!\).

Returns:

\(\prod_{i=1}^k t_i!\)

Return type:

int

Example usage:

f = Tree([[]]) * Tree([[],[]])
print(f.factorial())

6

join(root_color: int = 0) → Tree

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

Parameters:

root_color (int) – Color to assign to the root (default 0)

Returns:

\([t_1, t_2, \cdots, t_k]\)

Return type:

Tree

Example usage:

f = Tree([]) * Tree([[]])
kr.display(f, '→', f.join())

nodes() → int

For a forest \(t_1 t_2 \cdots t_k\), returns the number of nodes in the forest, \(\sum_{i=1}^k |t_i|\).

Returns:

Number of nodes

Return type:

int

Example usage:

f = Tree([]) * Tree([[]])
print(f.nodes())

3

num_trees() → int

For a forest \(t_1 t_2 \cdots t_k\), returns the number of trees in the forest, \(k\).

Returns:

Number of trees

Return type:

int

Example usage:

f = Tree([]) * Tree([[]])
print(f.num_trees())

2

sign() → ForestSum

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

Returns:

Signed forest, \((-1)^{|f|} f\)

Return type:

ForestSum

Example usage:

f1 = Tree([[]]) * Tree([[],[]])
kr.display(f1.sign())
f2 = Tree([]) * Tree([[],[]])
kr.display(f2.sign())

simplify() → CommutativeForest

Simplify the forest by removing redundant empty trees.

Returns:

self

Return type:

CommutativeForest

Example usage:

f1 = Tree([[],[[]]]) * Tree(None)
f2 = f1.simplify() # Tree([[],[[]]])

singleton_reduced() → CommutativeForest

Removes redundant occurrences of the single-node tree in the forest. If the forest contains a tree with more than one node, removes all occurences of the single-node tree. Otherwise, returns the single-node tree.

Returns:

Singleton-reduced forest

Example usage:

f1 = Tree([]) * Tree([[],[]])
f2 = Tree([]) * Tree([]) * Tree([])
kr.display(f1, '→', f1.singleton_reduced())
kr.display(f2, '→', f2.singleton_reduced())