Graphs: Python - Refactoring Path-Finding

Why is

Visiting callan

printed twice when the is run?

This is the command


railway.add_edge(peel, harwick)
railway.add_edge(harwick, callan)
railway.add_edge(callan, peel)

peel_to_ulfstead_path_exists = railway.find_path('peel', 'ulfstead')

that runs this piece of code in

  def find_path(self, start_vertex, end_vertex):
    start = [start_vertex]
    seen = {}
    while len(start) > 0:
      current_vertex = start.pop(0)
      seen[current_vertex] = True
      print("Visiting " + current_vertex)
      if current_vertex == end_vertex:
        return True
        vertex = self.graph_dict[current_vertex]
        next_vertices = vertex.get_edges()
        next_vertices = [vertex for vertex in next_vertices if vertex not in seen]
    return False

I would have assumed that after pop(0) removed “callan” from the “start” list that the while loop would end and return False. There would be no more next_vertices with which to extend the start list.

However, it runs one more time for the following results:

Visiting peel
Visiting harwick
Visiting callan
Visiting callan


Helps if you post enough code to reproduce it, otherwise others have to take your word for that your description of what is going on is accurate and won’t be able to make their own observations.
It would for example be nice to be able to verify that this is really happening before starting to look for possible causes, or one might end up looking for something that isn’t there.

Maybe you’re adding it twice to your queue, looks to me like you do have a bug that could lead to that happening.

In general though, you can use prints to make observations about what is being done, sounds like you’re only looking at the final outcome and not at all at what’s happening to get there.