グラフ内の2つの頂点間のパスを見つけるDjango

Question

これは主に論理的な質問ですが、コンテキストは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) 

です、ユーザは、視覚的にTWO頂点（以下、緑の円）

ジャバスクリプトは、次にジャンゴにこれら2つの頂点のPKを送信する選択することができるであろう

ビジネスロジック：

• A頂点が1-4を持つことができ、それが、この場合には、それらの間のルートを満たすラインクラスは、以下の4本の赤い線を見つけることがありますそれに関連した行は
• Aライン1-2頂点が
• のみ

頂点 2の間に1つの可能なルートがあります、それに関連することができます私がこれまで持って何

：

• 私は答えはおそらくパスを見つけることです、それは直接にはできません他の刚性一つの頂点からのすべてのパスを試みるによって発見されなければならない再帰
• が含まれていることを理解して私は基本的なロジックは、それぞれのすべてのラインを通ってループしている知っている

（このいずれかの不明）

見出さ4と三方接合部があるので、試されているすべてのルートは、再帰にわたって保存する必要があります頂点、これらの線の他の頂点を取得し、再帰的に歩くことを続けるが、私は実際にどこから始めるべきかわからない。

これは、私の知る限り得ることができるようですが、それはおそらく（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

あなたが指摘したように、これはジャンゴ/ Pythonの関連する質問ではなく、論理的/アルゴリズム上の問題。

あなたはアルゴリズムの多くを使用することができ、グラフに2つの頂点間のパスを検索するには： Dijkstraは、 A*、 DFS、 BFS、 Floyd–Warshallなど。あなたは何が必要に応じて選択することができます：最短/最小パス、すべてのパス...

これはDjangoでどのように実装するのですか？私は、モデル自体にアルゴリズムを適用しないことをお勧めします。これは、特に大規模なグラフの場合は高価（時間、dbクエリなど）になる可能性があるためです。代わりに、グラフをメモリ内のデータ構造にマップし、その上でアルゴリズムを実行したいと思います。

これは非常に完全な（データ構造+アルゴリズム）ライブラリであり、十分に文書化されているので、このNetworkxをご覧ください。 python-graphであり、これは、適切なデータ構造および重要なアルゴリズムの全セット（上述のもののいくつかを含む）を提供する。もっと多くのオプションがありますPython Graph Library