Tree Generation

Functions for generating rooted trees in lexicographic order, based on the algorithms of [BH80].

Unlabelled Trees

trees_of_order(order: int) → Generator[Tree, None, None][source]

Yields the trees of order \(n\), ordered by the lexicographic order.

Parameters:: order (int) – Order
Yields:: The next tree in lexicographic order, as long as the order of the tree is \(n\).
Return type:: Tree

Example usage:

kr.display(*trees_of_order(5))

trees_up_to_order(order: int) → Generator[Tree, None, None][source]

Yields the trees up to and including order \(n\), ordered by the lexicographic order.

Parameters:: order (int) – Maximum order
Yields:: The next tree in lexicographic order, as long as the order of the tree does not exceed \(n\).
Return type:: Tree

Example usage:

trees = list(trees_up_to_order(5))
for i in range(0, len(trees), 10):
    kr.display(*trees[i:i+10])

Colored Trees

colored_trees_of_order(order: int, d: int)[source]

Yields all distinct colored rooted trees of a given order with d colors.

Each node is decorated with a color from {0, …, d-1}.

Parameters:

order (int) – Number of nodes
d (int) – Number of colors

Yields:

Colored trees

Return type:

Tree

Example usage:

trees = list(colored_trees_of_order(4, 2))
for i in range(0, len(trees), 10):
    kr.display(*trees[i:i+10])

colored_trees_up_to_order(order: int, d: int)[source]

Yields all distinct colored rooted trees up to and including a given order with d colors.

Parameters:

order (int) – Maximum number of nodes
d (int) – Number of colors

Yields:

Colored trees

Return type:

Tree

Example usage:

trees = list(colored_trees_up_to_order(4, 2))
for i in range(0, len(trees), 10):
    kr.display(*trees[i:i+10])

colored_trees(d: int, max_order: int) → list[Tree][source]

Returns all distinct colored rooted trees up to a given order with d colors, starting with the empty tree.

Parameters:

d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

List of colored trees.

Return type:

list[Tree]

Planar Trees

planar_trees_of_order(order: int)[source]

Yields planar rooted trees of fixed order.

Order 0 contains only the empty planar tree.

Example usage:

trees = list(planar_trees_of_order(5))
for i in range(0, len(trees), 10):
    kr.display(*trees[i:i+10])

planar_trees_up_to_order(order: int)[source]

Yields planar rooted trees of all orders from 0 through order.

Example usage:

trees = list(planar_trees_up_to_order(5))
for i in range(0, len(trees), 10):
    kr.display(*trees[i:i+10])

Colored Planar Trees

colored_planar_trees_of_order(order: int, d: int)[source]

Yields all colored planar rooted trees of a given order with d colors.

Each node is decorated with a color from {0, …, d-1}. Planar trees have no symmetry, so every coloring is distinct.

Parameters:

order (int) – Number of nodes
d (int) – Number of colors

Yields:

Colored planar trees

Return type:

PlanarTree

Example usage:

trees = list(colored_planar_trees_of_order(4, 2))
for i in range(0, len(trees), 10):
    kr.display(*trees[i:i+10])

colored_planar_trees_up_to_order(order: int, d: int)[source]

Yields all colored planar rooted trees up to and including a given order with d colors.

Parameters:

order (int) – Maximum number of nodes
d (int) – Number of colors

Yields:

Colored planar trees

Return type:

PlanarTree

Example usage:

trees = list(colored_planar_trees_up_to_order(4, 2))
for i in range(0, len(trees), 10):
    kr.display(*trees[i:i+10])

Ordered Forests

ordered_forests_of_order(order: int)[source]

Yields ordered forests of planar rooted trees with a fixed total order.

Order 0 contains only the empty ordered forest.

ordered_forests_up_to_order(order: int)[source]: Yields ordered forests of planar rooted trees up to a given total order.

Colored Ordered Forests

colored_ordered_forests_of_order(order: int, d: int)[source]

Yields colored ordered forests with a fixed total order and d colors.

Each node is decorated with a color from {0, …, d-1}.

colored_ordered_forests_up_to_order(order: int, d: int)[source]: Yields colored ordered forests up to a given total order with d colors.

colored_ordered_forests(d: int, max_order: int) → list[source]

Returns all colored ordered forests up to a given total order with d colors, starting with the empty ordered forest.

Parameters:

d (int) – Number of colors.
max_order (int) – Maximum total number of nodes.

Returns:

List of colored ordered forests.

Return type:

list[OrderedForest]

Indexing

colored_tree_to_idx(tree: Tree, d: int, max_order: int) → int[source]

Returns the index of a colored tree in the canonical enumeration.

Index 0 is the empty tree. Non-empty trees are enumerated by order, then by shape, then by coloring.

Parameters:

tree (Tree) – A colored rooted tree.
d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

Index in the enumeration.

Return type:

int

idx_to_colored_tree(idx: int, d: int, max_order: int) → Tree[source]

Returns the colored tree at a given index in the canonical enumeration.

Parameters:

idx (int) – Index (0 = empty tree).
d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

The colored tree at the given index.

Return type:

Tree

colored_planar_tree_to_idx(tree, d: int, max_order: int) → int[source]

Returns the index of a colored planar tree in the canonical enumeration.

Planar analogue of colored_tree_to_idx(). Index 0 is the empty tree; non-empty trees are enumerated in the order emitted by colored_planar_trees_up_to_order().

Parameters:

tree (PlanarTree) – A colored planar rooted tree.
d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

Index in the enumeration.

Return type:

int

idx_to_colored_planar_tree(idx: int, d: int, max_order: int)[source]

Returns the colored planar tree at a given index in the canonical enumeration.

Planar analogue of idx_to_colored_tree(). Index 0 is the empty planar tree.

Parameters:

idx (int) – Index (0 = empty planar tree).
d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

The colored planar tree at the given index.

Return type:

PlanarTree

colored_ordered_forest_to_idx(forest, d: int, max_order: int) → int[source]

Returns the index of a colored ordered forest in the canonical enumeration.

Parameters:

forest (OrderedForest) – A colored ordered forest.
d (int) – Number of colors.
max_order (int) – Maximum total number of nodes.

Returns:

Index in the enumeration.

Return type:

int

idx_to_colored_ordered_forest(idx: int, d: int, max_order: int)[source]

Returns the colored ordered forest at a given index in the canonical enumeration.

Parameters:

idx (int) – Index, with 0 the empty ordered forest.
d (int) – Number of colors.
max_order (int) – Maximum total number of nodes.

Returns:

The colored ordered forest at the given index.

Return type:

OrderedForest

Canonical / Recursive Permutations

canonical_to_recursive_permutation(d: int, max_order: int)[source]

Compute the permutation mapping canonical tree indices to recursive tree indices.

perm[i] = j means the tree at canonical position i is at recursive position j. Both are 0-indexed and exclude the empty tree.

Parameters:

d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

Permutation array of shape (num_trees,).

Return type:

numpy.ndarray

recursive_to_canonical_permutation(d: int, max_order: int)[source]

Compute the permutation mapping recursive tree indices to canonical tree indices.

Inverse of canonical_to_recursive_permutation().

Parameters:

d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

Inverse permutation array of shape (num_trees,).

Return type:

numpy.ndarray

planar_canonical_to_recursive_permutation(d: int, max_order: int)[source]

Compute the permutation mapping canonical planar-tree indices to recursive planar-tree indices.

perm[i] = j means the planar tree at canonical position i is at recursive position j. Both are 0-indexed and exclude the empty tree. The canonical ordering is the one emitted by colored_planar_trees_up_to_order(); the recursive ordering matches the bottom-up planar enumeration used internally by pySigLib.

Parameters:

d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

Permutation array of shape (num_trees,).

Return type:

numpy.ndarray

planar_recursive_to_canonical_permutation(d: int, max_order: int)[source]

Compute the permutation mapping recursive planar-tree indices to canonical planar-tree indices.

Inverse of planar_canonical_to_recursive_permutation().

Parameters:

d (int) – Number of colors (path dimension).
max_order (int) – Maximum number of nodes.

Returns:

Inverse permutation array of shape (num_trees,).

Return type:

numpy.ndarray