How to get all ancestors of a Django object when ForeignKey is not self-referencing?

Question

I have a model Person and another model Relation. Before creating a new relation I want to check if this relation is possible or not.

This post and some other similar posts provides a solution but for self-referencing models, my model is not self referencing. Django self-recursive foreignkey filter query for all childs

class Person(models.Model):
    identifier = IntegerField(null=True)
    title = CharField(max_length=100, null=True)

    def get_all_parent_ids(self):
        # I want to get all the ancestors of this person
        # but this method only gets immediate parents right now
        return [parent.parent.id for parent in self.parenting.all()]

    def get_all_children_ids(self):
        # I want to get all the descendants of this person
        # but this method only gets immediate children right now
        return [child.children.id for child in self.baby_sitting.all()]


class Relation(models.Model):
    name = CharField(max_length=50, null=True)
    parent = ForeignKey(Person, on_delete=models.PROTECT, related_name="parenting")
    children = ForeignKey(Person, on_delete=models.PROTECT, related_name="baby_sitting")

    class Meta:
        unique_together = ('parent', 'children')

def is_relation_possible(new_parent_id, new_children_id):
    new_parent_person = Person.objects.get(pk=new_parent_id)
    all_parents = new_parent_person.get_all_parent_ids()
    if new_children_id in all_parents:
        return False
    else:
        return True

For example: Existing relaions - A to B - B to C - C to D - D to E

I want is_relation_possible(E, A) to return False, as E has an ancestor A.

Currently it only check immediate parents and not all parents.

Answer 1

You should to use recursion:

def is_relation_possible(new_parent_id, new_children_id):
    new_parent_person = Person.objects.get(pk=new_parent_id)
    all_parents = new_parent_person.get_all_parent_ids()
    related = ( new_children_id in all_parents 
                or 
                any( is_relation_possible( ancestor_id, new_children_id) 
                     for ancestor_id in all_parents )  # (*1)
               )
    return related

(*1) Here the trick: is related if itself is related or is related through their ancestors.

Notice 1: If you are working with graphs and not with hierarchies, it may turn on an infinite loop.

Notice 2: Not tested. Test it and come back :)