Generic Tree

Tree data structure

TreeNode is a generic class which can carry arbitrary python objects. It comes with basic methods to set parent and children. A method map allows to apply functions recursively on the tree in a generic manner.

orion.core.utils.tree.DepthFirstTraversal(tree_node: NodeType) Iterable[NodeType][source]

Iterate on a tree in a post-order traversal fashion

orion.core.utils.tree.PreOrderTraversal(tree_node: NodeType) Iterator[NodeType][source]

Iterate on a tree in a pre-order traversal fashion

class orion.core.utils.tree.TreeNode(item: T, parent: Self | None = None, children: Sequence[Self] = ())[source]

Tree node data structure

Nodes have an attribute item to carry arbitrary information. A node may only have one parent and can have as many children as desired.

Parents can be set at initialization or via node.set_parent. Setting a parent automatically set the current node as the child of the parent.

Children can be set at initialization or via node.add_children. Setting children automatically set their parent as the current node.

Tree of nodes are iterable, by default with preorder traversal.

Examples

 1a = TreeNode("a")
 2b = TreeNode("b", a)
 3c = TreeNode("c", a)
 4d = TreeNode("d", a)
 5e = TreeNode("e", a)
 6
 7f = TreeNode("f", b)
 8g = TreeNode("g", b)
 9
10h = TreeNode("h", e)
11
12# Gives this tree
13# a
14# |   \  \   \
15# b    c  d   e
16# | \         |
17# f  g        h
18
19g.set_parent(e)
20
21# Gives this tree
22# a
23# |  \  \   \
24# b   c  d   e
25# |          | \
26# f          h g
27
28c.add_children(h, g)
29
30# Gives this tree
31# a
32# |  \    \   \
33# b   c    d   e
34# |   | \
35# f   h  g
36
37a.drop_children(c)
38
39# Gives this tree
40# a
41# |  \   \
42# b   d   e
43# |
44# f
Attributes
item: T

Can be anything

parent: None or instance of `orion.core.utils.tree.TreeNode`

The parent of the current node, None if the current node is the root.

children: None or list of instances of `orion.core.utils.tree.TreeNode`

The children of the current node.

root: instance of `orion.core.utils.tree.TreeNode`

The top node of the current tree. The root node returns itself.

Methods

add_children(*nodes)

Add children to the current node

drop_children(*nodes)

Drop the children of the node, do nothing if no parent

drop_parent()

Drop the parent of the node, do nothing if no parent

get_nodes_at_depth(depth)

Returns a list of nodes at the corresponding depth.

map(function, node)

Apply a function recursively on the tree

set_parent(node)

Set the parent of the node

add_children(*nodes: Self) None[source]

Add children to the current node

Note that added children will have their parent set to the current node as well.

property children: list[Self]

Get children of the node, empty list if no children

drop_children(*nodes: Self) None[source]

Drop the children of the node, do nothing if no parent

If no nodes are passed, the method will drop all the children of the current node.

Note that the parent of the given node will be removed as well

Raises
ValueError

If one of the given nodes is not a children of the current node.

drop_parent() None[source]

Drop the parent of the node, do nothing if no parent

Note that the node will be removed from the children of the parent as well

get_nodes_at_depth(depth: int) list[Self][source]

Returns a list of nodes at the corresponding depth.

Depth is relative to current node. To get nodes at a depth relative to the root, use node.root.get_nodes_at_depth(depth).

property item: T

Get item of the node which may contain arbitrary objects

property leafs: list[Self]

Get the leafs of the tree

map(function: Callable, node: TreeNode[T] | Sequence[TreeNode[T]] | None) TreeNode[source]

Apply a function recursively on the tree

The function can be applied upwards on parents or downwards on children. The direction is defined by passing self.parent or self.children as the node argument.

Parameters
functioncallable

Callable object to which will be passed the current node plus the parent node or the children nodes, depending on the direction of function application. If map on parents, callable(self, rval_parent_node) If map on children, callable(self, rval_children_nodes). Note that the callable object is expected to return an object which will be set as the current node’s item (in the resulting tree), and the parent node or the children nodes depending on the direction of function application.

node: None, `orion.core.evc.TreeNode` or list

Can be either None: function is applied on current node only self.parent: function is applied recursively climbing up the tree until the root self.children: function is applied recursively going down the tree until the leafs

Examples

 1# Tree structure
 2# a
 3# |   \  \   \
 4# b    c  d   e
 5# | \         |
 6# f  g        h
 7#
 8
 9root = TreeNode(1)
10b = TreeNode(1, root)
11TreeNode(1, root)
12TreeNode(1, root)
13e = TreeNode(1, root)
14
15f = TreeNode(1, b)
16TreeNode(1, b)
17
18h = TreeNode(1, e)
19
20def increment(node, children):
21    for child in TreeNode(0, None, children):
22        child.item += 1
23
24    return node.item + 1, children
25
26# Should return
27#
28# 2
29# |   \  \   \
30# 3    3  3   3
31# | \         |
32# 4  4        4
33
34rval = root.map(increment, root.children)
35assert [node.item for node in rval] == [2, 3, 4, 4, 3, 3, 3, 4]
36
37def increment_parent(node, parent):
38    if parent is not None:
39        for parent in parent.root:
40            parent.item += 1
41
42    return node.item + 1, parent
43
44# Should return
45#
46# 4
47# |
48# 3
49# |
50# 2
51
52rval = f.map(increment_parent, f.parent)
53assert [node.item for node in rval.root] == [4, 3, 2]
54
55rval = h.map(increment_parent, h.parent)
56assert [node.item for node in rval.root] == [4, 3, 2]
property node_depth: int

The depth of the node in the tree with respect to the root node.

property parent: Self | None

Get parent of the node, None if no parent

property root: TreeNode[T]

Get the root of the tree

Root node returns itself

set_parent(node: Self) None[source]

Set the parent of the node

Note that setting a new parent will have the effect of dropping the previous parent, hence dropping this current node from the previous parent’s children list.

orion.core.utils.tree.flattened(trials_tree: TreeNode[T]) list[T][source]

Get a list of the tree items in pre-order traversal