Recursively Collect Children in Python/Django

Question

I have a model like so....

class Person(models.Model):
    name = models.CharField(max_length=55,null=False, blank=False)
    parent = models.ForeignKey('Person.Person', null=False, blank=False)

I want to create a recursive function that will eventually return a dictionary of an entire persons family tree....

So for example...

first_person = Person.objects.filter(name='FirstPerson')
family_tree = GetChildren(first_person)

Where GetChildren is my recursive function that will continuously call GetChildren, until there are no more children... It should then return a dictionary that holds all of these children like so...

{
    'name': 'FirstPerson',
    'children': [
        {
            'name': 'FirstPersonChild1'
            'children': [ ... ]
        },
        {
            'name': 'FirstPersonChild2'
            'children': [ ... ]
        }
    ]
}

I have never been good with recursion, would someone mind explaining how I would go about accomplishing this...

Answer 1

This implementation should work

def get_family_tree(person):
    """ return a family tree for a Person object """

    children = person.children.all()

    if not children:
        # this person has no children, recursion ends here
        return {'name': person.name, 'children': []}

    # this person has children, get every child's family tree
    return {
        'name': person.name,
        'children': [get_family_tree(child) for child in children],
    }

Note that this will take as many database calls as there are persons. You can try to fetch all the data into memory if you run into performance issues.

Thinking About Recursion

One way to think about recursion is to start off with the base case - i.e. where the recursion will end. In your case, we know how the family tree looks like if a person has no children:

{
    'name': 'FirstPerson',
    'children': [],
}

After you have the base case(s), think about the problem where you have to perform the recursion once.

In your case, it would be parents with children, but no grand children. We know how each child's family tree should look - it's just the base case! This leads us to the solution where we return the parent's name, and a list of each child's family tree. Leading to something like:

{
    'name': FirstPerson,
    'children': [<each element is a child's family tree>]
}

Edit

Django automatically generates reverse relations for a ForeignKey.

class Person(models.Model):
    ....
    parent = models.ForeignKey('self', related_name='children', blank=True, null=True)

p = Person()
p.children.all() # automatically fetch all Person objects where parent=p

See https://docs.djangoproject.com/en/1.9/ref/models/fields/#foreignkey

Answer 2

You can accomplish this by writing a custom method on the model. The way you call it would look something like this:

first_person = Person.objects.filter(name='FirstPerson')
family_tree = first_person.getChildren()

Where getChildren would look something like this:

def getChildren(self):
    children = Person.objects.filter(parent=self)
    # return children
    # OR just format the data so it's returned in the format you like
    # or you can return them as Person objects and have another method
    # to transform each object in the format you like (e.g Person.asJSON())

Answer 3

You should try the package django-mptt as it works great or this purpose:

You can use TreeForeignKey() as the ForeignKey.

You can then add this method to the model to get the objects (or look into the docs I have provided to get the children instead of the parents/ancestors):

def get_category_and_parents(self):
    """ Recursively retrieves parent categories (including self) using MPTT """
    full_category = self.category.get_ancestors(include_self=True)
    return full_category

Github:

https://github.com/django-mptt/django-mptt

Docs:

http://django-mptt.github.io/django-mptt/mptt.models.html#mptt.models.MPTTModel.get_children