Hierholzer's algorithm for finding Eulerian Cycle Python

Question

I am a beginner at Graph theory. I've been trying to implement Hierholzer's algorithm into code using Python since 5 days. My experience with graph theory is also 5 days so far. My codes are below:

def cycle(D1):
    import random
    key = list(D1.keys())
    ran_k = random.choice(key)
    tmp_stk = []
    tmp_stk += [ran_k]
    r_stack = []
    if len(D1[ran_k]) > 1:
        tmp_stk += [D1[ran_k][0]]
        del D1[ran_k][0]
    else:
        tmp_stk += D1[ran_k]
        del D1[ran_k]
   flag = True
   while flag:
       try:
           if len(D1[tmp_stk[-1]]) > 1:
              tmp_stk += [D1[tmp_stk[-1]][0]]
              del D1[tmp_stk[-2]][0]
           else:
              tmp_stk += D1[tmp_stk[-1]]
              del D1[tmp_stk[-2]]
       except (KeyError):
            flag = False
            return D1,tmp_stk

def stack(tmp_stk,D1):
    r_stack = []
    if len(D1):
        for i in tmp_stk[::-1]:
            if i in D1.keys():
                 r_stack += tmp_stk[tmp_stk.index(i)+1:][::-1]
                 tmp_stk = tmp_stk[:tmp_stk.index(i)+1]
        return tmp_stk,r_stack
    else:
        r_stack += [tmp_stk[::-1]]
        return tmp_stk,r_stack

def cycle2(D1,tmp_stk):
    flag = True
    while flag:
        try:
           if len(D1[tmp_stk[-1]]) > 1:
              tmp_stk += [D1[tmp_stk[-1]][0]]
              del D1[tmp_stk[-2]][0]
           else:
              tmp_stk += D1[tmp_stk[-1]]
              del D1[tmp_stk[-2]]
        except (KeyError):
             flag = False
      return D1,tmp_stk

D2 = {0:[3],1:[0],2:[1,6],3:[2],4:[2],5:[4],6:[5,8]
     , 7:[9],8:[7],9:[6]}

D2 graph is connected and each node has even degree. My code(cycle function) works fine when ran_k selects 6 as starting node and Eulerian circuit is [6, 5, 4, 2, 1, 0, 3, 2, 6, 8, 7, 9, 6]. Any starting node has Eulerian circuit as D2 graph is strongly connected and all nodes has even degree.

When ran_k selects 0 as starting node,my cycle function returns like: Remaining graph : {2: [6], 4: [2], 5: [4], 6: [5, 8], 7: [9], 8: [7], 9: [6]} and temporary stack as: [0, 3, 2, 1, 0]. This is also okay because I know I have to run cycle2 and stack function over these outputs of cycle function. I can solve this on my paper but I don't know how to use these functions using a while loop checking length of D2 is zero or length of tmp_stk 0. I would be so glad to see your suggestions.

score 0 · Answer 1 · answered Feb 19 '16 at 18:26

Add this function at the end:

def main(D):
d,ts = cycle(D)
if len(d):
    #flag = True
    r_s = []
    while len(d):
          #r_s = []
          ts,rs1,d = stack(ts,d)
          r_s += rs1
          d,ts = cycle2(d,ts)
    circle =  r_s+ts[::-1]
    return circle[::-1]
else:
    return ts

Hierholzer's algorithm for finding Eulerian Cycle Python

1 Answers1