Eulerian Tour & Path

# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]

from collections import defaultdict
from random import choice
import itertools
def eulerian_tour(graph):
    tour=[]
    nodes=defaultdict(list)
    for s, e in graph:
        nodes[s].append(e)
        nodes[e].append(s)
    start = choice(nodes.keys())
    tour.append(start)
    while(len(nodes[start])>0):
        last = nodes[start].pop()
        tour.append(last)
        nodes[last].remove(start)
        start = last
    if list(itertools.chain(*nodes.values())):
        #print nodes
        for start in nodes:
            if start in tour and len(nodes[start])>0:
                index = tour.index(start)
                #print start, index, tour    
                while (len(nodes[start])>0):
                    last = nodes[start].pop()
                    nodes[last].remove(start)
                    index+=1
                    tour.insert(index, last)
                    start = last
                    #print tour
                    #print nodes
    return tour

graph = [(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)]
eulerian_tour(graph)


Test case
[(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)]
step 1 – create nodes
take (0,1) create 2 set, 0: [1], 1: [0]
take (1,5) create/append set, 0:[1] ,1:[0, 5],5:[1] …
{0: [1, 4], 1: [0, 5, 7, 6], 2: [4, 5], 3: [7, 6], 4: [5, 8, 2, 0], 5: [1, 4, 9, 2], 6: [1, 3], 7: [1, 3], 8: [4, 9], 9: [5, 8]})

step 2 – pick random key value, let us assume start node = 7, add start node in tour=[7]
a.find out 7: of last value in the list 7:[1,3] add the tour = [7, 3]
b.remove 7: of [3]  and 3: of 7
so the list will be like: {0: [1, 4], 1: [0, 5, 7, 6], 2: [4, 5], 3: [6], 4: [5, 8, 2, 0], 5: [1, 4, 9, 2], 6: [1, 3], 7: [1], 8: [4, 9], 9: [5, 8]})

last added tour = 3
a.find out 3: of last value in the list 6, add node in tour = [7, 3, 6]
b.remove 3: of [6] and 6: of [3]
so the list will be like: {0: [1, 4], 1: [0, 5, 7, 6], 2: [4, 5], 3: [], 4: [5, 8, 2, 0], 5: [1, 4, 9, 2], 6: [1], 7: [1], 8: [4, 9], 9: [5, 8]})

repeat until nodes list is empty, if not empty

step3
a.take first list key value [0], check it in tour[0] not in [7, 3, 6, 1, 7]
b.move next key [1], check it in tour[1] in [7, 3, 6, 1, 7], find index 3
c. start node = 1
d.find out 1: of last value in the list [0,5], add the tour next to index value [7, 3, 6, 1, 5, 7]
d.remove 1: of [5] and 5: of [1] ,  {0: [1, 4], 1: [0], 2: [4, 5], 3: [], 4: [5, 8, 2, 0], 5: [4, 9, 2], 6: [], 7: [], 8: [4, 9], 9: [5, 8]})
c.last added tour = 5, repeat until reach end of key value
then move next key [2], … until reach all the nodes
final result => tour  is [7, 3, 6, 1, 5, 2, 4, 8, 9, 5, 4, 0, 1,  7]

#create tour for the given nodes
def create_tour(nodes):
    n = len(nodes) - 1
    return [(nodes[i], nodes[i + 1]) for i in range(-1, n)]
nodes = [1,2,3,4,5]
tour = create_tour(nodes)
#(1,2),(2,3),(3,4),(4,5)(5,1)
#The method get() returns a value for the given key.
#If key is not available then returns default value None.

#sum of nodes both start and end
#{1: 2, 2: 2, 3: 2, 4: 2, 5: 2}
def get_degree(tour):
    degree = {}
    for x, y in tour:
        degree[x] = degree.get(x, 0) + 1
        degree[y] = degree.get(y, 0) + 1
    return degree

# b 1 
# t (1, 2), match, return 2
# t (2, 3)
# t (5, 1), match, return 5
def check_edge(t, b, nodes):
    if t[0] == b:
        if t[1] not in nodes:
            return t[1]
    elif t[1] == b:
        if t[0] not in nodes:
            return t[0]
    return None

"""
b    nodes        explore
1 => [1]          [1]
1 => [1,2,5]      [5,2]
2 => [1,2,3,5]    [5,3]  
3 => [1,2,3,4,5]  [5,4]
4 => [1,2,3,4,5]  [5]
5 => [1,2,3,4,5]  []
"""
def connected_nodes(tour):
    a = tour[0][0]
    nodes = set([a])
    explore = set([a])
    while len(explore) > 0:
        b = explore.pop()
        for t in tour:
            node = check_edge(t, b, nodes)
            if node is None:
                continue
            nodes.add(node)
            explore.add(node)
    return nodes

def is_eulerian_tour(nodes, tour):
    # all nodes must be even degree
    # and every node must be in graph
    degree = get_degree(tour)
    for node in nodes:
        try:
            d = degree[node]
            #rint d, node
            if d % 2 == 1:
                print "Node %s has odd degree" % node
                return False
        except KeyError:
            print "Node %s was not in your tour" % node
            return False
    connected = connected_nodes(tour)
    if len(connected) == len(nodes):
        return True
    else:
        print "Your graph wasn't connected"
        return False

nodes = [1,2,3,4,5]
tour = create_tour(nodes)
return is_eulerian_tour(nodes, tour)
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: