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

Question

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

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

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) 

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

Код JavaScript будет затем отправить рк этих двух вершин, чтобы Django, и он должен найти классы строки, которые удовлетворяют маршрут между ними, в этом случае, следующие 4 красные линии:

Бизнес Логика:

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

То, что я до сих пор:

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

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

Это, насколько я мог бы получить, но это, вероятно, не помогает (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... 

Answer 1

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

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

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

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