In short, I need a **fast** algorithm to count how many acyclic paths are there in a simple directed graph.

By *simple* graph I mean one without self loops or multiple edges.
A *path* can start from any node and must end on a node that has no outgoing edges. A path is *acyclic* if no edge occurs twice in it.

My graphs (empirical datasets) have only between 20-160 nodes, however, some of them have many cycles in them, therefore there will be a very large number of paths, and my naive approach is simply not fast enough for some of the graph I have.

What I'm doing currently is "descending" along all possible edges using a recursive function, while keeping track of which nodes I have already visited (and avoiding them). The fastest solution I have so far was written in C++, and uses std::bitset argument in the recursive function to keep track of which nodes were already visited (visited nodes are marked by bit 1). This program runs on the sample dataset in 1-2 minutes (depending on computer speed). With other datasets it takes more than a day to run, or apparently much longer.

The sample dataset: http://pastie.org/1763781 (each line is an edge-pair)

Solution for the sample dataset (first number is the node I'm starting from, second number is the path-count starting from that node, last number is the total path count): http://pastie.org/1763790

*Please let me know if you have ideas about algorithms with a better complexity. I'm also interested in approximate solutions (estimating the number of paths with some Monte Carlo approach). Eventually I'll also want to measure the average path length.*

Note: Same question previously posted on stackoverlow, hope this is not against the rules. Later realized the question has more to do with maths.