Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
An easy bad upper bound for an undirected connected graph $G$ is given by ${n\choose 2}c$ where $c$ is the complexity (number of spanning trees) of $G$ and where $G$ has $n$ vertices. The number $c$ is easy to compute by Kirhoff's theorem. –  Roland Bacher Apr 6 '11 at 16:21
    
This is not really an answer, I'm still thinking about it... But perhaps one way to make your algorithm faster is to implement it iteratively instead of recursively. This will remove many function calls, and should be a bit nicer in the memory. I don't really think there is another way than bruteforce enumeration in this case :-/ –  Nathann Cohen Apr 6 '11 at 17:38
add comment

1 Answer

I believe the magical words are "topological sort".

share|improve this answer
    
Igor, topological sort is only for acyclic graphs, but even there I'm not completely sure how it helps in counting the number of paths. Can you elaborate please? –  Szabolcs Apr 6 '11 at 16:10
    
To clarify, my graphs have many cycles in them, but I need to count acyclic paths (i.e. paths with no repeating nodes). –  Szabolcs Apr 6 '11 at 16:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.