Eulerian Tour in Python

Question

This is a recursive algorithm implementation of Eulerian tour search.

I guess there is no way to make it more efficient (except rewriting with loops instead of recursion). Any advice on style?

def sub(visited, _cur, graph):
 if not graph:
 return visited + [_cur]
 for i, edge in enumerate(graph):
 cur, nex = edge
 if _cur not in edge:
 continue
 _graph = graph[:]
 del _graph[i]
 if _cur == cur:
 res = sub(visited + [cur], nex, _graph)
 else:
 res = sub(visited + [nex], cur, _graph)
 if res:
 return res
def find_eulerian_tour(graph):
 head, tail = graph[0], graph[1:]
 prev, nex = head
 return sub([prev], nex, tail)
assert find_eulerian_tour([(1, 2), (2, 3), (3, 4), (4, 1)]) == [1, 2, 3, 4, 1]
assert 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)
]) == [0, 1, 7, 3, 6, 1, 5, 4, 8, 9, 5, 2, 4, 0]

Answer 1

Comments and good docstrings would go a long way. Obviously if I was familiar with the algorithm I'd understand easier, but you're not helping a lot with your naming. Why are you using _cur and cur? Do you just want to use the same name twice without clashing? If so you should do it another way, because _var is the Python style of indicating a variable that should be treated as private and not modified externally. It's an idiom for classes and looks out of place here.

Even still, cur, nex mean current and next, right? As you noted you shouldn't use next because it's a builtin name, but using next_branch or something more descriptive is better than stripping away a letter. Also if I've got the wrong end of the stick and nex is something else, that also just means you need a better shortened word or a comment explaining what nex is.

Also more whitespace will make the flow of your code easier to read than a solid block of text:

def sub(visited, _cur, graph):
 if not graph:
 return visited + [_cur]
 for i, edge in enumerate(graph):
 cur, nex = edge
 if _cur not in edge:
 continue
 _graph = graph[:]
 del _graph[i]
 if _cur == cur:
 res = sub(visited + [cur], nex, _graph)
 else:
 res = sub(visited + [nex], cur, _graph)
 if res:
 return res

Even before adding code and more readable names, this breaks up what's happening so a reader can parse it easier.

Answer 2

def find_euler_tour(visited,current,graph):
 queue=[current]
 while queue:
 if graph[current]:
 queue.append(current) 
 current=graph[current].pop()
 else:
 visited.append(current)
 current=queue.pop()
 return 

Thanks, changed your code to get rid of the recursive part, and I am using adjacency graphs (which have 2n edges) . Also you rebooted your graph matrix at every step, and I knew mine had 10000ish edges so, this way I am just slowly eating away at smaller lists inside of a dictionary of children vertices connected to parent vertices (adjacency graph).

Graph was created like this: assumming a 2-tuple for each edge between node A,B

from collections import defaultdict
graph=defaultdict(list)
for A,B in edges:
 graph[A].append(B)
 graph[B].append(A)

Called like

visited=[]
current=1 #starting at Node 1 for example
find_euler_tour(visited,current,graph)

I was after a complete n-ary tree eulerian walk through a undirected tree graph. First step toward Least Common Ancestor.