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)

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

Затем 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