Django发现图中两个顶点之间的路径

这主要是一个逻辑问题，但上下文在Django中完成。Django发现图中两个顶点之间的路径

在我们的数据库中有顶点和班线，这些形成（神经）网络，但它是无序的，我不能改变它，这是一个旧的数据库

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的，它必须找到满足他们之间的路由，在这种情况下，线类，以下4条红线：

业务逻辑：

一个顶点可以有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...

来源

2017-02-14 Mojimi

正如你所指出的，这不是一个Django/Python的相关问题，但逻辑/算法问题。

找到两个顶点之间的路径中，你可以使用很多算法图：Dijkstra，A*，DFS，BFS，Floyd–Warshall等。您可以根据您的需要选择：最短/最小的路径，所有路径.. 。

如何在Django中实现？我建议不要将该算法应用于模型本身，因为这可能是昂贵的（在时间上，db查询等），特别是对于大图;相反，我宁愿将图形映射到内存数据结构中，然后在其上执行算法。

你可以看看这个Networkx，这是一个非常完整的（数据结构+算法）和有据可查的库;它提供了一个合适的数据结构和一整套重要的算法（包括上面提到的一些）。 Python Graph Library

来源

2017-02-18 00:49:08 trinchet

我个人希望通过这种关系来实现，因为这似乎更快，但Networkx真的很棒，并且可以帮助其他项目 – Mojimi

Django发现图中两个顶点之间的路径

回答

相关问题