hierholzer.py

def recursive_eulerian_path(adj, start_node):
    temp_adj = {v: list(adj[v]) for v in adj}

    def dfs(start):
        stack = [start]
        path = []
        while stack:
            while temp_adj[stack[-1]]:
                next_node = temp_adj[stack[-1]].pop()
                stack.append(next_node)
            path.append(stack.pop())
        return path[::-1]

    return dfs(start_node)
  
def iterative_eulerian_path(adj, start_node):
    temp_adj = {v: list(adj[v]) for v in adj}  # Copy adjacency list
    stack = [start_node]
    path = []

    while stack:
        while temp_adj[stack[-1]]:  # While there are outgoing edges
            stack.append(temp_adj[stack[-1]].pop())  # Visit the next node
        path.append(stack.pop())  # Backtrack when no edges left

    return path[::-1]  # Reverse to get correct order