My first graph traversal code

I'm trying to solve a graph traversal problem I found, and was wondering how I could improve my implementation. Currently it seems a little convoluted and long.

The problem is as follows:
I have a matrix of size (rows x cols). This matrix has some cells that are empty (designated by a 0) and some cells that are blocked off (designated by a 1). Given a length, I would like to find a consecutive set of empty cells (ie, a path) of size length.

For this specific code instance, I actually hardcoded the matrix, as well as the length. My approach was:

• to loop through the matrix;

• at each position try to find a path, if that position was empty and not yet visited;

• if so, then find all adjacent positions that fit the same condition (ie, empty and not visited);

• if adjacent positions exist, continue finding further adjacent positions until my path is complete in size;

• if a path is not possible, then print "impossible".

My code is as follows:

```
def positionInGraph(pos):
return ((pos[0] >= 0) and (pos[1] >= 0)) and ((pos[0] < rows) and (pos[1] < cols))

def positionNotVisited(pos):
return not(pos in visited)

def positionIsEmpty(pos):
return (graph[pos[0]][pos[1]]==0)

def getAdjacent(posx, posy):
adjQueue = [(posx-1,posy), (posx, posy+1), (posx+1, posy), (posx, posy-1)]
for i in adjQueue:
if (positionInGraph(i) and positionNotVisited(i) and positionIsEmpty(i)):
yield i

def getOnePath(pos):
counter = 0
pathList = []
processQueue = []
if (not(positionIsEmpty(pos)) or (pos in visited)):
return (pathList, counter)
else:
processQueue.append(pos)
while (processQueue and (counter < length)):
currentPos = processQueue.pop()
visited.add(currentPos)
pathList.append(currentPos)
counter = counter + 1
adjQueue = getAdjacent(currentPos[0],currentPos[1])
if (not(adjQueue) and counter < length):
pathList.pop(currentPos)
c

1. Bug

I tried a different test case:

graph = [[1, 0, 0, 0, 1], [1, 1, 0, 1, 0], [0, 0, 0, 0, 0], [1, 1, 0, 1, 1], [1, 0, 0, 0, 0]]
rows = 5
cols = 5
length = 8

and then findFinalPath returned the following path:

[(0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0), (3, 2), (4, 2)]

This is not a legal path, since (2, 0) is not adjacent to (3, 2).

I give an explanation for this bug in 2.18 below, but it would be a good exercise to for you to try to figure out for yourself what's going wrong here. How does your search manage to step from (2, 0) to (3, 2)?

1. Comments on your code

-
No docstrings! What do your functions do, and how do you call them?

-
This kind of program is an excellent candidate for doctests.

-
The use of global variables makes your code difficult to re-use. For example, the global variable graph means that it would be awkward if you ever wanted to find paths in two different graphs.

When you have persistent state (like your graph) with associated operations (like your function positionInGraph) it's often a good idea to organize your code into classes and methods respectively. See section 3 below for how I would do this in your case.

-
You don't guard the execution of the test program with if __name__ == __main__:. This means that when I import your program into an interactive Python interpreter, it immediately starts running, which makes it harder for me to test. Put your test code into test functions or doctests.

-
Returning the string "impossible" when no path is found isn't the best way to design the interface. Returning an exceptional value to indicate failure tends to be error-prone: it's too easy for the caller to forget to check. It's usually better to raise an exception when exceptional circumstances are encountered.

-
You represent your coordinates as a pair (y, x). It would be slightly easier to understand the output of your program if you represented coordinates in the usual way (x, y). This would of course require a corresponding change, either looking up cells with graph[pos[1]][pos[0]] (preferred) or transposing your matrix so that it is in column-major order.

-
You set the number of rows and columns by hand but these numbers are easy to determine: they are len(graph) and len(graph[0]) respectively. (I prefer to call these numbers height and width myself.)

-
Your functions positionInGraph, positionNotVisited and positionIsEmpty all take a pos as their argument, but getAdjacent takes two arguments posx and posy (which are wrongly named: posx is the y-coordinate and vice versa). You should generally strive to be consistent in little details like this: it makes it easier to remember how to call functions.

-
The Python style guide (PEP8) says that "Function names should be lowercase, with words separated by underscores as necessary to improve readability" and the same for variable names. So you should consider changing positionIsEmpty to position_is_empty and so on. (You're not obliged to follow PEP8 but it makes it easier for other Python programmers to read your code.)

-
You can use itertools.product to avoid nested loops.

-
The loop

for i in adjQueue:
    processQueue.append(i)

can be written

processQueue.extend(adjQueue)

-
You have a variable called processQueue but it is not a queue. A queue is a data structure where you add elements to one end of a list and remove them from the other end (in Python you would use collections.deque). A data structure where you add and remove elements at the same end is called a stack.

-
You have a variable counter that you increment and decrement in parallel with adding and removing positions to pathList, so that counter is always the length of pathList. It would be better to drop counter and call len(pathList) instead: one less thing to go wrong. (If you were worried that len(pathList) might be an O(n) operation as it is in some languages, you can look at the TimeComplexity page on the Python wiki for reassurance.)

-
If you have an algorithm that uses a stack, it's often easiest and clearest to implement it as a recursive function (you can implicitly use the function call stack instead of having to explicitly push and pop your own stack). See section 3 below for how to do this.

-
You give the maze once in a comment:

# oxoo
# xoxo
# ooxo
# xooo
# oxox

and then again in code:

graph = [[0,1,0,0],[1,0,1,0],[0,0,1,0],[1,0,0,0],[0,1,0,1]]

This violates the DRY principle (Don't Repeat Yourself): it would be easy for you to make a mistake when encoding your maze as a matrix of 1s and 0s. Why not get the computer to do it for you?

-
Similarly, it's hard for you to check the results of your program, because the path comes out as a list of coordinates, which is tedious and error-prone to check by eye. Even in the buggy example I gave in section 1 above, it would be easy to give it a quick look and miss the err

StackExchange Code Review Q#24136, answer score: 8