Нахождение связей между объектами в n-й степени

Question

Для следующих моделей:

class Entity(models.Model):
    name = models.CharField(max_length=256)

class Entry(models.Model):
    """ A <subj> has a <connection> to an <obj>
    """
    subj = models.ForeignKey(Entity, related_name='subject')
    connection = models.CharField(max_length=512)
    obj = models.ForeignKey(Entity, related_name='object')

У меня хранятся данные такого типа:

A работает на Z
B работает на Z
B является братомC
C живет по соседству с D

, где A, B, C, D и Z являются экземплярами Entity и «работают в» и т. Д. Хранятся в поле «отношение» модели Entry.1011 *

Теперь, как мне найти связь между A и D, учитывая, что между всеми сущностями много связей?Я хотел бы иметь возможность распечатать что-то вроде:

A подключен к D в 4-й степени (и покажет шаги в это время).

IЯ отметил это как вопрос Django, так как намерение использовать его на веб-сайте с поддержкой Django, но мне интересно, может ли здесь помочь ORM Django.

Заранее спасибо!

Answer 1

Это проблема теории графов. Ваша модель представляет ребра, соединяющие узлы, и вы хотите найти пути между узлами. Для такого рода вещей есть библиотеки Python, например, интерфейс Python для библиотеки Boost.

Изучите теорию графов и ознакомьтесь с соответствующими пакетами Python. Алгоритм поиска, который вам нужен, - это поиск в ширину или глубину.

Answer 2

Для тех, кто случайно наткнулся на эти вопросы: эссе на http://www.python.org/doc/essays/graphs/ было очень полезно.Словари на графике имеют сущности в качестве ключей, а списки сущностей - в качестве путей.

С помощью функции find_all_paths, показанной в эссе, указанном выше, я смог сделать именно то, что хотел.Спасибо всем за указатели.

Answer 3

Вам необходимо изучить алгоритм, такой как Модифицированный обход дерева предварительных заказов, который позволяет хранить такую ​​информацию в базе данных.Есть хорошая реализация Django под названием django-mptt .