I would like to build a tree similar to the one below.
However, it appears that the children of each node are not being set correctly and I am unsure why.
For background, I am trying to implement the Boolean 6-Multiplexer Problem using Genetic Programming (GP). A Function is an operator that would have its children as input. For example, IF represents the operation: if children[0], return children[1], else return children[2]. A Terminal is basically a leaf node of the tree, which has a value and does not have children.
class Node:
def __init__(self, val: int = None, children: "list[Node]" = []):
self.val = val
self.children = children
def add_child(self, node):
self.children.append(node)
def __str__(self, level=0) -> str:
ret = "\t" * level + self.__repr__() + f"({self.val})" + "\n"
for child in self.children:
ret += child.__str__(level + 1)
return ret
def required_children_count(self) -> int:
return 0
def eval(self) -> int:
pass
class Terminal(Node):
def __repr__(self):
return "Terminal"
def required_children_count(self):
return 0
def eval(self):
return self.val
class Function(Node):
pass
class AND(Function):
def __repr__(self):
return "AND"
def required_children_count(self):
return 2
def eval(self):
return self.children[0].eval() and self.children[1].eval()
class OR(Function):
def __repr__(self):
return "OR"
def required_children_count(self):
return 2
def eval(self):
return self.children[0].eval() or self.children[1].eval()
class NOT(Function):
def __repr__(self):
return "NOT"
def required_children_count(self):
return 1
def eval(self):
return not self.children[0].eval()
class IF(Function):
def __repr__(self):
return "IF"
def required_children_count(self):
return 3
def eval(self):
return (
self.children[1].eval()
if self.children[0].eval()
else self.children[2].eval()
)
class GP:
def __init__(
self,
terminals: "list[Type[Terminal]]" = [], # TODO: figure out this struct
functions: "list[Type[Function]]" = [],
solutions={},
pop_size=100,
pm=0.05,
pc=0.4,
max_depth=3,
):
self.pop_size = pop_size
self.terminals = terminals
self.functions = functions
self.population = []
self.max_depth = max_depth
def generate_full_tree_helper(self, node: Node, depth=0):
for i in range(node.required_children_count()):
if depth == self.max_depth:
node.children.append(Terminal(4))
else:
new_node = random.choice(self.functions)()
self.generate_full_tree_helper(new_node, depth + 1)
node.add_child(new_node)
print(
f"depth: {depth}, node: {node.__repr__()}, children: {len(node.children)}"
)
def generate_full_tree(self):
head = random.choice(self.functions)()
self.generate_full_tree_helper(head)
return head
# ...
# (a0, a1) -> (d0, d1, d2, d3)
if __name__ == "__main__":
gp = GP(functions=[AND, OR, NOT, IF])
gp.generate_full_tree()
Which will print:
depth: 2, node: IF, children: 3
depth: 2, node: IF, children: 6
depth: 2, node: IF, children: 10
depth: 1, node: NOT, children: 11
depth: 0, node: IF, children: 12
depth: 2, node: NOT, children: 15
depth: 1, node: NOT, children: 16
depth: 0, node: IF, children: 17
depth: 2, node: IF, children: 20
depth: 2, node: IF, children: 23
depth: 2, node: IF, children: 25
depth: 1, node: NOT, children: 26
depth: 0, node: IF, children: 27
When I would expect it to print (due to the required children count of each Function):
depth: 2, node: IF, children: 3
depth: 2, node: IF, children: 3
depth: 2, node: IF, children: 3
depth: 1, node: NOT, children: 1
depth: 0, node: IF, children: 3
depth: 2, node: NOT, children: 1
depth: 1, node: NOT, children: 1
depth: 0, node: IF, children: 3
depth: 2, node: IF, children: 3
depth: 2, node: IF, children: 3
depth: 2, node: IF, children: 3
depth: 1, node: NOT, children: 1
depth: 0, node: IF, children: 3
If I try and print(gp.generate_full_tree()), I get the following, which I assume is due to the children being in a cycle somehow:
Traceback (most recent call last):
File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/q3.py", line 99, in <module>
print(gp.generate_full_tree())
File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/functions.py", line 13, in __str__
ret += child.__str__(level + 1)
File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/functions.py", line 13, in __str__
ret += child.__str__(level + 1)
File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/functions.py", line 13, in __str__
ret += child.__str__(level + 1)
[Previous line repeated 993 more times]
File "/Users/michaelvytlingam/Development/ECE457A/a4/q3/functions.py", line 11, in __str__
ret = "\t" * level + self.__repr__() + f"({self.val})" + "\n"
RecursionError: maximum recursion depth exceeded
I normally have a pretty good understanding of recursion, but for some reason, this has been stumping me for quite some time now. If I were to guess, I would say the node.add_child(new_node) line doesn't do what I think it does. Any help would be greatly appreciated.
