Introduction
We’re currently working on a Django REST Framework project. It connects to a Postgres database that holds some hierarchical (tree structure) data, that goes a number of levels deep. We should offer an endpoint for GET requests that returns the entire nested tree structure (parent, children, grandchildren etc.) when no parameter is offered.
Sample data
The table below shows the sample data of regions, where each region can have a parent, indicating the hierarchy of regions. In this example, the hierarchy is three levels deep (world>continent>country). But in reality, the tree could go much deeper, having an unknown number of levels (world>continent>country>province>city>neighborhood>etc.).
| id | region | parent_region_id |
|---|---|---|
| 1 | world | NULL |
| 2 | europe | 1 |
| 3 | asia | 1 |
| 4 | africa | 1 |
| 5 | belgium | 2 |
| 6 | germany | 2 |
| 7 | spain | 2 |
| 8 | japan | 3 |
| 9 | indonesia | 3 |
| 10 | vietnam | 3 |
| 11 | tanzania | 4 |
| 12 | egypt | 4 |
| 13 | senegal | 4 |
Our goal
The JSON output shown below is what we try to achieve. It’s the goal for the response body of the GET request for the /region resource.
{
"id":1,
"region":"world",
"children":[
{
"id":2,
"region":"europe",
"children":[
{
"id":5,
"region":"belgium"
},
{
"id":6,
"region":"germany"
},
{
"id":7,
"region":"spain"
}
]
},
{
"id":3,
"region":"asia",
"children":[
{
"id":8,
"region":"japan"
},
{
"id":9,
"region":"indonesia"
},
{
"id":10,
"region":"vietnam"
}
]
},
{
"id":4,
"region":"africa",
"children":[
{
"id":11,
"region":"tanzania"
},
{
"id":12,
"region":"egypt"
},
{
"id":13,
"region":"senegal"
}
]
}
]
}
What we’ve tried and achieved so far
Here’s how we tried to achieve our goal. See code below for models, serializers and views:
Models.py
________
class HierarchyData:
region = models.CharField(max_length=100, null=False, default=None)
parent = models.ForeignKey("self", models.DO_NOTHING, null=True, blank=True, db_column='parent', related_name="children")
Serializers.py
__________
class HeirarchyDataSerializer(serialisers.ModelSerializer):
class Meta:
model = HierarchyData
fields = [“id”,”region”, “children”]
Views.py
__________
Class ListHierarchyData(generics.ListAPIView):
queryset = HierarchyData.objects.all()
serializer_class = HeirarchyDataSerializer
permission_classes = [isAuthenticated]
When I call the end point for given scenario, I get the JSON response in the following format:
{
“id”: 1,
“region”: “world”,
“children”: [ 2,3,4]
}
Related Stack Overflow questions that didn’t seem to answer my issue
- How to recursively query in django efficiently?
- Django - Models - Recursively retrieve parents of a leaf node
- Django self-recursive foreignkey filter query for all childs
Above mentioned question partially solves my problem but I’m still unable to get the desired result. See details below:
1: I can’t touch database directly, I have to interact with database with ORM only.
2: Recursive time out and can’t serialize, saying object of type “Model” is not serializable.
3: This one partially worked for me: Based on this post, I tried to add the following in the model:
def get_children(self):
children = list()
children.append(self)
for child in self.children.all():
children.extend(children.get_children())
return children
I then get all nested children, but all nested values are on the same level. For example world has children [2,3,4] and those have (grand)children themselves. Then it lists those on the same line, e.g children = [2,3,4,5,6,7,8,9, 10, 11,12,13]. This doesn’t represent the levels in the sample data.
Then I tried the following solution for the model:
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
That one works; it finds the nested children but it creates two issues: a. It gives me serializer errors when I use the code as it is, but if I add ‘get_all_children’ in serializer and add a different serializer for that attribute, then it serializes the objects, which I’m ok with. b. It is unable to append them in a nested fashion, it just nests a list inside another list without having children. It shows the data like this (limited to Europe, to not have a huge example shown here):
{
"id":1,
"region":"world",
"get_all_children":[
[
{
"id":2,
"region":"europe"
}
],
[
[
{
"id":5,
"region":"belgium"
}
],
[
{
"id":6,
"region":"germany"
}
],
[
{
"id":7,
"region":"spain"
}
]
]
]
}
Now the data is fine except that after Europe it doesn’t start to nest the children inside the same array, it just starts a new array for the children and append them with outer list. It basically adds a nested structure, without nesting it inside the parent.
Our question
How can we return the output mentioned in ‘our goal’ for this region data, that holds a tree structure that goes an unknown amount of levels deep? of course it's finite depth.
The only constraint I have to follow is that I can't edit the views part!
