Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Django finding paths between two vertexes in a graph

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)

enter image description here

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 :

enter image description here

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...
like image 416
Mojimi Avatar asked Feb 14 '17 18:02

Mojimi


People also ask

How do you find the path between two nodes on a graph?

Approach: Either Breadth First Search (BFS) or Depth First Search (DFS) can be used to find path between two vertices. Take the first vertex as a source in BFS (or DFS), follow the standard BFS (or DFS). If the second vertex is found in our traversal, then return true else return false.

How do you find the shortest path between two vertices on a graph in Python?

Approach: The idea is to use queue and visit every adjacent node of the starting nodes that traverses the graph in Breadth-First Search manner to find the shortest path between two nodes of the graph.

Which traversal is used to find the shortest path between two vertices?

Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Is there a path in directed graph?

A directed path (sometimes called dipath) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.


1 Answers

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

like image 81
trinchet Avatar answered Oct 19 '22 13:10

trinchet