find_eulerian_tour.py

import random

graph = [(8, 16), (8, 18), (16, 17), (18, 19), (3, 17), (13, 17), (5, 13),(3, 4), (0, 18), (3, 14), (11, 14), (1, 8), (1, 9), (4, 12), (2, 19), (1, 10), (7, 9), (13, 15), (6, 12), (0, 1), (2, 11), (3, 18), (5, 6), (7, 15), (8, 13), (10, 17)]
traversal = []

def build_connections(graph):
    flattened_nodes = [node for edge in graph for node in edge]# [1, 2, 2, 3, 3, 1]
    unique_nodes = list(set(flattened_nodes))# [1, 2, 3]
    connections = dict()

    # init the dictionary with keys corresponding to empty lists
    for node in unique_nodes:
        connections[node] = list()
        # {1: [], 2: [], 3: []}

    # buildup connections bidirectionally
    for edge in graph:
        connections[edge[0]].append(edge[1])
        connections[edge[1]].append(edge[0])
        # {1: [2, 3], 2: [1, 3], 3: [2, 1]}

    return connections

def find_eulerian_tour(graph):
    # create the connections so we know what are valid paths
    connections = build_connections(graph)
    temp_traversal = []

    # pick a random starting node and save it.
    start_node = random.choice(connections.keys())
    temp_traversal.append(start_node)

    node = start_node

    while len(connections[node]) > 0:
        to_node = random.choice(connections[node])
        temp_traversal.append(to_node)
        connections[node].remove(to_node)
        connections[to_node].remove(node)

        node = to_node

    if len(temp_traversal) == len(graph) + 1:
        traversal = temp_traversal
        print "success!", traversal
        return traversal
    else:
        print "YOU SUCK", temp_traversal
        find_eulerian_tour(graph)


find_eulerian_tour(graph)