- 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:
- Euler Path.
- Directed Graph.
- Only two nodes.
- High edge count.
- Edge costs are the same.
Here is an image to illustrate a possible set up.