CODEWITHSUNDEEP
c++algorithmgraph
Snowman
Snowman

Reputation: 1543

Count the number of Euler PATHs in directed graph?

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, 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.

enter image description here

Upvotes: 0

Views: 1134

Answers (1)

SashaMN
SashaMN

Reputation: 708

If you want to generate all possible pathes, I think it's not possible to speed up, because you have to print a lot of pathes. But if you need to only count them, you can do this faster.

You have edges of 4 types. 1) 0-0; 2) 1-1; 3) 0-1; 4)1-0

First of all, let's count how many we have edges of type 3 and 4.

Suppose:

S1 - total count of edges of type 1

S2 - total count of edges of type 2

S3 - total count of edges of type 3

S4 - total count of edges of type 4

If |S3 - S4| > 1 the path does not exist.

For your graph, S3 = 1, S4 = 2. Suppose, we have a path. Let's fix edges of type 3 and 4.

Then the path will look like:

(1-1)*, 1-0, (0-0)*, 0-1, (1-1)*, 1-0, (0-0)*

(1-1)* - means 0 or more times repeat edge 1-1.

Now the algorithm looks obvious:

  1. generate permutation of (1-0) edges
  2. generate permutation of (0-1) edges
  3. generate permutation of (0-0) edges
  4. generate permutation of (1-1) edges
  5. Find all compositions of S3, and S4 in not more then S1 and S2 parts.
  6. Write the answer.

Steps 1-4 will take O(S1! * S2! * S3! * S4!) time (S1 + S2 + S3 + S4 = n).

So the algorithm will be slow.

We can find total count, using the rule of product.

Steps 1-4 give us S1! * S2! * S3! * S4! combinations.

It's possible to count step 5 combinations in O(N) time. Just calculate the prefix sum in this article: https://en.wikipedia.org/wiki/Composition_(combinatorics)

Upvotes: 1

Related Questions