Recursive Relationship

This information is also available here.

I frequently run across a situation where I need to group objects. Often these objects will belong in more than one group and the groups will consist of smaller groups. I use two Many to Many fields to represent this situation. In this example the employees field is related to my Employee model while the relationships field is related to itself creating our recursive relationship. Neither field is required and for the recursive relationships field I turn symmetry off. So here are the models.

from django.db import models

class Employee(models.Model):
    name = models.CharField(
            max_length=32)

class Department(models.Model):
    name = models.CharField(
            max_length=64)
    employees = models.ManyToManyField(
            Employee,
            null=True)
    departments = models.ManyToManyField(
            'self',
            null=True,
            symmetrical=False)

Now that we've defined our models we can create a function to return a query set of the employees for a given department. This is a simple function that creates a query set containing all of the employees for a given department and then calls itself doing the same for each of the sub departments and so on. This allows for unlimited depth and nesting of groups/departments.

def employees(department):
    query_set = department.employees.all()
    for department in department.departments.all():
         query_set = query_set | employees(department)
    return query_set

That's all there is to it. I typically create a utils.py file in my applications to store such functions. I added a few more utility functions to help demonstrate functionality as well. If you are a visual person you can use the dump function to return the organizational chart in no specific order.

def dump():
    from recursive.models import Department
    results = ''
    for department in Department.objects.all():
        results += "%s\n" % department.name
        for employee in employees(department):
            results += "\t%s\n" % employee.name
    return results

It's often nice to know if a object is part of a group so I also have an has_employee function for testing this.

def has_employee(employee, department):
    if employee in employees(department):
        return True
    else:
        return False

And here are some tests to make sure it's doing what I think it's doing.

from django.test import TestCase

class SimpleTest(TestCase):
    def test_recursive(self):
        """
        """
        from recursive.models import Department
        from recursive.models import Employee
        Employee(name='Jay').save()
        Employee(name='Brad').save()
        Employee(name='Aaron').save()
        Employee(name='Mark').save()
        Employee(name='John').save()
        self.assertEqual(Employee.objects.count(),5)

        emp = Employee.objects.all()

        d1 = Department(name='President')
        d1.save()
        d1.employees.add(emp[0])

        d2 = Department(name='VP Finance and Administration')
        d2.save()
        d2.employees.add(emp[1])

        d3 = Department(name='Computer Services')
        d3.save()
        d3.employees.add(emp[2])
        d3.employees.add(emp[3])

        d4 = Department(name='Finance')
        d4.save()
        d4.employees.add(emp[4])

        d5 = Department(name='Finance and Administration')
        d5.save()
        d5.departments.add(d2)
        d5.departments.add(d3)
        d5.departments.add(d4)

        from recursive.utils import employees

        self.assertEqual(len(employees(d1)),1)
        self.assertEqual(len(employees(d5)),4)

        from recursive.utils import has_employee
        self.assertEqual(has_employee(emp[0], d1), True)
        self.assertEqual(has_employee(emp[4], d1), False)
        self.assertEqual(has_employee(emp[4], d5), True)

        from recursive.utils import dump
        self.assertEqual(dump(),"President\n\tJay\nVP Finance and " \
                "Administration\n\tBrad\nComputer Services\n\tAaron\n\t" \
                "Mark\nFinance\n\tJohn\nFinance and Administration\n\t" \
                "Brad\n\tAaron\n\tMark\n\tJohn\n")

        print "\n%s" % dump()