each graph member in depth first search contains 2 symbols python

Question

I have this python depth-first search code which just works fine.

def findworld(x): 
    znext = 'z'  # dummy value for  next
    c = 0

    for c in range(len(world)): # pairs of links from (f) to  destination (t)
        f = world[c][0]
        t = world[c][1]           
        if(x == world[c][0]) : znext = world[c][1]; break
    return znext;

world = [['a', 'b'], ['b', 'c'],
         ['c', 'd'], ['d', 'i'],
         ['i', 'n'], ['n', 'm'],
         ['m', 'l'], ['l', 'k'] ,
         ['k', 'p'] , ['p', 'u'], ['u', 'v'] , ['v', 'w'] , ['w', 'x'] , ['x', 'y'] ] # this is a set of linked rooms from a to d

initial ='i'  # initial starting rooom
goal = 'x'  # final destination goal
route = []  # keep rooms visted as a route
queue = []

queue.append(initial) # the starting (initial) room

print("Robot at: ", initial)
print("Goal is: ", goal)
compter = 0

# the loop explores our 
while queue != None:  # if queue then stop
    headq = queue[0][0]  # pull first item in queue into head
    route.append(headq)  # add each locaton (headq) to route
    tail = queue[1:len(queue)]  # get tail of queue after first item removed
    nextlink = findworld(headq[0][0])  # returns the next linked room
    newqueue = []  # make a new queue including the next link to follow + tail 
    newqueue += nextlink
    newqueue += tail
    queue = newqueue
    print (route)

    if(headq == goal):
        break

However, I want to implement it so it works with graph members like a1, a2, a3, z11 etc.

But there are problems with selecting array elements which give me infinite loop.

What I've done was

def findworld(x): 
    znext = 'z0'
    c = 0

    for c in range(len(world)):
        f = world[c][0]
        t = world[c][1]
        print("f ",f)
        print("t ",t)
        print("find x", x)
        print("find world", world[c][1])             
        if(x == world[c][0]) : znext = world[c][1]; break
    return znext;

world = [['a0', 'a1'],
         ['a1', 'a2'], ['a2', 'a3'], ['a3', 'a4'],
         ['a4', 'a5'], ['a5', 'a6'], ['a6', 'b6'],
         ['b6', 'd6'], ['d6', 'e6'], ['e6', 'f6'],
         ['f6', 'g6'], ['g6', 'g5'], ['g5', 'g4'],
         ['g4', 'g3'], ['g3', 'g2'], ['g2', 'g1'],
         ['g1', 'h1'], ['h1', 'j1'], ['j1', 'j2'],
         ['j2', 'j3'], ['j3', 'j4'], ['j4', 'j5'],
         ['j5', 'j6'], ['j7', 'j8'], ['j8', 'j9'],
         ['j9', 'k9'], ['k9', 'l9'], ['l9', 'm9'] ]

initial ='a0'
goal = 'a4'
route = []
queue = []

queue.append(initial)

print("Robot at: ", initial)
print("Goal is: ", goal)
compter = 0

while queue != None:
    headq = queue
    print("hq ", headq)
    route.append(headq)
    compter = compter + 1
    print (compter)
    tail = queue[1:len(queue)]
    print("tail ", tail)
    nextlink = findworld(headq)
    print("nextlink ", nextlink)
    newqueue = []
    newqueue += nextlink
    newqueue += tail
    queue = newqueue
    print("q", queue)

    if(headq == goal):
        break

But because I made headq = queue it's always the same member. I've never tried python before. How can I do it so it would work as the first code?

Answer 1

There are several significant problems. The first is that you're comparing a list, x, to a string in your nodes list, world[c][0]. This check will always be False, hence your infinite loop. Another is that you're confusing the dimensionality of your list in one or two places. One result of this is that you separate the two characters of the node name, and the single character can never equal the entire node label.

Try changing one aspect at a time. Use a lot of print statements to trace the values you pass and manipulate. At each decision point, make sure that you're manipulating the values you think you have. This will fail consistently until you get to the end, but you'll know what you're doing at each point.