# based on this:
# https://stackoverflow.com/questions/28518369/build-all-hamiltonian-paths-from-an-edge-list

graph = {
#   node: [list of allowed followers]
    1: [2, 3, 4, 6, 8, 9],   # Lost In The Brain
    2: [3, 4, 5, 10],   # Afraid Of The Dark
    3: [2, 4, 6, 8],         # Total Annihilation
    4: [3, 8, 9, 10],   # Humps
    5: [2, 3, 6, 7, 8, 10],       # U Break My Heart
    6: [1, 2, 3, 4, 5, 8, 10 ],   # Walking Home
    7: [1, 3, 4, 5, 8],      # Hey Last Night
    8: [1, 3, 9],         # Mellow Vibes
    9: [3, 5, 8, 10],   # O Oh
    10: [1, 3, 5, 9],      # Strawberry Wine
}

# allowed starting nodes
starts = [1, 2]


def find_all_paths(graph, start, totallen, path=[]):
    path = path + [start]
    if len(path) == totallen:
        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, totallen, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

cycles = []

for start in starts:
    print "Non-cyclic paths starting with", start
    paths = find_all_paths(graph, start, len(graph), [])
    for path in paths:
        first = path[0]
        last = path[-1]
        if first in graph[last]:
            cycles.append(path)
        else:
            print path

print "Cycles (duplicated for each start song):"
for cycle in cycles:
    print cycle