Django models hierarchy to adjacency list or nested set - optimal way (with filtering)

Question

my django application stores some hierarchical data in the DB, as following:

 class Foo(Model):
     # ... fields
     parent = ForeignKey('self', null = True)

Now, in order to display that tree data in jqGrid Tree I need that data to be converted to adjacency list or nested set, as those two methods are supported by jqGrid.

I've written simple function that builds an adjacency list, as following (pseudocode)

list=[]
def build_list(parent = None, level = 0)
    data = Foo.objects.select_related().filter(parent=parent).annotate(sub_count = Count('foo'))
    for x in objects:
        obj = {
        'name': x.name,
        'id': x.pk,
        'level': level,
        'isLeaf': x.sub_count == 0
        }
    list.append(obj)
    if x.sub_count > 0:
        build_list(x.pk, level + 1)

however I'm afraid of this recursion as the number of records grows.

Is there any better way of doing that?

PS. I can't change the schema (definition) of the model, as other parts of the application (and other services) rely on the current structure.

PS. 2. the database behind is Postgres, but I'd like the solution to stay db-agnostic, if possible

Answer 1

There is an algorithm for storing hierarchical data in SQL-database. It's called Modified Preorder Tree Traversal. You can read Storing Hierarchical Data in a Database article for details. It will allow you to select all items of the sub-tree in one query.

For Django there is an application that implements it - django-mptt

Actually you will need to modify your database, but this will include adding two numeric columns, so you can leave parent and all other fields untouched

Answer 2

You could use BFS to avoid memory issues:

Untested Code:

def example_bfs():
    roots = Foo.objects.filter(parent=None).annotate(sub_count = Count('foo'))
    q = []
    q = list(roots)
    tree = []
    if q:
        iter = q.pop(0)
    else:
        return tree
    while iter:
        dict = {}
        objs = []
        childs = Foo.objects.filter(parent = iter).annotate(sub_count = Count('foo'))
        for x in childs:
            obj ={}
            objs.append(obj)
        dict[iter] = objs
        tree.append(dict)
        q += list(childs)
        level += 1 
        try:
            iter = q.pop(0)
        except:
            return tree
    return tree