graph.py

def searchGraph(graph,start,end):
    results=[]
    generatePath(graph,[start],end,results)
    results.sort(lambda x,y:cmp(len(x),len(y)))
    return results

def generatePath(graph,path,end,results):
    state=path[-1]
    if state == end:
        results.append(path)
    else:
        for arc in graph[state]:
            if arc not in path:
                generatePath(graph,path+[arc],end,results)


if __name__ == "__main__":
        Graph={
              'A':['B','C','D'],
              'B':['E'],
              'C':['D','F'],
              'D':['B','E','G'],
              'E':[],
              'F':['D','G'],
              'G':['E']
              }
        r = searchGraph(Graph,'A','D')
        print "A to D"
        for i in r:
            print i

        r=searchGraph(Graph,'A','E')
        print "A to E"
        for i in r:
            print i