Eulerian Tour

I suck at algorithms. Discrete math in general actually :) But you know, it’s working outside of your comfort zone what makes you progress, so I’m taking Udacity’s course on Algorithms.

One of the first assignments is to find an algorithm to find an eulerian tour and implement in Python. An eulerian tour is path that begins and ends on the same node of a graph and traverses all edges only once.

Well, is one of the first problems, so how difficult can it be, right?

After several notebook pages it turned out to be not that trivial (at least to me). I think I worked on it for a week and tried several different approaches “this can be solved using depth first search for sure…”, “maybe some recursion will help…”

Come on, it can't be that difficult
This is… madness!

Some approaches worked for simple graphs but failed when tested against bigger ones (20 nodes or so).

Then I thought again about the conditions a graph must fulfill in order to have an eulerian path: it must be connected and all the nodes must have even degree

I realised that this would happen if you construct a graph fusing several single loops together. The nodes belonging to only one single loop will have degree 2 (one in, one out), the nodes pertaining to two loops will have degree 4 (twice in and out), etc. In general the degree of a node is 2 * N (where N is the number of single loops it belongs to)

So i decided to write an iterative algorithm that looks for a single loop (A -> B -> C -> A), saves it, removes it from the graph, then looks for another loop on the remaining graph and so on. Until the graph is null, that is, no edges present.

Afterwards is just a matter (tricky code, though) of “piercing” the loops together by their common nodes.

The code is here:

# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]

################################################################
# Auxiliary
################################################################    

def get_degrees(edge_list):
    ''' This returns a dictionary of 
        nodes and their degrees '''

    degrees = dict()    
    for u, v in edge_list:
        degrees[u] = degrees.get(u, 0) + 1
        degrees[v] = degrees.get(v, 0) + 1

    return degrees

def get_highest_degree_node(edge_list):
    degrees =  get_degrees(edge_list)
    sorted_degrees = sorted(degrees, key = lambda k: degrees[k], reverse = True)

    return sorted_degrees[0]

def get_branches(edge_list, node):
    ''' Returns all nodes reachable from a node '''
    branches = []
    for u, v in edge_list:
        if u == node:
            branches.append(v)
        elif v == node:
            branches.append(u)
        else:
            pass

    degrees = get_degrees(edge_list)

    # Sort this by ascending degree
    # Meaning: lower degree nodes get visited earlier        
    return sorted(branches, key = lambda k: degrees[k])

def remove_branch(edge_list, current_node, branch):
    # Remove the branch, since it has been traversed already
    if ((current_node, branch)) in edge_list:
        edge_list.remove((current_node, branch))
    elif ((branch, current_node)) in edge_list:
        edge_list.remove((branch, current_node))
    else:
        pass

    return edge_list

def next_node(current_node, edge_list):
    ''' I don't need anything else 
        * where I am 
        * what is left unexplored 
        @return: new node '''

    branches = get_branches(edge_list, current_node)
    if branches != []:
        branch = branches[0]
        edge_list = remove_branch(edge_list, current_node, branch)
        return branch
    else:
        return None

def fusion_loop(original_list, element, new_element):
    ''' It fuses two loops by a common element '''
    idx = original_list.index(element)
    left = original_list[:idx]
    right = original_list[idx + 1:]

    new_list = left + new_element + right

    return new_list

def rotate_around(original_list, element):
    ''' It cycles the list so the cycle starts at element '''
    idx = original_list.index(element)
    if idx == 0:
        return original_list
    else:
        return original_list[idx:] + original_list[1:idx] + [element]

def find_common_element(list1, list2):
    ''' Returns the FIRST OCURRENCE of a common element '''
    for e1 in list1:
        if e1 in list2:
            return e1

    return None

################################################################
# The algorithm itself
################################################################

def find_eulerian_tour(edge_list, loops_list = []):

    while edge_list != []:

        branch = None    
        current_node = get_highest_degree_node(edge_list)
        nodes_visited = [current_node]

        print "\nStarting in node %d (degree: %d)..." % (current_node, get_degrees(edge_list)[current_node])

        while branch != nodes_visited[0]:
            branch = next_node(current_node, edge_list)
            nodes_visited.append(branch)
            current_node = branch

        loops_list.append(nodes_visited)

    ########################################################
    # Post-processing of loops_list
    print "loops_list:", loops_list
    eulerian_tour = loops_list[0] # kind of arbitrary
    loops_list.remove(loops_list[0])

    while loops_list != []:
        for loop in loops_list:
            common_node = find_common_element(eulerian_tour, loop)
            if common_node:
                cycled_loop = rotate_around(loop, common_node)
                eulerian_tour = fusion_loop(eulerian_tour, common_node, cycled_loop)
                loops_list.remove(loop)
                print "* eulerian_tour:", eulerian_tour

    return eulerian_tour

################################################################
# Tests
################################################################
def test(my_graph):
    print my_graph, "len:", len(my_graph)
    my_eulerian_tour =  find_eulerian_tour(my_graph)
    print my_eulerian_tour, "length:", len(my_eulerian_tour)

test([(1, 2), (2, 3), (3, 4), (4, 1), (2, 5), (5, 2)])
test([(1, 2), (2, 3), (3, 4), (4, 1), (2, 5), (5, 4), (4, 2)])    
test([(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)])
test([(1, 13), (1, 6), (6, 11), (3, 13), (8, 13), (0, 6), (8, 9),(5, 9), (2, 6), (6, 10), (7, 9), (1, 12), (4, 12), (5, 14), (0, 1),  (2, 3), (4, 11), (6, 9), (7, 14), (10, 13)])
test([(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)])
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s