Path finding between models in Django

Question

I am trying to make a graph like structure in django using models to create paths between model instances.

But I am no quite sure about how to do that automatically.

The basic structure of my models is something like this:

class Location(TimeStampedModel):
   name = models.Charfield()
   level = models.SmallPositiveIntegerField()
   previous_locations = models.ForeignKey('self')
   next_locations = models.ForeignKey('self')
   related_locations = models.ForeignKey('self')

That previous_locations, next_locations and related_locations were my first approach in order to get some kind of tree structure, but they are pretty useless when there are several locations with the same level. For example, location_1 (with level = 1) can go to location_2 and location_3 (both with level = 2) and then both can go to location_4 (with level = 4).

Maybe changing the foreign key to a many to many relation can solve this, but it's still not clear to my how to create the paths.

For the paths, I made the following model:

class Path(TimeStampedModel):
   name = models.Charfield()
   locations = models.ManyToManyField(Locations)

Summarizing, the goal is select two locations and automatically create the shortest path or a group of paths (as maybe 2 paths require the same amount of steps). However, I don't know how to doit with the relations I currently have.

I am open to some ideas but I don't want to modify my models too much.

Does some "tree graph" model exist for django? Maybe there's something to which I can say "Hey, take those locations with those levels and those relations between them and create a graph and give me that sweet shortest path" but I don't know about it.

If it does not exist: Can someone guide me on how to make an algorithm to find the shortest path between those locations?

To show an example of exactly what I want to do with my models, here we have an image. The shortest path from 1 to 7 is 1, 3, 7. But from 1 to 8 there are two equally large paths. And I want to be able to go from 5 to 7 (that's why I have related location). How can I automatically do it?

Not asking for code, just give me a hint or a place where I can read. Thanks!

Path finding between models in Django

0 Answers