[FIXED] How to find ALL Eulerian paths in directed graph

Issue

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.

Solution

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.

Answered By - Gassa

Answer Checked By - Mildred Charles (PHPFixing Admin)