Django self-recursive foreignkey filter query for all childs

Question

I have this model with a self referencing Foreign Key relation:

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')

Now I want to get all the multi level children for a person. How do I write a Django query for it? It needs to behave like recursive function.

Zagazig

Answer 1

You can always add a recursive function to your model:

EDIT: Corrected according to SeomGi Han

def get_all_children(self, include_self=True):
    r = []
    if include_self:
        r.append(self)
    for c in Person.objects.filter(parent=self):
        _r = c.get_all_children(include_self=True)
        if 0 < len(_r):
            r.extend(_r)
    return r

(Don't use this if you have a lot of recursion or data ...)

Still recommending mptt as suggested by errx.

EDIT: 2021 since this answer is still getting attention :/

Use django-tree-queries instead!

Gordan

Should be get_all_children() as the function call and you need to use r = r + c.get_all_children() or you'll end up with nested lists. I don't seem to have the rights to edit this myself – Nonrecognition

Updated code according to comment. If everyone was allowed to edit all posts we would have a big problem :) – Gordan

I think this should have include_self=True in the inner function call as well. Otherwise, at each recursion we just go down one more level, never actually adding anything to r. It only worked correctly for me after making that change. – Multitude

Your solution gives a good notion but is untested. At the end, r is a nested empty list. Please consider fixing it.. – Fabi

#42676585 – Connote

Answer 2

You should read about Modified preorder tree traversal. Here is django implementation. https://github.com/django-mptt/django-mptt/

Banister

is it necessary to use third party solution? is there any other way?? – Zagazig

@Ashan: You can always read about it e.g. here: dev.mysql.com/tech-resources/articles/hierarchical-data.html and write the code yourself – Koerner

Answer 3

sunn0's suggestion is great idea, but get_all_children() returns weird results. It returns something like [Person1, [Person3, Person4], []]. It should be changed to like below.

def get_all_children(self, include_self=True):
    r = []
    if include_self:
        r.append(self)
    for c in Person.objects.filter(parent=self):
        _r = c.get_all_children(include_self=True)
        if 0 < len(_r):
            r.extend(_r)
    return r

Adlai

Answer 4

If you know the max depth of your tree, you could try something like this (untested):

Person.objects.filter(Q(parent=my_person)|Q(parent__parent=my_person)| Q(parent__parent__parent=my_person))

Indusium

Answer 5

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')



    def get_children(self):
          children = list()
          children.append(self)
          for child in self.children.all():
              children.extend(children.get_children())
          return children

get_children() is going to fetch all the children of an instance using the related name and then it's going to call get_children() on the child if found recursively until no further data/children are found.

Prodigal

This answer could be improved by adding an explanation. – Set

Done, Is it ok now? – Prodigal

Answer 6

I know this is old, but someone might just get helped.

     def get_all_children(self, container=None):
         if container is None:
             container = []
         result = container
         for child in self.children.all():
             result.append(child)
             if child.children.count() > 0:
                 child.get_all_children(result)
         return result

and then simply make this a property (OR a cached_property if that works for you) on the model so it can be called on any instance.

Enamel

This does not answer the questioner, "get all the multi level children for a person"... This will in fact only get the direct children (i.e. one-level) for a person. – Ritchie

Thanks @Ritchie I must have misunderstood the question. I just updated my response with a similar snippet i have i have in one of my projects. – Enamel

Answer 7

I'm also going to write in QuerySet since this will allow you to chain them. And I will provide answer for both retrieval of all children and all parents.

class PersonQuerySet(QuerySet):
    def descendants(self, person):
        q = Q(pk=person.pk)
        for child in person.children.all():
            q |= Q(pk__in=self.descendants(child))
        return self.filter(q)

    def ancestors(self, person):
        q = Q(pk=person.pk)
        if person.parent:
            q |= Q(pk__in=self.ancestors(person.parent))
        return self.filter(q)

Now we need to set PersonQuerySet as the manager.

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')

    people = PersonQuerySet.as_manager()

---

So here's the final query.

albert_einstein = Person.people.get(name='Albert Einstein')
bernhard_einstein = Person.peole.get(name='Bernhard Caesar Einstein')
einstein_folks = Person.people.descendants(albert_einstein).ancestors(bernhard_einstein)

---

Note: The following solutions is as slow as as the rest of the other answers earlier. I have inspected the Database hit everytime it recurse to its child/parent. (If anyone can improve further with some optimization & caching, this would be better, perhaps prefetch relevant data before querying). In the meanwhile, mptt is more practical.

Ritchie

Answer 8

I had a very similar business problem, wherein given a team member, I was supposed to find out the complete team under under him. But having a large number of employees made the recursive solution very inefficient and also my API was getting time-out errors from server.

The accepted solution takes the node, goes to it's first child and goes deep down till bottom of the hierarchy. Then comes back up again to the second child (if exists), and then again goes down till the bottom. In short, it explores all the nodes one by one and appends all the members in an array. This leads to a lot of db calls and should be avoided if there is a huge number of nodes to be explored. The solution I came up with, fetches the nodes layer-wise. The number of db calls is equal to the number of layers. Have a look at this SO link for the solution.

Orff

Answer 9

Here is what I wrote to get all the steps of a post that are connected through their 'child' field

steps = Steps.objects.filter(post = post) 
steps_ids = steps.values_list('id', flat=True) 

Get all the children of 'steps' recursively:

objects   = Steps.objects.filter(child__in=steps_ids) 
while objects:
    steps     = steps | objects 
    steps_ids = objects.values_list('id', flat=True) 
    objects   = Steps.objects.filter(child__in=steps_ids) 

Eatmon

Answer 10

Every time you call recursion and access new child elements, a database call will be made(that is, the number of requests will be how many children there are).

To avoid this: can create a queryset from dictionaries and, based on it, create a dictionary with the parent__name keys. Using this key, select child elements in recursion:

def children_list(self):
    data = Person.objects.values('name', 'parent__name')

    result = {}
    for entry in data:
        result.setdefault(entry['parent__name'], []).append(entry)

    def generate_inside(name):
        arr = []
        if name in result:
            for entry in result[name]:
                arr.append(entry['name'])
                result_recursion = generate_inside(entry['name'])
                arr.extend(result_recursion)

        return arr

    return generate_inside(self.name)

To check the number of hits to the database(run shell):

python manage.py shell

connect all the necessary modules:

from .models import Person
from django.db import connection, reset_queries

and make a request:

reset_queries()  

print(Person.objects.all()[0].children_list()) 

print('how many queries', len(connection.queries))

Lorgnon