Login

Nested set abstraction for hierarchical data

Author:
lars.yencken
Posted:
May 9, 2008
Language:
Python
Version:
.96
Tags:
tree hierarchy nested-set
Score:
0 (after 0 ratings)

The nested set abstraction is a very nice way to store hierarchical data, for example places, in a database. It provides an easy way to say that Melbourne is within Victoria, which is within Australia, etc.</p>

The calls to addChild() are expensive, so this model is slow to build, and bad if you do frequent updates. If you're building a read-only model though, it's much faster than ForeignKey('self') for determining ancestor/descendent relationships.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class HierarchicalModel(models.Model):
    "A generic hierarchical database model."

    left_visit = models.IntegerField(primary_key=True)
    right_visit = models.IntegerField(db_index=True)

    class Meta:
        abstract = True

    @classmethod
    def getRoot(cls):
        "Get the unique root node for this table."
        return cls.objects.get(left_visit=1)

    @classmethod
    def initRoot(cls, **kwargs):
        "Set the unique root object. Call only once."
        kwargs['left_visit'] = 1
        kwargs['right_visit'] = 2
        rootObj = cls(**kwargs)
        rootObj.save()
        return rootObj

    def getAncestors(self):
        "Returns all ancesters of this node."
        return self.objects.filter(
                left_visit__lte=self.left_visit,
                right_visit__gte=self.right_visit,
            ).order_by('left_visit')

    def getSubtree(self):
        "Returns the subtree under (and including) this node."
        return self.objects.filter(
                left_visit__gte=self.left_visit,
                right_visit__lte=self.right_visit,
            ).order_by('left_visit')

    def addChild(self, **kwargs):
        "Adds a child node under this node."
        cls = self.__class__
        nodeCount = cls.getRoot().right_visit
        parent_left_visit = self.left_visit
        parent_right_visit = self.right_visit

        cursor = connection.cursor()
        cursor.execute("""
                UPDATE %s SET right_visit = right_visit + 2
                WHERE right_visit >= %s
            """, (cls._meta.db_table, parent_right_visit))
        cursor.execute("""
                UPDATE %s SET left_visit = left_visit + 2
                WHERE left_visit > %s
            """, (cls._meta.db_table, parent_right_visit))

        kwargs['left_visit'] = parent_right_visit
        kwargs['right_visit'] = parent_right_visit + 1
        newNode = cls(**kwargs)
        newNode.save()

        self.right_visit += 2
        return newNode

    def __cmp__(self, rhs):
        return cmp(self.left_visit, self.right_visit)

    def leaves(self):
        "Returns all leaf nodes under this node."
        return self.getSubtree().extra(where=['left_visit + 1 = right_visit'])

More like this

  1. CSV Exporting of Model Data by monokrome 5 years, 3 months ago
  2. Change model field attribute in a DRY way by jedie 3 years, 4 months ago
  3. CSV Exporting of Model Data by monokrome 5 years, 3 months ago
  4. TreePrint: Print nested lists, tuples, dicts by michaeljtbrooks 2 years, 8 months ago
  5. Model with random ID by jobs@flowgram.com 6 years, 8 months ago

Comments

lars.yencken (on May 9, 2008):

Ah, ok, it looks like they've done a very thorough job. I just pulled this out of my code after I'd cleaned it up to use model inheritance. Perhaps it's still useful as a very small subset of what django-mptt does. Thanks for the link.

#

Please login first before commenting.