python - Django encuentra caminos entre dos vértices en un gráfico

recursion django-models

Question

Esta es principalmente una pregunta lógica, pero el contexto se hace en Django.

En nuestra base de datos tenemos Vertex y clases de línea, estas forman una red (neural), pero no está ordenada y no puedo cambiarla, es una base de datos heredada.

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)

Ahora, en la aplicación, el usuario podrá seleccionar visualmente DOS vértices (los círculos verdes a continuación)

El javascript enviará el pk de estos dos vértices a Django, y tiene que encontrar las clases de línea que satisfacen una ruta entre ellos, en este caso, las siguientes 4 líneas rojas:

Lógica de negocios:

• Un Vertex puede tener de 1 a 4 líneas relacionadas con él
• Una línea puede tener 1-2 vértices relacionados
• Solo habrá una ruta posible entre dos vértices

Lo que tengo hasta ahora

• Entiendo que la respuesta probablemente incluya la recursión
• La ruta se debe encontrar probando cada ruta desde un Vértice hasta que el otro se encuentre, no se puede encontrar directamente
• Como hay uniones de cuatro y tres vías, todas las rutas que se intentan se deben guardar durante la recursión (no estoy seguro de esta)

Sé que la lógica básica es recorrer todas las líneas de cada vértice, y luego obtener el otro vértice de estas líneas, y seguir caminando recursivamente, pero realmente no sé por dónde empezar en este.

Esto es todo lo que pude obtener, pero probablemente no ayuda (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

Como ha señalado, esta no es una pregunta relacionada con Django / Python, sino una cuestión lógica / algorítmica.

Para encontrar caminos entre dos vértices en un gráfico, puede usar muchos algoritmos: Dijkstra , A * , DFS , BFS , Floyd-Warshall, etc. Puede elegir según lo que necesite: ruta más corta / mínima, todas las rutas ...

¿Cómo implementar esto en Django? Sugiero no aplicar el algoritmo sobre los modelos en sí, ya que esto podría ser costoso (en términos de tiempo, consultas db, etc.) especialmente para gráficos grandes; en cambio, prefiero mapear el gráfico en una estructura de datos en memoria y ejecutar el algoritmo sobre él.

Puede echarle un vistazo a esta Networkx , que es una biblioteca muy completa (estructura de datos + algoritmos) y bien documentada; python-graph , que proporciona una estructura de datos adecuada y un conjunto completo de algoritmos importantes (incluidos algunos de los mencionados anteriormente). Más opciones en Python Graph Library