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

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.

Answer 3

Though the code fails for Undirected graphs but runs perfectly well with directed ones. How ever it still doesn't solve the problem at hand from Udacity's side but can be treated as a lower version of the same. Please don't mind the badly used Python as I am still new to the language.

---

Two test scenarios of fairly good level of complexity added at the bottom.

---

initialNode = ''
nglength = 0
in_graphLength = 0
normalizedGraph = list()
path = []
node_dict = {}
mod_flag = ''

def find_eulerian_tour(graph):
    global in_graphLength
    in_graphLength = len(graph)
    graph = normalize_graph(graph,[],-1,len(graph))
    print (path)
    return path
def normalize_graph(graph,nG,remNode,length):
    counter = 0
    global path
    global initialNode
    global in_graphLength
    global nglength
    global normalizedGraph
    localGraph = list()
    path = []
    pathList = []
    if(remNode != -1):
        normalizedGraph = nG
    baseNode = 0
    if(len(normalizedGraph) != 0):
        ini1, ini2 = normalizedGraph[0]
        initialNode = ini1
        a1,b1 = normalizedGraph[len(normalizedGraph) - 1]
        baseNode = b1
        if(remNode != -2):
            graph.pop(remNode)
    if(remNode == -1):
        a,b = graph[0]
        baseNode = b
        normalizedGraph.append(graph[0])
        initialNode = a
        nglength = 1
        graph.pop(0)
    i = 0
    if(len(graph) != 0):
        for n1, n2 in graph:
            i = i + 1
            if(n1 == baseNode):
                localGraph = graph[:]
                if(isJunction((n1,n2),localGraph, nglength)):
                    graph.pop(i-1)
                    graph.append((n1,n2))
                    normalize_graph(graph, normalizedGraph, -2,in_graphLength)
                    break
                else:
                    normalizedGraph.append((n1, n2))
                    nglength = nglength + 1
                    normalize_graph(graph, normalizedGraph, i - 1,in_graphLength)
                    break

    else:
        if( counter == 0):
            counter = counter + 1
            a0, b0 = normalizedGraph[0]
            for n1, n2 in normalizedGraph:
                path.append(n1)
            path.append(a0)
            path = path
            return path

def isJunction((n1,n2), graph, nglength):
    global node_dict
    count = 0
    if(len(graph) > 1):
        for a1, a2 in graph:
            if (n1 == a1):
                count = count + 1
        if (count > 1):
            if(str(n1) not in node_dict):
                key = str(n1)
                node_dict[key] = count
            else:
                return handle_degree(n1)
            return modification_needed((n1, n2), graph, nglength)
        else:
            return False
    else:
        return False

def handle_degree(n1):
    global node_dict
    key = str(n1)
    if(node_dict.get(key) == 2):
        return False

def modification_needed((n1,n2),graph, tmplength):
    i = 0
    global mod_flag
    if( n2 == initialNode):
        return True
    if(len(graph) > 1):
        for b1, b2 in graph:
            if(n2 == b1):
                i = i + 1
                tmplength = tmplength + 1
                if (b1,b2) in normalizedGraph:
                    mod_flag = True
                    continue
                if(tmplength < in_graphLength and b2 == initialNode):
                    mod_flag = True
                    continue
                else:
                    graph.pop(i-1)
                    modification_needed((b1,b2),graph,tmplength)
    return mod_flag


#find_eulerian_tour([(1,2),(2,6),(7,2),(6,1),(2,3),(3,5),(3,4),(4,5),(5,7),(7,3),(5,6),(6,7)])
#find_eulerian_tour([(0,4),(1,0),(4,2),(4,8),(2,5),(9,5),(8,9),(5,4),(5,1),(7,1),(3,7),(1,6),(6,3)])

Answer 4

What if we do this? ( just checked and it passed udacity test!!)

import itertools
def create_tour(alist):
    return list(itertools.permutations(alist,2))