Поиск путей между моделями в Django

Я пытаюсь сделать графоподобную структуру в django, используя модели для создания путей между экземплярами моделей.

Но я не совсем уверен в том, как сделать это автоматически.

Базовая структура моих моделей выглядит примерно так:

class Location(TimeStampedModel):
   name = models.Charfield()
   level = models.SmallPositiveIntegerField()
   previous_locations = models.ForeignKey('self')
   next_locations = models.ForeignKey('self')
   related_locations = models.ForeignKey('self')

Такие previous_locations, next_locations и related_locations были моим первым подходом, чтобы получить некую древовидную структуру, но они довольно бесполезны, когда есть несколько локаций с одинаковым уровнем. Например, локация_1 (с уровнем = 1) может перейти в локацию_2 и локацию_3 (обе с уровнем = 2), а затем обе могут перейти в локацию_4 (с уровнем = 4).

Возможно, изменение внешнего ключа на отношение многие ко многим может решить эту проблему, но мне все еще не ясно, как создавать пути.

Для дорожек я сделал следующую модель:

class Path(TimeStampedModel):
   name = models.Charfield()
   locations = models.ManyToManyField(Locations)

Подводя итог, цель состоит в том, чтобы выбрать два места и автоматически создать кратчайший путь или группу путей (поскольку, возможно, 2 пути требуют одинакового количества шагов). Однако я не знаю, как это сделать с теми отношениями, которые у меня сейчас есть.

Я открыт для некоторых идей, но я не хочу слишком сильно модифицировать свои модели.

Существует ли какая-то модель "древовидного графа" для django? Может быть, есть что-то, чему я могу сказать: "Эй, возьми эти места с этими уровнями и отношениями между ними, создай граф и дай мне этот сладкий кратчайший путь", но я не знаю об этом.

Если его не существует: Может ли кто-нибудь подсказать мне, как составить алгоритм для поиска кратчайшего пути между этими местами?

Чтобы показать пример того, что именно я хочу сделать со своими моделями, вот изображение. Кратчайший путь от 1 до 7 - это 1, 3, 7. Но от 1 до 8 есть два одинаково больших пути. И я хочу иметь возможность пройти от 5 до 7 (поэтому у меня есть связанное расположение). Как я могу сделать это автоматически?

Не прошу код, просто дайте мне подсказку или место, где я могу прочитать. Спасибо!

Вернуться на верх