Django находит пути между двумя вершинами в графе

Это в основном логический вопрос, но контекст выполняется в Django.

В нашей базе данных есть вершинные и линейные классы, они образуют (нейронную) сеть, но она неупорядочена, и я не могу ее изменить, это Legacy Database

class Vertex(models.Model)
    code = models.AutoField(primary_key=True)
    lines = models.ManyToManyField('Line', through='Vertex_Line')

class Line(models.Model)
    code = models.AutoField(primary_key=True)

class Vertex_Line(models.Model)
    line = models.ForeignKey(Line, on_delete=models.CASCADE)
    vertex = models.ForeignKey(Vertex, on_delete=models.CASCADE)

Теперь, в приложении, пользователь сможет визуально выбрать TWO​​strong > вершины (зеленые круги ниже)

введите описание изображения здесь

Затем javascript отправит pk этих двух вершин в Django, и он должен найти классы Line, которые удовлетворяют маршруту между ними, в этом случае следующие четыре красные строки:

введите описание изображения здесь

Бизнес-логика:

  • Вершина может иметь связанные с ней 1-4 строки
  • Линия может содержать 1-2 Вершины, связанные с ней
  • Будет только один возможный маршрут между двумя вершинами

Что я до сих пор:

  • Я понимаю, что ответ, вероятно, включает рекурсию
  • Путь должен быть найден, пробирая каждый путь из одной вершины до тех пор, пока не найдет другую, ее нельзя найти непосредственно
  • Так как есть четыре и трехсторонние соединения, все проверяемые маршруты должны быть сохранены во всей рекурсии (неуверенность в этом)

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

Это насколько я могу получить, но это, вероятно, не помогает (views.py):

def findRoute(request):
    data = json.loads(request.body.decode("utf-8"))
    v1 = Vertex.objects.get(pk=data.get('v1_pk'))
    v2 = Vertex.objects.get(pk=data.get('v2_pk'))
    lines = v1.lines.all()
    routes = []
    for line in lines:
        starting_line = line
        #Trying a new route
        this_route_index = len(routes)
        routes[this_route_index] = [starting_line.pk]
        other_vertex = line.vertex__set.all().exclude(pk=v1.pk)
        #There are cases with dead-ends
        if other_vertex.length > 0:
        #Mind block...

Ответы

Ответ 1

Как вы указали, это не вопрос, связанный с Django/Python, а логический/алгоритмический вопрос.

Чтобы найти пути между двумя вершинами в графе, вы можете использовать множество алгоритмов: Dijkstra, A*, DFS, BFS, Floyd-Warshall и т.д. Вы можете выбрать в зависимости от того, что вам нужно: кратчайший/минимальный путь, все пути...

Как реализовать это в Django? Я предлагаю не применять алгоритм к самим моделям, поскольку это может быть дорогостоящим (с точки зрения времени, db-запросов и т.д.) Специально для больших графиков; вместо этого я предпочел бы сопоставить график в структуре данных в памяти и выполнить над ним алгоритм.

Вы можете взглянуть на этот Networkx, который является очень полным (структура данных + алгоритмы) и хорошо документированная библиотека; python-graph, который обеспечивает подходящую структуру данных и целый набор важных алгоритмов (включая некоторые из упомянутых выше). Дополнительные параметры в Библиотека графиков Python