Parent/Child(ren) Hierarchy / "Nested Sets", in Python/Django

Question

I'm using Django/Python, but pseudo-code is definitely acceptable here.

Working with some models that already exist, I have Employees that each have a Supervisor, which is essentially a Foreign Key type relationship to another Employee.

Where the Employee/Supervisor hierarchy is something like this:

Any given Employee has ONE Supervisor. That Supervisor may have one or more Employees "beneath", and has his/her own Supervisor as well. Retrieving my "upline" should return my supervisor, his supervisor, her supervisor, etc., until reaching an employee that has no supervisor.

Without going hog-wild and installing new apps to manage these relationships, as this is an existing codebase and project, I'm wondering the "pythonic" or correct way to implement the following functions:

def get_upline(employee): 
    # Get a flat list of Employee objects that are
    # 'supervisors' to eachother, starting with 
    # the given Employee. 
    pass


def get_downline(employee):
    # Starting with the given Employee, find and 
    # return a flat list of all other Employees 
    # that are "below". 
    pass

I feel like there may be a somewhat simple way to do this with the Django ORM, but if not, I'll take any suggestions.

I haven't thoroughly checked out Django-MPTT, but if I can leave the models in tact, and simply gain more functionality, it would be worth it.

Answer 1

Relational databases are not good for this kind of graph queries, so your only option is to do a bunch of query. Here is a recursive implementation:

def get_upline(employee):
    if self.supervisor:
        return [employee] + self.supervisor.get_upline()
    else:
        return [employee]

def get_download(employee):
    l = [employee]
    for minion in self.minion_set.all():
        l.extend(minion.get_download())
    return l

Answer 2

You don't have to touch your models to be able to use django-mptt; you just have to create a parent field on your model, django-mptt creates all the other attributes for mptt automaitcally, when you register your model: mptt.register(MyModel).

Though if you just need the 'upline' hierarchy you wouldn't need nested sets. The bigger performance problem is going the opposite direction and collect eg. children/leaves etc, which makes it necessary to work on a nested set model!