Generic Tree¶
Tree data structure for the experiment version control system¶
Tree data structure for the experiment version control system
Experiment version control requires building trees of the experiments so that we can fetch trials from one experiment to another or navigate from one experiment to another to visualise different statistics.
TreeNode and tree iterators support the tree data structure of the experiment version control. 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.
-
class
orion.core.evc.tree.
DepthFirstTraversal
(tree_node)[source]¶ Iterate on a tree in a pre-order traversal fashion
Attributes: - stack: list of `orion.core.evc.tree.TreeNode`
Nodes logged during iteration
- seen: set of `orion.core.evc.tree.TreeNode`
Nodes which have been returned during iteration
-
class
orion.core.evc.tree.
PreOrderTraversal
(tree_node)[source]¶ Iterate on a tree in a pre-order traversal fashion
Attributes: - stack: list of `orion.core.evc.tree.TreeNode`
Nodes logged during iteration
-
class
orion.core.evc.tree.
TreeNode
(item, parent=None, children=())[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 initialiation or via node.set_parent. Setting a parent automatically set the current node as the child of the parent.
Children can be set at initialiation 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
a = TreeNode("a") b = TreeNode("b", a) c = TreeNode("c", a) d = TreeNode("d", a) e = TreeNode("e", a) f = TreeNode("f", b) g = TreeNode("g", b) h = TreeNode("h", e) # Gives this tree # a # | \ \ \ # b c d e # | \ | # f g h g.set_parent(e) # Gives this tree # a # | \ \ \ # b c d e # | | \ # f h g c.add_children(h, g) # Gives this tree # a # | \ \ \ # b c d e # | | \ # f h g a.drop_children(c) # Gives this tree # a # | \ \ # b d e # | # f
Attributes: - item: object
Can be anything
- parent: None or instance of `orion.core.evc.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.evc.tree.TreeNode`
The children of the curent node.
- root: instance of `orion.core.evc.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 map
(function, node)Apply a function recursively on the tree set_parent
(node)Set the parent of the node -
add_children
(*nodes)[source]¶ Add children to the current node
Note that added children will have their parent set to the current node as well.
-
children
¶ Get children of the node, empty list if no children
-
drop_children
(*nodes)[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
()[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
-
item
¶ Get item of the node which may contain arbitrary objects
-
map
(function, node)[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: - function : callable
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
# Tree structure # a # | \ \ \ # b c d e # | \ | # f g h # root = TreeNode(1) b = TreeNode(1, root) TreeNode(1, root) TreeNode(1, root) e = TreeNode(1, root) f = TreeNode(1, b) TreeNode(1, b) h = TreeNode(1, e) def increment(node, children): for child in TreeNode(0, None, children): child.item += 1 return node.item + 1, children # Should return # # 2 # | \ \ \ # 3 3 3 3 # | \ | # 4 4 4 rval = root.map(increment, root.children) assert [node.item for node in rval] == [2, 3, 4, 4, 3, 3, 3, 4] def increment_parent(node, parent): if parent is not None: for parent in parent.root: parent.item += 1 return node.item + 1, parent # Should return # # 4 # | # 3 # | # 2 rval = f.map(increment_parent, f.parent) assert [node.item for node in rval.root] == [4, 3, 2] rval = h.map(increment_parent, h.parent) assert [node.item for node in rval.root] == [4, 3, 2]
-
parent
¶ Get parent of the node, None if no parent
-
root
¶ Get the root of the tree
Root node returns itself