Depth-first searching a 2D list

dfs.py

'''
Depth-first searching a 2D list

a  |  b  |  c  |  d
--------------------
e  |  f  |  g  |  h
--------------------
i  |  j  |  k  |  l
--------------------
m  |  n  |  o  |  p

Find all paths from a to p by only using down and right
movements.

Example:
["aeimnop", "abcdhlp", "abfgklp", ...]

        a
      /   \
    e       b
  /   \   /   \
 i      f      c
 ...

'''


class Graph:

    def __init__(self):
        # Maybe defaultdict?
        self.vertices = dict()

    def add_vertex(self, vertex):
        self.vertices[vertex] = []

    def add_edge(self, from_vertex, to_vertex):
        if from_vertex not in self.vertices:
            self.add_vertex(from_vertex)
        self.vertices[from_vertex].append(to_vertex)

    def find_path(self, from_vertex, to_vertex, path=[], paths=[]):
        path.append(from_vertex)

        if from_vertex == to_vertex:
            paths.append(path[:])
        else:
            for neighbor in self.vertices.get(from_vertex):
                if neighbor not in path:
                    self.find_path(neighbor, to_vertex, path, paths)

        path.pop()
        if len(path) < 1:
            return paths


if __name__ == '__main__':
    # Test case two-dimensional list
    source_list = [['a', 'b', 'c', 'd'],
                   ['e', 'f', 'g', 'h'],
                   ['i', 'j', 'k', 'l'],
                   ['m', 'n', 'o', 'p']]

    # Initialize graph
    g = Graph()

    # Add vertices
    for j in xrange(len(source_list)):
        row_length = len(source_list[j])
        for i in xrange(len(source_list[j])):
            # Add vertex
            vertex = source_list[j][i]
            g.add_vertex(vertex)

            # Add right neighbor
            if i + 1 < row_length:
                g.add_edge(vertex, source_list[j][i + 1])

            # Add lower neighbor
            if j + 1 < len(source_list):
                g.add_edge(vertex, source_list[j + 1][i])

    paths = g.find_path('a', 'p', path=[], paths=[])
    print [p for p in paths]