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:
What I have so far:
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...
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.
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.
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.
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.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With