Recursively Collect Children In Python/django

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

Solution 1:

This implementation should work

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

    children = person.children.all()

    ifnot children:
        # this person has no children, recursion ends herereturn {'name': person.name, 'children': []}

    # this person has children, get every child's family treereturn {
        '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': [<eachelementisachild'sfamilytree>]
}

Edit

Django automatically generates reverse relations for a ForeignKey.

classPerson(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

Solution 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:

defgetChildren(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())

Solution 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):

defget_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