Welcome, guest | Sign In | My Account | Store | Cart
# Finding Eulerian path in undirected graph
# Przemek Drochomirecki, Krakow, 5 Nov 2006

def eulerPath(graph):
   
# counting the number of vertices with odd degree
    odd
= [ x for x in graph.keys() if len(graph[x])&1 ]
    odd
.append( graph.keys()[0] )

   
if len(odd)>3:
       
return None
   
    stack
= [ odd[0] ]
    path
= []
   
   
# main algorithm
   
while stack:
        v
= stack[-1]
       
if graph[v]:
            u
= graph[v][0]
            stack
.append(u)
           
# deleting edge u-v
           
del graph[u][ graph[u].index(v) ]
           
del graph[v][0]
       
else:
            path
.append( stack.pop() )
   
   
return path

History