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…”

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)])