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