Django在图中的两个顶点之间找到路径

Question

这主要是一个逻辑问题,但上下文是在Django中完成的.

在我们的数据库中,我们有Vertex和Line Classes,它们形成一个(神经)网络,但它是无序的,我无法改变它,它是一个遗留数据库

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将这两个顶点的pk发送到Django,它必须找到满足它们之间路由的Line类,在这种情况下,以下4个红线:

商业逻辑:

• 顶点可以有1-4条与之相关的线
• 一条线可以有1-2个与它相关的顶点
• 两个顶点之间只有一条可能的路径

到目前为止我所拥有的:

• 我明白答案可能包括递归
• 必须通过尝试从一个Vertex的每个路径找到路径,直到另一个找到,它不能直接找到
• 由于有四个和三个路口,所有正在尝试的路径必须在整个递归过程中保存(不确定这个)

我知道基本逻辑是循环遍历每个Vertex的所有行,然后得到这些行的另一个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中实现这一点？我建议不要将算法应用于模型本身,因为这可能是昂贵的(在时间,数据库查询等方面......),特别适用于大型图形; 相反,我宁愿将图形映射到内存数据结构中并在其上执行算法.

你可以看看这个Networkx,这是一个非常完整的(数据结构+算法)和文档齐全的库; python-graph,它提供了一个合适的数据结构和一整套重要的算法(包括上面提到的一些).Python Graph Library中有更多选项