Django finding paths between two vertexes in a graph

Question

This is mostly a logical question, but the context is done in 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 :

Business Logic:

A Vertex can have 1-4 Lines related to it
A Line can have 1-2 Vertexes related to it
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)

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) :

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...

score 13 · Accepted Answer · edited May 23 '17 at 12:17

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

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...

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.

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

I personally wanted to do it by relationships as that seemed faster, but Networkx really is amazing and helped with other projects — Mojimi, Mar 02 '17 at 18:51

Django finding paths between two vertexes in a graph

1 Answers1