Саморекурсивный фильтр чужих ключей Django для всех дочерних объектов

Question

У меня есть эта модель с самореферентным отношением внешнего ключа:

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')

Теперь я хочу получить всех многоуровневых детей для человека.Как мне написать запрос Django для него?Он должен вести себя как рекурсивная функция.

Answer 1

Вы всегда можете добавить рекурсивную функцию в вашу модель:

РЕДАКТИРОВАТЬ: Исправлено в соответствии с SeomGi Хан

def get_all_children(self, include_self=True):
    r = []
    if include_self:
        r.append(self)
    for c in Person.objects.filter(parent=self):
        _r = c.get_all_children(include_self=True)
        if 0 < len(_r):
            r.extend(_r)
    return r

(Не используйте это, если у вас много рекурсии или данных ...)

Все еще рекомендую mptt в соответствии с предложением errx.

Answer 2

Вы должны прочитать о модифицированном обходе дерева предзаказов. Вот реализация Django. https://github.com/django-mptt/django-mptt/

Answer 3

предложение sunn0 - отличная идея, но get_all_children () возвращает странные результаты.Он возвращает что-то вроде [Person1, [Person3, Person4], []].Это должно быть изменено, как показано ниже.

def get_all_children(self, include_self=True):
    r = []
    if include_self:
        r.append(self)
    for c in Person.objects.filter(parent=self):
        _r = c.get_all_children(include_self=True)
        if 0 < len(_r):
            r.extend(_r)
    return r

Answer 4

Если вы знаете максимальную глубину вашего дерева, вы можете попробовать что-то вроде этого (не проверено):

Person.objects.filter(Q(parent=my_person)|Q(parent__parent=my_person)| Q(parent__parent__parent=my_person))

Answer 5

Я знаю, что это старый, но кто-то может просто помочь.

     def get_all_children(self, container=None):
         if container is None:
             container = []
         result = container
         for child in self.children.all():
             result.append(child)
             if child.children.count() > 0:
                 child.get_all_children(result)
         return result

, а затем просто сделайте это property (ИЛИ cached_property, если это работает для вас) на модели, чтобы его можно было вызывать в любом случае.

Answer 6

Я также собираюсь написать в QuerySet, так как это позволит вам связать их в цепочку. И я предоставлю ответ как для поиска всех детей и всех родителей.

class PersonQuerySet(QuerySet):
    def descendants(self, person):
        q = Q(pk=person.pk)
        for child in person.children.all():
            q |= Q(pk__in=self.descendants(child))
        return self.filter(q)

    def ancestors(self, person):
        q = Q(pk=person.pk)
        if person.parent:
            q |= Q(pk__in=self.ancestors(person.parent))
        return self.filter(q)

Теперь нам нужно установить PersonQuerySet в качестве менеджера.

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')

    people = PersonQuerySet.as_manager()

---

Итак, вот последний запрос.

albert_einstein = Person.people.get(name='Albert Einstein')
bernhard_einstein = Person.peole.get(name='Bernhard Caesar Einstein')
einstein_folks = Person.people.descendants(albert_einstein).ancestors(bernhard_einstein)

---

Примечание: Следующие решения так же медленны, как и остальные ответы ранее. Я проверял попадание в базу данных каждый раз, когда она рекурсирует своему ребенку / родителю. (Если кто-то может улучшить дальнейшее с некоторой оптимизацией и кэшированием, это будет лучше, возможно, предварительная выборка соответствующих данных перед запросом) Тем временем, mptt более практичен.

Answer 7

У меня была очень похожая бизнес-проблема , при которой, учитывая члена команды, я должен был найти всю команду под ним.Но большое количество сотрудников делало рекурсивное решение очень неэффективным, а мой API получал ошибки тайм-аута с сервера.

Принятое решение берет узел, переходит к его первому дочернему элементу и углубляется до нижней части иерархии.Затем снова возвращается ко второму ребенку (если существует), а затем снова опускается до самого дна.Короче говоря, он исследует все узлы один за другим и добавляет все элементы в массив.Это приводит к большому количеству вызовов БД, и его следует избегать, если нужно исследовать огромное количество узлов.Решение, которое я придумал, извлекает узлы послойно.Количество вызовов в БД равно количеству слоев.Посмотрите на эту SO ссылку для решения.