How to link parent and children to each other?

Question

Having two simple classes; one with only parent attribute, and one with both parent and children attributes. This means that the one with both parent and children inherits from the one with only parent.

Here's the class with only parent attribute. Let's call it Child since it can only be a child, not a parent. I'll use a method set_parent() to make it more clear, but I would use a setter in my actual code.

class Child(object):

    def __init__(self, parent=None):
        self.__parent = None
        self.set_parent(parent)

    def set_parent(self, parent):
        # Remove self from old parent's children
        if self.__parent:
            self.__parent.remove_child(self)
        # Set new parent
        self.__parent = parent
        # Add self to new parent's children
        if self.__parent:
            self.__parent.add_child(self)

The code makes perfect sense and seems to work just fine. This is, if the Parent class looks as simple as this:

class Parent(Child):

    def __init__(self, parent=None):
        super(Parent, self).__init__(parent)
        self.__children = []

    def add_child(self, child):
        if child not in self.__children:
            self.__children.append(child)

    def remove_child(self, child):
        if child in self.__children:
            self.__children.remove(child)

However, I want to be able to call my_parent.add_child(my_child) and have my_child's parent attribute set to my_parent while removing my_child from it's old parent's children.

I can't seem to figure out how to actually design the code, everything I try will turn into an infinite loop between set_parent() and add_child() or remove_child().

I know this site is not meant for other people to write code for me, but could someone at least give some hints? My brain just can't handle this problem, I've been thinking for 30 minutes straight and haven't gotten anything done. Help appreciated!

Answer 1

This problem, which is called a "Two-Way Association", is described in book "Refactorization: Improving the Design of Existing Code" by Martin Fowler, Kent Beck, and few more authors. The way the problem is solved in the book is by assigning one of the classes a complete control over another class. First, you need to decide which class must be in control here. I believe that in your case the Child should be in control, which is counter-intuitive to how the real world works. Then, you need to allow the controller to access private members of the controlled. In C++ you would solve this by making one of the classes a "friend" of another. In other languages that have true privacy you could make a public accessor method and clearly state in the documentation that it's to be used by one class only. In Python however you're not limited in such way. Consider the following code:

class Child(object):
    def __init__(self, parent=None):
        self._parent = None
        self.set_parent(parent)

    def set_parent(self, parent):
        # Remove self from old parent's children
        if self._parent:
            self._parent._children.remove(self)
        # Set new parent
        self._parent = parent
        # Add self to new parent's children
        if self._parent:
            self._parent._children.append(self)


class Parent(Child):
    def __init__(self, parent=None):
        super(Parent, self).__init__(parent)
        self._children = []

    def add_child(self, child):
        if child not in self._children:
            child.set_parent(self)

    def remove_child(self, child):
        if child in self._children:
            child.set_parent(None)


c1 = Child()
c2 = Child()
p1 = Parent()
p2 = Parent()

p1.add_child(c1)
p1.add_child(c2)
print "1:"
print "c1._parent", c1._parent
print "c2._parent", c2._parent
print "p1._children", p1._children
print "p2._children", p2._children
p2.add_child(c1)
print "2:"
print "c1._parent", c1._parent
print "c2._parent", c2._parent
print "p1._children", p1._children
print "p2._children", p2._children

c1 = Child()
c2 = Child()
p1 = Parent()
p2 = Parent()

c1.set_parent(p1)
c2.set_parent(p1)
print "3:"
print "c1._parent", c1._parent
print "c2._parent", c2._parent
print "p1._children", p1._children
print "p2._children", p2._children
c1.set_parent(p2)
print "4:"
print "c1._parent", c1._parent
print "c2._parent", c2._parent
print "p1._children", p1._children
print "p2._children", p2._children

Answer 2

What you're doing is nonsense. Just make them one class and use either add_child() and remove_child() or set_parent(), but not both.

Answer 3

Before going into the problem at hand, there are a couple of things you should fix with coding in python. First of all, you probably don't want to prefix your instance attribute names with a double underscore. Python will mangle the attribute name by prefixing it with the class name, which will likely result in unintended effects.

Class A(object):
    def __init__(self):
        self.__myvar = 5

a = A()

print a.__myvar
>>> AttributeError: 'A' object has no attribute '__myvar'

print a._A__myvar
>>> 5

Next, it seems like you're trying to construct something similar to a tree. For this task, there is no need to have a separate class for children and parents. You should be able to use the same class for both! As you seem to have realized, Python doesn't have a native tree data structure so most people tend to build their own. You can also see some packages people have made for non-native data structures here.

Finally, for a cheeky (and slightly confusing) tree implementation in python check this gist out. There is a more useful version out there that subclasses defaultdict, however I can't seem to find it right now.

Okay, so down to business. I've consolidated your Child and Parent classes into a single Node class. You can ignore the name, __str__, and __repr__ definitions as I just used those to keep track of what was what.

class Node(object):

    def __init__(self, name, parent=None):
        self.name = name
        self._parent = None
        self._children = []
        self.set_parent(parent)

    def add_child(self, other):
        if not self.has_child(other):
            self._children.append(other)

        if not other._parent == self:  # Prevents infinite loop
            other.set_parent(self)

    def remove_child(self, other):
        idx = self._children.index(other)
        return self._children.pop(idx)

    def set_parent(self, other):
        if self._parent is not None:
            if self._parent.has_child(self):
                self._parent.remove_child(self)

        self._parent = other

        if isinstance(other, Node):
            other.add_child(self)

    def has_child(self, child):
        if child in self._children:
            return True
        return False

    def __str__(self):
        return "<Node {}>".format(self.name)

    def __repr__(self):
        return self.__str__()

Now to test this and make sure everything works as expected.

p = Node('p')
c1 = Node('c1', p)
c2 = Node('c2', c1)

print p, ':', p._parent, p._children
print c1, ':', c1._parent, c1._children
print c2, ':', c2._parent, c2._children

>>> <Node p> : None [<Node c1>]
>>> <Node c1> : <Node p> [<Node c2>]
>>> <Node c2> : <Node c1> []

p.add_child(c2)
print p, ':', p._parent, p._children
print c1, ':', c1._parent, c1._children
print c2, ':', c2._parent, c2._children

>>> <Node p> : None [<Node c1>, <Node c2>]
>>> <Node c1> : <Node p> []
>>> <Node c2> : <Node p> []

c1.set_parent(c2)
print p, ':', p._parent, p._children
print c1, ':', c1._parent, c1._children
print c2, ':', c2._parent, c2._children

>>> <Node p> : None [<Node c2>]
>>> <Node c1> : <Node c2> []
>>> <Node c2> : <Node p> [<Node c1>]

Hopefully that solves your problems. I haven't done exhaustive testing on this so let me know if you run into any issues.

Answer 4

parent.add_child(child) and child.set_parent(parent) are (supposed to be) the same operation. Have one of them delegate to the other, or have both delegate to a third method, or just remove one of them. It'll make things much easier to reason about.

The quick and dirty way to go about this would be an _add_child method that adds a child without touching the child's parent attribute. Your set_parent could use that to avoid infinite recursion. However, methods like _add_child or your current remove_child are error-prone, because they break the symmetry of the two-way link. One side's idea of what the relationship looks like is temporarily different from the other side, and it's easy to accidentally get the sides out of sync. It'd be cleaner to implement add_child and set_parent in terms of methods that update both sides of the relationship at once.

Unsolicited extra advice: Don't use the double underscore prefix. It doesn't prevent code outside the class from accessing the property, and you shouldn't be trying to prevent that in Python anyway. Just use a single underscore, to indicate that it's not part of the class's public API.