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

This is mostly a logical question, but the context is done in Django.

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

In our Database we have Vertex and Line Classes, these form a (neural)network, but it is unordered and I can't change it, it's a Legacy Database

在我们的数据库中我们有顶点和线类，它们形成一个(神经)网络，但是它是无序的，我不能改变它，它是一个遗留数据库

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)

Now, in the application, the user will be able to visually select TWO vertexes (the green circles below)

现在，在应用程序中，用户将能够直观地选择两个顶点(下面的绿色圆圈)

The javascript will then send the pk of these two Vertexes to Django, and it has to find the Line classes that satisfy a route between them, in this case, the following 4 red Lines :

然后javascript将这两个Vertexes的pk发送给Django，它必须找到满足它们之间路由的行类，在本例中，如下4条红线:

Business Logic:

业务逻辑:

• A Vertex can have 1-4 Lines related to it
• 一个顶点可以有1-4条与之相关的直线
• A Line can have 1-2 Vertexes related to it
• 一条线可以有1-2个与之相关的顶点
• There will only be one possible route between two Vertexes
• 两个顶点之间只有一条可能的路径

What I have so far:

到目前为止，我所拥有的:

• I understand that the answer probably includes recursion
• 我知道答案可能包括递归
• The path must be found by trying every path from one Vertex untill the other is find, it can't be directly found
• 路径必须通过尝试从一个顶点到另一个顶点的所有路径来找到，否则不能直接找到
• Since there are four and three-way junctions, all the routes being tried must be saved throughout the recursion(unsure of this one)
• 由于有4个和3个路口，所以在整个递归过程中必须保存所有正在尝试的路由(不确定)

I know the basic logic is looping through all the lines of each Vertex, and then get the other Vertex of these lines, and keep walking recursively, but I really don't know where to start on this one.

我知道基本的逻辑是循环遍历每个顶点的所有线，然后得到这些线的另一个顶点，然后继续递归地走，但是我真的不知道从哪里开始。

This is as far as I could get, but it probably does not help (views.py) :

这是我所能得到的，但可能没有帮助(观点。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...

1 个解决方案

#1

As you has pointed, this is not a Django/Python related question, but a logical/algorithmic matter.

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

To find paths between two vertexes in a graph you can use lot of algorithms: Dijkstra, A*, DFS, BFS, Floyd–Warshall etc.. You can choose depending on what you need: shortest/minimum path, all paths...

要找到图中两个顶点之间的路径，可以使用很多算法:Dijkstra、a *、DFS、BFS、Floyd-Warshall等。您可以根据需要进行选择:最短路径/最小路径，所有路径……

How to implement this in Django? I suggest to don't apply the algorithm over the models itself, since this could be expensive (in term of time, db queries, etc...) specially for large graphs; instead, I'd rather to map the graph in an in-memory data structure and execute the algorithm over it.

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

You can take a look to this Networkx, which is a very complete (data structure + algorithms) and well documented library; python-graph, which provides a suitable data structure and a whole set of important algorithms (including some of the mentioned above). More options at Python Graph Library

您可以查看这个Networkx，它是一个非常完整的(数据结构+算法)和文档化良好的库;python-graph，它提供了一个合适的数据结构和一组重要的算法(包括上面提到的一些算法)。Python图形库中的更多选项