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
    return tour

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.

Answer 1

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
    return tour

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

Answer 2

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]

def remove_edge(raw_list, discard):
    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]

Answer 3

Here's a case your algorithm can't handle: the complete graph on 4 vertices. Sticking a print tour in there, you get:

>>> cg4 = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
>>> find_eulerian_tour(cg4)
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 0]
[0, 1, 2, 0, 3]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 1]
[etc.]

I'll leave you to find the problem with your approach -- you could easily google for a complete implementation, so since you didn't, I'm assuming you want the fun of figuring it out for yourself. :^)

Edit:

Hmmph. I admit I thought it was simply a missed failure case at the start. Anyway, @WolframH beat me to an updated example, but you could also look at the complete graph on 5 vertices, where your code gives

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

and misses the edges (2,3), (2,4), and (3,4).

Answer 4

The question can be solved easily than the above solutions using simple recursion.

def find_eulerian_tour(graph):
    tour=[]
    find_tour(graph[0][0],graph,tour)
    return tour
def find_tour(u,E,tour): 
  for (a,b) in E:
    if a==u:
        E.remove((a,b))
        find_tour(b,E,tour)
    elif b==u:
        E.remove((a,b))
        find_tour(a,E,tour)
  tour.insert(0,u)

This code works for any input list of tuples and returns a list of the tour. Pls send suggestions and changes if any. Thanks @WolframH:Your code doesn't work if any loop exists in the graph and the tuples are entered just to fail your code.