[Solved]: Count the number of Euler PATHs in directed graph?

Problem Detail: 

• I would like to find all Euler PATHs in a directed graph.
• Counting (instead of finding) all the Euler PATHs is sufficient.
• Circuits are not good for me, only Paths.

I am doing a problem, that I have derived to a point, where knowing the number of paths fast would help. Currently, I have written (in c++) a recursive function that finds all of them, but it complexity grows quickly, so my algorithm gets slow fast. My algorithm is ~O(2^n). I would like a faster one for counting, if possible.

I have researched the topic, but I can only find proofs (for being NP complete, or polynomial) and algorithms for Euler Circuits in directed and undirected graphs. But again, I am looking for Euler Paths in directed graphs.

My graphs have only two nodes, but a lot of edges, that should be touched only once, like in an Euler Path.

So in summary:

1. Euler Path.
2. Directed Graph.
3. Only two nodes.
4. High edge count.
5. Edge costs are the same.

Here is an image to illustrate a possible set up.

Asked By : Snowman

Answered By : Yuval Filmus

You can actually come up with a formula for this. Let $\ell_0,\ell_1$ be the number of self-loops at $0,1$, and let $e_{01},e_{10}$ be the edges from $0$ to $1$ and in the other direction. We must have $|e_{01}-e_{10}| \leq 1$. If $e_{01} = e_{10}+1$ then the path must start at $0$; if $e_{10} = e_{01}+1$ then it must start at $1$; if $e_{01} = e_{10}$ then both are possible. We will count paths starting at $0$.

Given an Eulerian path starting at $0$, we can write it as $$ L_0 E_1 L_1 E_2 \cdots E_m L_m, $$ where $L_0,L_2,\ldots$ are collections of self-loops at $0$, $L_1,L_3,\ldots$ are collections of self-loops at $1$, $E_1,E_3,\ldots$ are $0\to 1$ edges, and $E_2,E_4,\ldots$ are $1\to 0$ edges. We can decompose this path into three components: $$ E_1 E_2 \ldots E_m \\ L_0 L_2 \ldots \\ L_1 L_3 \ldots $$ We can choose the first component in $e_{01}! e_{10}!$ ways, the second component in $\ell_0!$ ways, and the third component is $\ell_1!$ ways. It remains to choose a way of partitioning the latter two strings into their components. In order to count this, assume that $m$ is even (the case $m$ odd is very similar) and divide the original path differently: $$ L_0 E_1 L_2 E_3 L_4 \ldots E_{m-1} L_m \\ L_1 E_2 L_3 E_4 L_5 \ldots E_{m-2} L_{m-1} E_m $$ The first line contains $m/2$ "breakpoints" out of $\ell_0 + m/2$ symbols in total, so the number of ways of breaking $L_0L_2\ldots L_m$ into its $m/2+1$ parts is $\binom{\ell_0+m/2}{m/2}$. The computation is similar for the second line, once we remove the $E_m$ which must appear at the end; we get $\binom{\ell_1+m/2-1}{m/2-1}$.

I'll leave you the task of bringing everything together to one formula.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52462

3.2K people like this

 Download Related Notes/Documents