Looping through two instances of a same model with Many-To-Many field

High everyone !
I’m what you would call a newbie in webdev and I’m trying to code an “itinary calculator” for public transportations with 1 connexion/correspondance max (i’ll try more complexe connections later, for fun).

So here’s the actual project : I make a web-app that allows users to alert about the presence of bus controllers in a bus line. So the individual would make the alert with the line number and the station/bus stop at which the control occured.
To make things spicier, I want to implement a “search function” where the user can put his departure station and arrival station, and it would calculate an itinary, and also calculate the risk based on the alerts. Now let’s just keep these two apps completely separated for the moment and focus on the “itinary calculator”.

What I’ve done is create a model Station and a model Line. Those are two independants models with a many-to-many fields, through another model called Route. It was important to make such a relationship model because I want a station/bus stop to have several lines passing through it, and each line goes through different stations in an orderly fashion. Here’s the code snipet I used :


class Station(models.Model):
    Station_name = models.CharField(max_length=200)
    Station_address = models.CharField(max_length=300)

class Line(models.Model):
    Line_number = models.PositiveIntegerField(validators=[MinValueValidator(1), MaxValueValidator(100)])
    Line_name = models.CharField(max_length=200, blank=True, null=True)
    Line_stations = models.ManyToManyField(Station, through="Route")

class Route(models.Model):
    line = models.ForeignKey(Line, on_delete=models.CASCADE)
    station = models.ForeignKey(Station, on_delete=models.CASCADE)
    order = models.IntegerField()

So this actually works fine. I can set up routes with a line 1 passing through stations 1,2,3,4…, and another line 2 passing through 10,4,11,12. So now, If I want to go from stations 1 to 12, I’ll have to take the line 1, at the stations 1 to 4, then at station 4, get off the bus and take the bus line 2 from stations 4 to 12. Easy on the paper, more difficult to code !

So I created this modelForm that gives two fields of choice (), both of them showing all the existing stations. One is “arrival_station”, and the other is “departure_station”. The form is submitted through the GET Method, and with that, I can just query and find all the lines that go through the arrival station, and the departure station. Now, what I want, is to find correspondances. That means, when the line found in departure doesn’t have a station that goes to the arrival station, find another line that would 1) have the arrival station, and (2) have a connexion with the departure line.

Here’s what I’ve done so far (i won’t put the def Search(request)… part, just the part where it loops through each instances of my query):

if form.is_valid():
  arrival_lines = Line.objects.filter(Line_stations__pk=form['arrival'].value())
  departure_lines = Line.objects.filter(Line_stations__pk=form['departure'].value())
  common_nodes = 0
  same_line = False

  for departure_instance in departure_lines:
     departure_stations = departure_instance.Line_stations.all() 
     for station in departure_stations:
       for arrival_instance in arrival_lines:
          if departure_instance == arrival_instance:

          arrival_stations = arrival_instance.Line_stations.all()
          if station in arrival_stations:
                common_nodes += 1

            context['same_line'] = same_line
            context['departure_lines'] = departure_lines
            context['arrival_lines'] = arrival_lines
            context['correspondances'] = common_nodes

I find this quite… horrible. Is there a more optimized way to do that ? Could I translate that to a simple query ?
Once I find a match, what’s the best thing to do ? A tupple with the departure line and arrival line ?
Note that this would only work for a one-connection path, and not more complex paths (which i’ll try later on cause it could be fun).

Thanks in advance for you attention

I thought about another way :

  1. Just define departure_line, and search if the arrival stations is one of the instances of this list “departure_line”. If true, no need to go further
  2. If none of the instances find a line with both the departure station and arrival station, THEN, I loop through each instance of departure line and then through each station of this instance to append a table “connexions” that would send a query that find both the arrival station AND the station being looped through : if there’s a match, then it’s done. I’ll edit later if I found it

What do you think about this way to go ?
My goal is to optimize my code because I’m still a begginer and I don’t want my server to slow down because of useless steps/things that could be automated in a more simpler, elegant way.

EDIT : Here’s what i’ve come to. It works, but I’m still wondering if it’s the best way to go :

        if form.is_valid():
            if form['departure'].value() != form['arrival'].value():
                departure_station = Station.objects.get(pk=form['departure'].value())
                arrival_station = Station.objects.get(pk=form['arrival'].value())
                departure_lines = departure_station.line_set.all()

                for departure_line_instance  in departure_lines:
                    departure_line_instance_stations = departure_line_instance.Line_stations.all()
                    if arrival_station in departure_line_instance_stations:
                       #break -> break if we want only one result of a direct line
                        for station_instance in departure_line_instance_stations:
                            arrival_lines = Line.objects.filter(
                            if arrival_lines:
                                context['connexion_path'].append((departure_line_instance, arrival_lines, station_instance))
                context['message'] = 'Arrival station must be different from departure station'

This feels similar to the traveling salesperson problem, though rather than calculating the shortest distance, you want all the options.

If the lines and stations are relatively static, could you cache the result and hide the complexity behind a service function? Then whenever your lines or stations change, you’d have to do the mess of updating the cache. However, I suspect that’s pretty irregular.

Regarding the querysets, it definitely seems like you can push some of the filtering into the database:

from django.db.models import Q, F
direct_lines = departure_station.line_set.filter(

indirect_lines = departure_station.line_set.exclude(

However, I’m not entirely sure that’s what you want. But I think it should sufficiently replace the looping mechanism you had here:

As an aside, give this section of the docs a read. It talks about how to access cleaned data in forms. Currently you’re accessing the raw values of the form. It should simplify your view a little too by avoiding having to look up model instances (the ModelForm will do that for you).

Whoops, should have linked the documentation for Q and F:

Q: Making queries | Django documentation | Django
F: Making queries | Django documentation | Django