# Finding a Eulerian Tour

### Question

I am trying to solve a problem on Udacity described as follows:

``````# 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]
``````

I came up with the following solution, which, while not as elegant as some of the recursive algorithms, does seem to work within my test case.

``````def find_eulerian_tour(graph):
tour = []

start_vertex = graph[0][0]
tour.append(start_vertex)

while len(graph) > 0:
current_vertex = tour[len(tour) - 1]
for edge in graph:
if current_vertex in edge:
if edge[0] == current_vertex:
current_vertex = edge[1]
elif edge[1] == current_vertex:
current_vertex = edge[0]
else:
# Edit to account for case no tour is possible
return False

graph.remove(edge)
tour.append(current_vertex)
break

graph = [(1, 2), (2, 3), (3, 1)]
print find_eulerian_tour(graph)

>> [1, 2, 3, 1]
``````

However, when submitting this, I get rejected by the grader. I am doing something wrong? I can't see any errors.

1
7
3/19/2016 1:39:40 PM

Here's a valid case where your algorithm fails:

``````graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
``````

Use the power of `print` to find out what happens to `graph` and `current_vertex`.

Another hint: Move the `else` down so that it belongs to the `for` and is executed when the `for` loop is not broken. As it is now, it can never be executed. After that correction, the algorithm still fails, of course.

The algorithm still fails, of course.

The algorithm still fails, of course.

Please, don't comment stating that the code doesn't work. It doesn't. The algorithm still fails, even if the code below does what the OP had in mind. The point was to show that the OP's algorithm is wrong, which the OP couldn't determine. For that, a correct implementation of OP's algorithm is needed (see below). A correct implementation of a wrong algorithm is still not a correct solution.

I'm sorry to make this answer worse by writing all these lengthy explanations, but people continue to complain that the code doesn't work (of course, the point was to show that it is wrong). They also downvote this answer, probably because they expect to be able to copy the code as a solution. But this is not the point, the point is to show to the OP that there is an error in his algorithm.

The code below does not find eulerian tours. Look elsewhere to copy code for passing your assingments!

``````def find_eulerian_tour(graph):
tour = []

current_vertex = graph[0][0]
tour.append(current_vertex)

while len(graph) > 0:
print(graph, current_vertex)
for edge in graph:
if current_vertex in edge:
if edge[0] == current_vertex:
current_vertex = edge[1]
else:
current_vertex = edge[0]

graph.remove(edge)
tour.append(current_vertex)
break
else:
# Edit to account for case no tour is possible
return False

graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
print(find_eulerian_tour(graph))
``````

Output:

``````[(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)] 1
[(2, 3), (3, 1), (3, 4), (4, 3)] 2
[(3, 1), (3, 4), (4, 3)] 3
[(3, 4), (4, 3)] 1
False
``````
9
2/16/2017 4:35:26 PM

I'm also in the same lecture, WolframH's answer doesn't work for me. Here is my solution (has been accepted by the grader):

Push all possible `next node` into a heap(`search`) then search each one of them while recording.

``````def next_node(edge, current):
return edge[0] if current == edge[1] else edge[1]

return [item for item in raw_list if item != discard]

def find_eulerian_tour(graph):
search = [[[], graph[0][0], graph]]
while search:
path, node, unexplore = search.pop()
path += [node]

if not unexplore:
return path

for edge in unexplore:
if node in edge:
search += [[path, next_node(edge, node), remove_edge(unexplore, edge)]]

if __name__ == '__main__':
graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
print find_eulerian_tour(graph)
``````

[1, 3, 4, 3, 2, 1]