Counting the number of Eulerian trails in a connected, directed graph

Question

I can't find anything about this online, and I'm beginning to suspect it's a hard problem. I know that counting the number of circuits is #P-complete, but I don't need the number of circuits; I need the number of trails. My current "solution" is to simply walk the graph, find every path, and count them.

Important notes:

1. The graph is directed.
2. The graph is connected.
3. The graph has at most two vertices with different in- and out-degrees.
4. I'm looking for trails, including but not limited to circuits.

Any information on this, including upper limits, computational complexity, algorithms, etc., would be helpful.

Answer 1

I'm not sure why I didn't realize this before, but perhaps this will help someone with my same misunderstanding: being able to count Eulerian trails for arbitrary directed, connected graphs would imply being able to count Eulerian circuits for arbitrary directed, connected graphs, which would imply $P=NP$, societies would crumble, and anarchy would reign. (Maybe I'm being a bit hyperbolic but you get the idea.)

Answer 2

Not enough reputation to leave a comment, but according to Wikipedia,

The number of Eulerian circuits in digraphs can be calculated using the so-called BEST theorem, named after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. The formula states that the number of Eulerian circuits in a digraph is the product of certain degree factorials and the number of rooted arborescences. The latter can be computed as a determinant, by the matrix tree theorem, giving a polynomial time algorithm.

It is the undirected case which is #P-complete. This doesn't answer the question in the BEST algorithm doesn't directly compute Eulerian trails, but as you said, the two problems are closely related: take your favorite graph with any Eulerian trails (which is an easy check), add an extra vertex adjacent to the odd-degree vertices (if any), and calculate the number of Eulerian circuits.