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 is the original code in Gregor Ulm's webpage and it works.

def find_eulerian_tour(graph):

def freqencies():
    # save all nodes of edges to my_list
    # e.g. [3,4,5,1,2,2,3,5]
    my_list = [x for (x, y) in graph]
    # get the max num of nodes-->create a list
    # set all to 0
    # for i in range(5) = 0 1 2 3 4
    # so range("5" +1) means
    # len=6, result=[0,0,0,0,0,0]
    # so that the index = the number itself
    result = [0 for i in range(max(my_list) + 1)]
    # nodes in my_list, increment
    # e.g. [0,1,2,2,1,2] 
    # 3appears 2times.
    for i in my_list:
        result[i] += 1
    return result
    # this is Frequencies of each nodes.

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)
        # get the sub_path
        # add them together
        # when draw to u, turn to sub, and then come back to go on the original tour path
        # [:a], start to a; [a+1:] a+1 to end
        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:
            # from "double-graph"
            # pop out the current one and its respondent one
            # actually it means we delete this edge
            current = graph.pop(graph.index((x,y)))
            graph.pop(graph.index((current[1], current[0])))
            # now add this "next" node into the tour
            tour.append(current[0])
            # decrement in frequency
            freq[current[0]] -= 1
            freq[current[1]] -= 1
            return find_path(tour, current[1])
    # if this "next" node is not connected to any other nodes
    # single one
    tour.append(next)
    return tour             

# in graph, all edges get reversed one and be added to graph
# can call it "double-graph"  
# it helps to calculate the frequency in find_path
# actually we can regard frequency as degrees for each node       
graph += [(y, x) for (x, y) in graph]
freq = freqencies()   
# set graph[0][0] as starting point
return helper([], graph[0][0])

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

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

You can mimic the behavior of BFS algorithm and piggyback on it.

Note: I haven't tried write the answer using linked lists because linked lists requires defining 2 classes (one to define nodes and their behaviors, and one to define the entire linked list and its behaviors). However, for more efficiency in (append) and (remove) behaviors, you should use linked lists instead of arrays :

def find_eulerian_tour(graph):
    nodes = set()

    for i in graph:
        if not i[0] in nodes:
            nodes.add(i[0])
        if not i[1] in nodes:
            nodes.add(i[1])

    tour = []
    tempstack = []
    graphtemp = []

    current_vertex = graph[0][0]
    tour.append(current_vertex)
    tempstack.append(current_vertex)
    last_edge = ()
    count = 0

    while len(set(tempstack)) + 1 < len(nodes) or (count == 0 or tour[0] != tour[len(tour) - 1]):
        count += 1
        flag = False
        for edge in graph:
           if current_vertex in edge and edge != last_edge:
                if current_vertex == edge[0]:
                    current_vertex = edge[1]
                else:
                    current_vertex = edge[0]
                last_edge = edge
                graphtemp.append(edge)
                graph.remove(edge)
                tour.append(current_vertex)
                tempstack.append(current_vertex)
                flag = True
                break

        if flag == False:
            tour.remove(current_vertex)
            current_vertex = tempstack[0]
            tempstack.remove(tempstack[0])
            graph.append(graphtemp[0])
            graphtemp.remove(graphtemp[0])


    return tour


print find_eulerian_tour([(1,2), (2,3), (3,1)])
print(find_eulerian_tour([(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)]))
print(find_eulerian_tour([(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)]))
print(find_eulerian_tour([(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)]))

Answer 4

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 5

This solution is optimized for O(V+E) complexity i.e. linear in number of Edges and Vertices in the graph

For those directly wishing to see the code: https://github.com/cubohan/py-algos/blob/master/eulerian_tour.py

Note that the code breaches readability and DRY design majorly but after reading the explanation, you can easily churn out your own version.

# eulerian_tour.py by cubohan
# circa 2017
#
# Problem statement: Given a list of edges, output a list of vertices followed in an eulerian tour
#
# complexity analysis: O(E + V) LINEAR


def find_eulerian_tour(graph):
    edges = graph
    graph = {}
    degree = {}
    start = edges[0][0]
    count_e = 0
    for e in edges:
        if not e[0] in graph:
            graph[e[0]] = {}
        if not e[0] in degree:
            degree[e[0]] = 0
        if not e[1] in graph:
            graph[e[1]] = {}
        if not e[1] in degree:
            degree[e[1]] = 0
        graph[e[0]][e[1]] = 1
        graph[e[1]][e[0]] = 1
        degree[e[0]] += 1
        degree[e[1]] += 1
        count_e += 1
    max_d = 0
    this_ = 0
    for v, d in degree.items():
        if not d%2 == 0:
            # Eulerian tour not possible as odd degree found!
            return False 
        if d>max_d:
            this_ = v
            max_d = d
    visited_e = {}
    def is_visited(i, j):
        key = str(sorted([i,j]))
        if key in visited_e:
            return True
        else:
            visited_e[key] = True
            return False
    start = this_
    route = [start]
    indexof = {}
    indexof[start] = 0
    while count_e>0:
        flag = False
        for to_v in graph[this_]:
            if not is_visited(to_v, this_):
                route.append([to_v])
                indexof[to_v] = len(route)-1
                degree[to_v] -= 1
                if degree[to_v] == 0:
                    del degree[to_v]
                degree[this_] -= 1
                if degree[this_] == 0:
                    del degree[this_]
                this_ = to_v
                flag = True
                count_e -= 1
                break
        if not flag:
            break
    for key, v in degree.items():
        if v <=0:
            continue
        try:
            ind = indexof[key]
        except Exception as e:
            continue
        this_ = key
        while count_e>0:
            flag = False
            for to_v in graph[this_]:
                if not is_visited(to_v, this_):
                    route[ind].append(to_v)
                    degree[to_v] -= 1
                    degree[this_] -= 1
                    this_ = to_v
                    flag = True
                    count_e -= 1
                    break
            if not flag:
                break
    route_ref = []
    for r in route:
        if type(r) == list:
            for _r in r:
                route_ref.append(_r)
        else:
            route_ref.append(r)
    return route_ref

if __name__ == "__main__":
    print find_eulerian_tour([(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)])

**First the problem can be divided into these subtasks: **

1. Build the graph into a more friendly structure than a list of edges for easier processing i.e (Adjacency Lists)

2. Find the degrees of each vertex to first check if an Eulerian Tour is possible (Are there only even degrees? Also, STORE these values in a dict with vertex as key => to be used later)

3. Build the Eulerian tour

The concept behind my solution is simple.

1. You choose the vertex with the highest degree as a starting point and set it as the current vertex. (Note: You accomplish this at the same time while calculating degrees of every vertex. You store all these degrees in a dictionary.)

2. You insert current vertex in the route list which is your answer (Note: also make a dictionary of vertices and their indexes in the route list. This will be used later.)

3. You visit the first edge of the current vertex if it's not already visited. (Note: A dictionary of visited edges is maintained, the key to this dict is a sorted tuple of the pair of vertices constituting the edge. After visiting an edge, mark it visited by inserting it into the dict.)

4. You maintain a count of degrees remaining of the current vertex and the visited vertex (This will prove useful later) (Note: you only need to subtract 1 from the dict of degrees you generate before each time you choose an edge)

5. You switch current vertex to the vertex on the other end of the edge you decided to visit.

6. Repeat steps 2-5 until you can't find an unvisited edge in the current vertex. (Note: this means you have returned to your starting vertex)

Now consider this: Notice that any unvisited edges/vertices will constitute subgraphs in the main graph which have the same properties as the main graph i.e. an Eulerian tour is possible from any of the vertices in the subgraph starting and ending at the same vertex.

All unvisted edges can be thus visited by taking Eulerian tours in these subgraphs You just need to merge these sub-tours with the first tour.

Next:

1. You loop through all the vertices of the graph and build a subtour in the same process as listed for the main tour if and only if the reduced degree of this vertex is non-zero

2. The way these tours will merge with the route list computed previously is that you replace the position of the vertex you're considering to start a subtour from in the route list with the subtour output list and later flattening this route list

We're still not done! What's wrong above?

What happens when you get a non-zero degree vertex which HASN'T BEEN VISITED and isn't present in the route list?!

A caveat: This is an exceptional case.

You might encounter vertices not visited before and thus they will not be present in the main route list.

IGNORE THESE while looping! One of the vertices you have already visited with non-zero reduced degree is GUARANTEED to lead to these vertices in the subtour you will create starting from those.

How is that possible??!!

Draw a graph from the test case given in the link to the code and you will understand. Trace out what your algo is doing every step of the process. Draw it! An image is log(N) complexity to understanding and words O(n2).

Ah, and note that this guarantee holds only if all the edges in the input list form a single graph and not two separate disjointed graphs.

Answer 6

I was going through the same course on Udacity. And I implemented Hierholzer's algorithm after reading it from Wikipedia. Here is the link to algorithm https://en.wikipedia.org/wiki/Eulerian_path

And below is my code. No doubt, it got accepted by the grader(after doing some Python3 to Python2 changes). :)

#!/usr/bin/env python3
# Find Eulerian Tour
#
# Write a program 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]

def get_a_tour():
    '''This function returns a possible tour in the current graph and removes the edges included in that tour, from the graph.'''
    global graph

    nodes_degree = {}       # Creating a {node: degree} dictionary for current graph.
    for edge in graph:
        a, b = edge[0], edge[1]
        nodes_degree[a] = nodes_degree.get(a, 0) + 1
        nodes_degree[b] = nodes_degree.get(b, 0) + 1

    tour =[]        # Finding a tour in the current graph.
    loop = enumerate(nodes_degree)
    while True:
        try:
            l = loop.__next__()
            index = l[0]
            node = l[1]
            degree = nodes_degree[node]
            try:
                if (tour[-1], node) in graph or (node, tour[-1]) in graph:
                    tour.append(node)
                    try:
                        graph.remove((tour[-2], tour[-1]))
                        nodes_degree[tour[-1]] -= 1     # Updating degree of nodes in the graph, not required but for the sake of completeness.
                        nodes_degree[tour[-2]] -= 1     # Can also be used to check the correctness of program. In the end all degrees must zero.
                    except ValueError:
                        graph.remove((tour[-1], tour[-2]))
                        nodes_degree[tour[-1]] -= 1
                        nodes_degree[tour[-2]] -= 1
            except IndexError:
                tour.append(node)
        except StopIteration:
            loop = enumerate(nodes_degree)

        if len(tour) > 2:
            if tour[0] == tour[-1]:
                return tour

def get_eulerian_tour():
    '''This function returns a Eulerian Tour for the input graph.'''
    global graph
    tour = get_a_tour()

    if graph:   # If stuck at the beginning, finding additional tour in the graph.
        loop = enumerate(tour[: -1])
        l = loop.__next__()
        i = l[0]
        node = l[1]
        try:
            while True:
                if node in list(zip(*graph))[0] or node in list(zip(*graph))[1]:
                    t = get_a_tour()    # Retreivng the additional tour
                    j = t.index(node)
                    tour = tour[ : i] + t[j:-1] + t[ :j+1] + tour[i+1: ]        # Joining the two tours.
                    if not graph:       # Found Eulerian Tour
                        return tour     # Returning the Eulerian Tour
                    loop = enumerate(tour[: -1])        # Still stuck? Looping back to search for another tour.
                l = loop.__next__()
                i = l[0]
                node = l[1]
        except StopIteration:   # Oops! seems like the vertices in the current tour cannot connect to rest of the edges in the graph.
            print("Your graph doesn't seem to be connected")
            exit()
    else:       # Found the Eulerian Tour in the very first call. Lucky Enough!
        return tour

# Sample inputs
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6)]
# graph = [(1, 2), (1, 3), (2, 3)]
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6), (9, 10), (10, 11), (11, 9)]
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6), (2, 7), (7, 8), (8, 2)]
# graph = [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (4, 6), (1, 5), (5, 6), (1, 6)]
# graph = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 3)]
# graph = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
# graph = [(2, 6), (4, 2), (5, 4), (6, 5), (6, 8), (7, 9), (8, 7), (9, 6)]

# creating a {node: degree} dictionary
nodes_degree = {}
for edge in graph:
    a, b = edge[0], edge[1]
    nodes_degree[a] = nodes_degree.get(a, 0) + 1
    nodes_degree[b] = nodes_degree.get(b, 0) + 1

#checking degree
degrees = nodes_degree.values() # remember it return a view
for degree in degrees:
    if degree % 2:
        print("Your graph have one or more nodes with odd degrees. Hence an Eulerian Tour is impossible.")
        exit()

#finding Eulerian Tour
tour = get_eulerian_tour()
print(tour)

Hope this helps.