6
\$\begingroup\$

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)
            counter -= 1
        for i in adjQueue:
            processQueue.append(i)


    print pathList
    return (pathList, counter)

def findFinalPath():
    #5 4 8
    # oxoo
    # xoxo
    # ooxo
    # xooo
    # oxox


    for i in xrange(0,rows):
        for j in xrange(0,cols):
            path = getOnePath((i,j))
            if path[1] == length:
                return path[0]

    return "impossible"

visited = set()
graph = [[0,1,0,0],[1,0,1,0],[0,0,1,0],[1,0,0,0],[0,1,0,1]]

rows = 5
cols = 4
length = 8


findFinalPath() 
\$\endgroup\$
8
\$\begingroup\$

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)?

2. Comments on your code

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

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

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.)

  8. 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.

  9. 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.)

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

  11. The loop

    for i in adjQueue:
        processQueue.append(i)
    

    can be written

    processQueue.extend(adjQueue)
    
  12. 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.

  13. 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.)

  14. 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.

  15. 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?

  16. 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 error. It would be better to present the results in a form that's easy for you to check. (See section 3 below for how I did this.)

  17. Your code has much unnecessary use of parentheses. The lines

    return ((pos[0] >= 0) and (pos[1] >= 0)) and ((pos[0] < rows) and (pos[1] < cols))
    return not(pos in visited)
    return (graph[pos[0]][pos[1]]==0)
    if (not(positionIsEmpty(pos)) or (pos in visited)):
    while (processQueue and (counter < length)):
    return (pathList, counter)
    

    can be written

    return 0 <= pos[0] < rows and 0 <= pos[1] < cols
    return pos not in visited
    return graph[pos[0]][pos[1]] == 0
    if not positionIsEmpty(pos) or pos in visited:
    while processQueue and counter < length:
    return pathList, counter
    

    respectively. "Program as if you know the language"!

  18. Explanation for the bug in section 1: your back-tracking implementation doesn't backtrack all your search state, so that the search state becomes inconsistent. When your search reaches a dead end, it pops the last position from pathList and decrements counter, but does not update the rest of the search state. This means that the next currentPos that gets popped from processQueue will not (in general) be adjacent to the end of the path. When you backtrack in a search, you need to backtrack all your state: in your case pathList, counter, processQueue, and visited all need to be backtracked, but you only update the first two of these, and so it goes wrong.

    See the revised code for how I keep the search state consistent. Every addition to the state as the search goes forward:

    path.append(p)
    visited.add(p)
    

    is matched by a corresponding deletion as the search backtracks:

    visited.remove(p)
    path.pop()
    

    (There's more to say about this issue, but I've moved this to section 4 below.)

3. Revised code

from itertools import product

class Found(Exception): pass
class NotFoundError(Exception): pass

class Maze(object):
    """A rectangular matrix of cells representing a maze.

    Describe the maze to the constructor in the form of a string
    containing dots for empty cells and any other character for walls.

        >>> m = Maze('''.#..
        ...             #.#.
        ...             ..#.
        ...             #...
        ...             .#.#''')
        >>> print(m.format(m.path(8)))
        .#.o
        #.#o
        oo#o
        #ooo
        .#.#
        >>> print(m.format(m.path(10)))
        ... # doctest: +IGNORE_EXCEPTION_DETAIL
        Traceback (most recent call last):
          ...
        NotFoundError: no path of length 10

    """
    def __init__(self, maze):
        self.matrix = [[c != '.' for c in line] for line in maze.split()]
        self.height = len(self.matrix)
        self.width = len(self.matrix[0])
        assert all(len(row) == self.width for row in self.matrix)

    def in_bounds(self, p):
        """Return True if `p` is a legal position in the matrix."""
        return 0 <= p[0] < self.width and 0 <= p[1] < self.height

    def empty(self, p):
        """Return True if `p` is an empty position in the matrix."""
        return not self.matrix[p[1]][p[0]]

    def neighbours(self, p):
        """Generate legal positions adjacent to `p`."""
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            q = p[0] + dx, p[1] + dy
            if self.in_bounds(q):
                yield q

    def path(self, n):
        """Find a path of length `n` in the maze, or raise NotFoundError if
        there is no such path.

        """
        path = []
        visited = set()
        def search(p):
            path.append(p)
            visited.add(p)
            if len(path) == n:
                raise Found()
            for q in self.neighbours(p):
                if self.empty(q) and q not in visited:
                    search(q)
            visited.remove(p)
            path.pop()
        try:
            for p in product(range(self.width), range(self.height)):
                if self.empty(p):
                    search(p)
        except Found:
            return path
        else:
            raise NotFoundError('no path of length {}'.format(n))

    def format(self, path=()):
        """Format the maze as a string. If optional argument path (an
        iterable) is given, highlight cells in the path.

        """
        path = set(path)
        def row(y):
            for x in range(self.width):
                p = x, y
                if not self.empty(p): yield '#'
                elif p in path: yield 'o'
                else: yield '.'
        return '\n'.join(''.join(row(y)) for y in range(self.height))

4. Extra credit: encapsulation of search state

In 2.18 above I discussed the need to update your search state properly when implementing a back-tracking search. As with any kind of data consistency problem, it's good practice to encapsulate operations that must be performed together.

An easy way to do this in Python is via a context manager. A "context manager" is just an object with __enter__ and __exit__ methods: when the context manager is the subject of a with statement, the __enter__ method is called on entry to the with statement, and the __exit__ method on exit. By putting your forward operations in the __enter__ method and the back-tracking operations in the __exit__ method you can be sure that these pair up properly.

But an even easier way to do this is to use contextlib.contextmanager to build the context manager for you, like this:

from contextlib import contextmanager

def path(self, n):
    """Find a path of length `n` in the maze, or raise NotFoundError if
    there is no such path.

    """
    path = []
    visited = set()

    @contextmanager
    def visit(p):
        path.append(p)       # Forward: add p to path.
        visited.add(p)       # Forward: mark p as visited.
        yield                # Rest of search happens here.
        visited.remove(p)    # Backtrack: mark p not visited.
        path.pop()           # Backtrack: remove p from path.

    def search(p):
        with visit(p):
            if len(path) == n:
                raise Found()
            for q in self.neighbours(p):
                if self.empty(q) and q not in visited:
                    search(q)
    try:
        for p in product(range(self.width), range(self.height)):
            if self.empty(p):
                search(p)
    except Found:
        return path
    else:
        raise NotFoundError('no path of length {}'.format(n))
\$\endgroup\$
  • 1
    \$\begingroup\$ It seems you forgot: if name == "main": import doctest doctest.testmod() \$\endgroup\$ – cat_baxter Mar 21 '13 at 11:37
  • 1
    \$\begingroup\$ I run doctests using python -mdoctest program.py, so the omission is deliberate on my part. But your comment might be helpful for the OP. \$\endgroup\$ – Gareth Rees Mar 21 '13 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.