In Udacity’s Introduction to Algorithms course, one of the challenge problems asks you to define a function that, given a graph that contains an Eulerian path, returns one such path. I’ve reproduced my solution below. The solutions posted on the Udacity forum where often in two camps: somewhat verbose imperative, and very concise functional ones that implemented Hierholzer’s algorithm for finding cycles in Eulerian paths. My solution is somewhat in the middle. It’s relatively concise, but it makes use of an additional data structure I found helpful as it allows to easily inspect the state during program execution: a list containing the number of unused edges per node. I think it’s quite easy to follow the flow of execution, but I’ll walk you through step by step afterwards.
Here is the program listing:
def find_eulerian_tour(graph):
def freqencies():
my_list = [x for (x, y) in graph]
result = [0 for i in range(max(my_list) + 1)]
for i in my_list:
result[i] += 1
return result
def find_node(tour):
for i in tour:
if freq[i] != 0:
return i
return -1
def helper(tour, next):
find_path(tour, next)
u = find_node(tour)
while sum(freq) != 0:
sub = find_path([], u)
tour = tour[:tour.index(u)] + sub + tour[tour.index(u) + 1:]
u = find_node(tour)
return tour
def find_path(tour, next):
for (x, y) in graph:
if x == next:
current = graph.pop(graph.index((x,y)))
graph.pop(graph.index((current[1], current[0])))
tour.append(current[0])
freq[current[0]] -= 1
freq[current[1]] -= 1
return find_path(tour, current[1])
tour.append(next)
return tour
graph += [(y, x) for (x, y) in graph]
freq = freqencies()
return helper([], graph[0][0])
The graph is given as a list of tuples. Tuple (x, y) indicates that node x has an (undirected) edge to node y. In line 37 the list with nodes is enlarged by adding tuples (y, x) to it, which reflects the fact that the edges are undirected.
In addition, a list of the number of edges per node (“freq”) is created and updated as the list with the eventual Eulerian tour is built. This means that whenever a node that is part of the Eulerian tour is found, the two affected nodes have their number of edges reduced by one.
If the graph has cycles, it is possible that the first pass of find_path() doesn’t process part of the graph. In this case, the program checks whether the sum of the list “freq” is equal to zero. If it is, then the Eulerian tour has been computed since there are no unused edges left. On the other hand, if “sum(freq)” is greater than zero, then unused edges are left, so the program proceeds finding a node with unused edges, finds another cycle, and inserts it into the resulting Eulerian tour. This step will be repeated for as long as there are unused edges in the graph.
Please note that any node can be used as a staring point. This follows from the existence of an Eulerian path, which uses all edges. Since it contains all edges, you can pick any node and from there pick any edge to start the Eulerian tour with.
On the Udacity forums I found a very helpful test case, which is a graph with three cycles. When working on the program, I used this and two derivative cases to test and guide development. Here they are:
graph1 = [(0, 1), (1, 2), (2, 0)] # returns [0, 1, 2, 0] graph2 = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)] # returns [0, 1, 2, 3, 4, 2, 0] graph3 = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2), (4, 5), (5, 6), (6, 4)] # returns [0, 1, 2, 3, 4, 5, 6, 4, 2, 0]
