How to design a directed graph model in Django?

Using Django
1

I want to create a model that represents an object with ancestors and descendants of the same kind. In view, it would be enough to display only direct parents and children.

from django.db import models
from django.contrib.auth.models import User

class Node(models.Model):
    name = models.CharField(max_length=100)
    description = models.CharField(max_length=500)
    ancestors = models.ManyToManyField('self', blank=True, symmetrical=False)
    descendants = models.ManyToManyField('self', blank=True, symmetrical=False)
    author = models.ForeignKey(User, on_delete=models.CASCADE)

What is the best way to design this kind of model?

2

Given the generalized nature of the relationships described in your Node model and that there is a “direction” between them, my first reaction is to divide this into two models:

class Node(...):
    name = ...
    description = ...
    author = ...

class Vertex(...):
    ancestor = ForeignKey(Node, ...)
    descendant = ForeignKey(Node, ...)

    class Meta:
        unique_together = [['ancestor', 'descendant']]

and I’d probably add a constraint on the class to prevent ancestor == descendant.

1 Like
3

I get an error using this layout:

graph.Vertex.ancestor: (fields.E304) Reverse accessor for 'graph.Vertex.ancestor' clashes with reverse accessor for 'graph.Vertex.descendant'.      
        HINT: Add or change a related_name argument to the definition for 'graph.Vertex.ancestor' or 'graph.Vertex.descendant'.

How to set this related_name argument properly? Or how to add a constraint?

4

It pretty much doesn’t matter what you choose as a name, as long as it’s unique.
See:

I would, in general, recommend some degree of internal consistency - so although you only need to specify one related name (allowing the use of the default for the other), I wouldn’t recommend that.

I might suggest something like using ancestor_set and descendant_set.

But there’s a twist.

Keep in mind that if you use related_name = “ancestor_set” on the ancestor field, then node.ancestor_set is the set of Vertex for which its ancestor field is referring to node. Therefore, what you’re getting from Vertex is actually the list of descendant associated with that node!

Therefore, if this makes sense to you, I would do something like:
ancestor = ForeignKey(Node, related_name=“descendants”)
descendant = ForeignKey(Node, related_name=“ancestors”)

Given an object, node, you’re then writing queries like:
descendants = Node.objects.filter(ancestors__ancestor=node)
to retrieve all the first order descendants.

See any of @adamchainz’s comments here or his blog posts (including Using Django Check Constraints to Prevent Self-Following - Adam Johnson) to see examples of check contraints. He does a lot better job of explaining them than I’d be able to.

1 Like