eulerian_tour.py

def tour(nodes, graph):
    print ">>", nodes, graph

    if len(nodes) == 0:
        return []

    if len(graph) == 0:
        return nodes

    start_node = nodes[-1]

    for i in range(len(graph)):
        # print i, graph
        edge = graph[i]
        if not start_node in edge:
            continue

        g2 = graph[:]
        g2.pop(i)
        if edge[0] == start_node:
            next_node = edge[1]
        else:
            next_node = edge[0]

        n2 = nodes[:]
        n2.append(next_node)

        t = tour(n2, g2)
        if t:
            return t

    # print "dead end"
    return []


def find_eulerian_tour(graph):
    # your code here
    nodes={}
    for a, b in graph:
        if nodes.has_key(a):
            nodes[a] += 1
        else:
            nodes[a] = 1
        if nodes.has_key(b):
            nodes[b] += 1
        else:
            nodes[b] = 1

    odd_degree_nodes = []
    for n in nodes:
        d = nodes[n]
        if d%2 != 0:
            odd_degree_nodes.append(n)

    if len(odd_degree_nodes) not in [0, 2]:
        print "no eulerian tour"
        return []

    start_node = graph[0][0]
    end_node = start_node
    if len(odd_degree_nodes) == 2:
        start_node, end_node = odd_degree_nodes

    # print start_node, end_node

    visited = [start_node]
    return tour(visited, graph)

if __name__ =="__main__":
    edges = [(1, 2), (2, 3), (3, 1)]
    print find_eulerian_tour(edges)