Problem with path reversing in CS50 AI -> Degrees

Question

I have a problem in my code that reverses the path my BFS search algorythm takes. The first project in the CS50 Introduction to artificial intelligence is called degrees and finds a path from one actor to another through degrees of separations in movies. My pathfinding works, everything works except for reversing the path my BFS algorythm takes. I checked my code dozens of times now and I can't seem to find the mistake I am making. I am quite new to Python so maybe it's syntax related but I really can't find the mistake. The while loop I marked is supposed to reverse the steps taken by the algorythm but it only cycles through it once instead of multiple times.

Please help me :)

QF = QueueFrontier()

startNode = Node(state=source, parent=None, action=None)

QF.add(startNode)

exploredNodes = set()

while True:

    if QF.empty():

        return None

    else:
        print ("Searching...")

        currentNode = QF.remove()

        if currentNode.state in exploredNodes:
            print ("Already visited")
        else:
            exploredNodes.add(currentNode.state)

            neighbors = neighbors_for_person(currentNode.state)

            for movie_id, person_id in neighbors:
                if person_id == target:
                    movies = []
                    actors = []
                    while currentNode.action is not None:   ***<- this is the faulty while loop***
                        print("Cycle")
                        movies.append(currentNode.action)
                        actors.append(currentNode.state)
                        currentNode = currentNode.parent
                    movies.reverse()
                    actors.reverse()
                    print ("Target acquired")
                    print(movies)
                    print(actors)
                    path = list(zip(movies, actors))
                    print(path)
                    return path
                else:
                    newNode = Node(state=person_id, parent=currentNode, action=movie_id)

                    QF.add(newNode)

                    print (newNode.state)

This is the code. The while loop that's supposed to give me the path the algorythm took only gives out one pair of actors and movies instead of multiple pairs.

Answer 1

So, here is your debugged code. Basically there were two main reasons why it was not working....

1. you were adding the node when it was not a target among the neighbors without checking whether that node is already in frontier.

2. when you backtrack, the neighbor from where you backtrack, you have not declared that neighbor as a node yet. Without declaring it as node, you were just doing currentnode.action which means the node which you removed earlier from frontier and not the node among neighbors (the target node)

   QF = QueueFrontier()

   startNode = Node(state=source, parent=None, action=None)

   QF.add(startNode)

   exploredNodes = set()

   while True:

    if QF.empty():
        raise Exception("No solution")
    else:
        #print ("Searching...")
   
        currentNode = QF.remove()
        print("CurrentNode:" + currentNode.state)
        if currentNode.state in exploredNodes:
            print ("Already visited")
        else:
            exploredNodes.add(currentNode.state)
   
            neighbors = neighbors_for_person(currentNode.state)
   
            for movie_id, person_id in neighbors:
                if person_id == target:
                    print ("Target acquired")
                    n=Node(state=person_id, parent=currentNode, action=movie_id)
                    print("Target:" + n.state)
                    movies = []
                    actors = []
   
                    while n.parent is not None:
                        s= n.parent
                        print(s)
                        movies.append(n.action)
                        actors.append(n.state)
                        n = n.parent
                    movies.reverse()
                    actors.reverse()
   
                    print(movies)
                    print(actors)
                    path = list(zip(movies, actors))
                    print(path)
                    return path
                elif (person_id not in exploredNodes):
                    newNode = Node(state=person_id, parent=currentNode, action=movie_id)
                    print("Newnode:" + newNode.state)
                    QF.add(newNode)`
   

Hope this helped. I ran it on my computer using Kevin Bacon and Tom Cruise... check for other instances too...

here is the output I got:

Loading data... Data loaded. Name: Kevin Bacon Name: Tom Cruise CurrentNode:102 Newnode:200 Newnode:193 Newnode:158 Newnode:197 Newnode:641 Target acquired Target:129 <util.Node object at 0x000002CBC5E94400> ['104257'] ['129'] [('104257', '129')] 1 degrees of separation. 1: Kevin Bacon and Tom Cruise starred in A Few Good Men