Python: manipulating sub trees

Question

I'm a nooby. I'd like to acknowledge Allen Downey, Jeffrey Elkner and Chris Meyers and 'How to think like a computer scientist' for what I know.

I'm building a genetics inspired program to generate equations that match some provided problem.

The node class looks like this:

class Node(object):
    '''
    '''
    def __init__(self, cargo, left=None, right=None):
        self.cargo = cargo
        self.left  = left
        self.right = right
        self.parent = None
        self.branch = None
        self.seq = 0

    def __str__(self):
        return str(self.cargo)

    def copy(self):
        return copy.deepcopy(self)

I have a Tree class that contains an attribute: self.data which is a linked series of nodes forming a tree which I can traverse to produce an equation.

To perform crossover, I'd like to be able to swap subtrees chosen at random from two instances of Tree.

As self.data is being constructed, it builds a dictionary with a sequential key holding each node as a value. One such record looks like this:

    3: <__main__.Node object at 0x0167B6B0>} 

I thought I'd be clever and simply choose a node each from two tree instances and exchange their respective parents node.left or node.right values. Each node records if it is a left or right in its node.branch attribute.

I don't know how to reference self.data(subnode) to change it.

And both tree instances would have to have access to each other's nodes by the address saved in the dictionary.

I fear I shall have to copy and replace each subtree.

Any comments would be appreciated.

Thanks,

Peter Stewart

Nanaimo, Canada

Answer 1

Unfortunately you don't provide us with the Tree class, but let's assume it's something like:

class Tree(object):
  def __init__(self):
    self.data = None
    self.nextkey = 0
    self.thedict = {}

with the various attributes being updated accurately when new nodes are inserted. Now, while you talk about "the address saved in the dictionary", it's clear that the dict's value is NOT "an address" -- rather, it's a Node object (if you define a special method __repr__ in your node you may be able to see that in a clearer way; what you're seeing is the default representation, used for all Python objects whose type don't define or inherit __repr__).

So, swapping random subtree between two different trees only requires care in updating all of the many redundant pieces of information that you're keeping (and that must ALL be in sync). By the way, it would be simpler if such updates were methods of Tree and/or Node and so usable for any of various kinds of "edit" (insertion, removal, etc), rather than buried deep in a function that performs the updates as part of a random swap -- that's good OO practice. But, that's somewhat of a side issue.

You also don't tell us exactly how the branch attribute works, I'll assume it's a string, 'left' or 'right' as appropriate (or None if there's no parent, i.e., a root node).

To remove a subtree, you need to update: the parent node, setting to None its appropriate attribute; the root of the subtree, setting to None its parent and branch attributes; AND the Tree, removing that entry from the Tree's thedict attribute. You will also need to remember what the parent and branch were in order to be able to insert some other subtree at that spot. Therefore...:

def removeSubtreeFromTree(tree, keyindict):
  subtreenode = tree.thedict.pop(keyindict)
  parent, branch = subtreenode.parent, subtreenode.branch
  # a sanity chech can't hurt...;-)
  assert getattr(parent, branch) is subtreenode
  subtreenode.parent, subtreenode.branch = None, None
  setattr(parent, branch, None)
  return subtreenode, parent, branch

Now to ADD a new subtree to a given parent and branch in a Tree is simpler:

def addNewSubtree(tree, subtreenode, parent, branch):
  # sanity checks R us
  assert getattr(parent, branch) is None
  assert subtreenode.parent is None
  assert subtreenode.branch is None
  setattr(parent, branch, subtreenode)
  subtreenode.parent = parent
  subtreenode.branch = branch
  tree.thedict[tree.nextkey] = subtreenode
  tree.nextkey += 1

Note you can't just reuse the previous keys: there might be a "conflict" (assuming keys are unique only within a single given Tree... if you made them globally unique instead, then you could indeed reuse them).

Finally, putting these two operations and a little more together can be done. If you never need to "swap" a tree's very root, it's simpler (no special case needed to deal with a parentless subtree...) so I'm temporarily going to assume that (if you want more generality you WILL have to code the finicky special cases -- ideally after refactoring things to be methods as I previously suggested;-)...:

   def randomNonrootSubtree(tree):
     # we're in trouble if the tree ONLY has a root w/no really SUB trees;-)
     assert len(tree.thedict) > 1
     while True:
       thekey = random.choice(tree.thedict.keys())
       subtree = tree.thedict[thekey]
       if subtree.parent: return thekey

and at last...:

   def theSwapper(t1, t2):
     k1 = randomNonrootSubtree(t1)
     k2 = randomNonrootSubtree(t2)
     st1, p1, b1 = removeSubtreeFromTree(t1, k1)
     st2, p2, b2 = removeSubtreeFromTree(t2, k2)
     addNewSubtree(t1, st2, p1, b1)
     addNewSubtree(t2, st1, p2, b2)

Answer 2

If I understand correctly, you are looking for something like this...

(I have not tested this.)

def swap_nodes(dict_1, key_1, dict_2, key_2):
    node_1 = dict_1[key_1]
    node_2 = dict_2[key_2]

    # Update dicts and seq fields for the two nodes...
    dict_1[key_1] = node_2
    node_2.seq = key_1
    dict_2[key_2] = node_1
    node_1.seq = key_2

    # Update the parents...
    if node_1.branch == "left":
        node_1.parent.left = node_2
    else:
        node_1.parent.right = node_2

    if node_2.branch == "left":
        node_2.parent.left = node_1
    else:
        node_2.parent.right = node_1

    # Now update the branch and parent fields of the nodes...
    node_1.branch, node_2.branch = node_2.branch, node_1.branch
    node_1.parent, node_2.parent = node_2.parent, node_1.parent