Compare two methods of listing all paths between two nodes in a graph

list_all_paths.py

#!/usr/bin/env python

import timeit

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

def makegraph(nodes) :
    import random
    G, rng = {}, range(nodes)
    for i in rng :
        G[str(i + 1)] = [str(j+1) for j in rng if i != j and random.random() > 0.75]

    return G

def showgraph(G) :
    for node in G :
        print node, '::',
        for k in G[node] :
            print k,
        print

def find_all_paths(G, start, end, visited = []) :
    for i in G[start] :
        if i not in visited :
            if i == end :
                yield [start] + [i]
            else :
                for j in find_all_paths(G, i, end, visited + [start]) :
                    yield [start] + j

def gfind_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

if __name__ == '__main__' :
    G = makegraph(17)
    showgraph(G)
    frm, to = '14', '2'
    print '******Recursive Version'
    t = timeit.Timer('for n,i in enumerate(find_all_paths(G, frm, to)) :	pass', 'from __main__ import find_all_paths, G, frm, to')
    print t.timeit(number=10)
    print '******Guido\'s version'
    t = timeit.Timer('for n,i in enumerate(gfind_all_paths(G, frm, to)) :	pass', 'from __main__ import gfind_all_paths, G, frm, to')
    print t.timeit(number=10)