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發現圖中兩個頂點之間的路徑

回答

相關問題