How to find ALL Eulerian paths in directed graph

Question

I have a directed graph and I want to find all existing eulerian paths (in my graph I actually know that those will be circuits).

I have done some research so I can use for example Hierholzer's algorithm as in here: http://stones333.blogspot.co.uk/2013/11/find-eulerian-path-in-directed-graph.html to find a path from given node but this algorithm returns only one path I believe.

My idea to solve this is to have an algorithm that will return ALL existing Eulerian paths / circuits starting from given node. Then I will run this algorithms for all nodes and get the results. This will have n^2 or n^3 complexity which is great.

So my question is if there is an algorithm that will find all Eulerian paths / circuits in directed graph from given node? Or maybe someone knows another solution to my problem.

EDIT: after Gassa comment I think that the solution with Euler paths might be an overkill for my problem. Problem is as follows: for given n we create a pairs of integers which sum is <= n. For those pairs find all paths that connects all of the pairs such that second value of previous pair equals to the first value from next pair (like domino).

Example: n = 2, then available pairs = {(0,0), (0,1),(1,0),(1,1),(2,0),(0,2)}. One of the valid chains = (0,0)=>(0,1)=>(1,1)=> (1,0)=>(0,2)=>(2,0). I preferred algorithm using graphs because for example (0,0) might not be valid sometimes, but let's say it is valid for the sake of this question. Brute force solution to this problem is to of course create all permutations of available pairs and then see if they are valid but this is obviously O(n!) complex. I am pretty sure this could be done in some "smart" way.

Answer 1

In the general case, the number of distinct Eulerian paths is exponential in the number of vertices n. Just counting the number of Eulerian circuits in an undirected graph is proven to be #P-complete (see Note on Counting Eulerian Circuits by Graham R. Brightwell and Peter Winkler). Quoting Wikipedia:

A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = NP, and thus P = PH. No such algorithm is currently known.

So perhaps you will need another approach.

If however your graph has certain properties which make the exponential number of Eulerian circuits impossible, do tell us these properties.

Answer 2

If you want to enumerate all Eulerian paths (and, like Gassa, I have my doubts), then the following simple output-sensitive algorithm has polynomial overhead, which, since n will be very small, should suffice. There's a recursive procedure for enumerating all paths from v that goes like this in Python.

def paths(v, neighbors, path):                # call initially with path=[]
    yield path[:]                             # return a copy of the mutable list
    for w in list(neighbors[v]):
        neighbors[v].remove(w)                   # remove the edge from the graph
        path.append((v, w))                   # add the edge to the path
        yield from paths(w, neighbors, path)  # recursively enumerate
                                              #   all path extensions from w
                                              #   in the residual graph
        path.pop()                            # remove the edge from the path
        neighbors[v].add(w)                      # add the edge to the graph

To return Eulerian paths only, we make two modifications. First, we prune the recursion if there is no Eulerian path extending the current path. Second, we do the first yield only when neighbors[v] is empty, i.e., the only extension is the trivial one, so path is Eulerian. Since the degree balance condition is satisfied, we prune by just checking strong connectivity of the non-isolated vertices at each recursive call, given that we add an arc from the starting vertex to v. This can be accomplished with two traversals, one to verify that every non-isolated vertex can reach the starting vertex and one to verify that every non-isolated vertex is reachable from v. (Alternatively, you could add the arc temporarily and do one traversal, but then you'd have to handle multigraphs, which you may not want to.)