StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFast algorithm for counting the number of acyclic paths on a directed graph
text
Body
copied!<p>In short, I need a <strong>fast</strong> algorithm to count how many acyclic paths are there in a simple directed graph.</p> <p>By <em>simple</em> graph I mean one without self loops or multiple edges. A <em>path</em> can start from any node and must end on a node that has no outgoing edges. A path is <em>acyclic</em> if no edge occurs twice in it.</p> <p>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.</p> <p>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.</p> <p>The sample dataset: <a href="http://pastie.org/1763781" rel="noreferrer">http://pastie.org/1763781</a> (each line is an edge-pair)</p> <p>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): <a href="http://pastie.org/1763790" rel="noreferrer">http://pastie.org/1763790</a></p> <p><em>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.</em></p> <p>Edit: also posted on MathOverflow under same title, as it might be more relevant there. Hope this is not against the rules. Can't link as site won't allow more than 2 links ...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload