Recursively gather children in Python / Django

Question

I have such a model ...

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 ultimately return a dictionary of a whole family of people ...

So for example ...

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

Where GetChildren is my recursive function that will constantly call GetChildren until there are more children ... Then it should return a dictionary that stores all these children, for example ...

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

I have never been good with recursion, someone could explain how I will do 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 family tree return { 'name': person.name, 'children': [get_family_tree(child) for child in children], } 

Please note that this will require as many database queries as there are people. You can try to extract all the data into memory if you encounter performance problems.

The thought of recursion

One way to think about recursion is to start with the base case - that is, where the recursion ends. In your case, we know what a family tree looks like if a person has no children:

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

Once you have the underlying code (s), think about the problem when you need to do the recursion once.

In your case, these would be parents with children, but not grandchildren. We know what each child family tree should look like - this is just a basic case! This leads us to a solution in which we return the parent name and list of each child family. I will cite something like:

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

Edit

Django automatically generates reverse relationships for 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 your own method on the model. What you call it will look something like this:

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

Where getChildren will look something like this:

 def getChildren(self): children = Person.objects.filter(parent=self) # return children # OR just format the data so it 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 (eg Person.asJSON()) 

Answer 3

You should try the django-mptt package as it works just fine or for this purpose:

You can use TreeForeignKey() as a ForeignKey.

Then you can add this method to the model for receiving objects (or view the documents that I provided to get children instead of 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.imtqy.com/django-mptt/mptt.models.html#mptt.models.MPTTModel.get_children