|Pathologically Eclectic Rubbish Lister|
Re^7: Finding All Paths From a Graph From a Given Source and End Nodeby BrowserUk (Pope)
|on Nov 02, 2010 at 14:09 UTC||Need Help??|
Did you also benchmark other code? Like in this post?
No.Here's the 5 million path tree, the command line and timing, but from a cursory glance at code you reference, you're going to require a lot (10GB or more) of memory.
If you prefer the 10,000 path graph as a test:
(I can't see the point in copying around the %seen hash 1) or even the current path of a DFS. :) Furthermore this code can be easily linearized to avoid the function-call overhead...In general there are still plenty of possible optimizations left to speed up such a search.
Improvements or alternatives welcome :) . I'm not claiming the fastest on the block, just better than my own previous efforts.
neversaint expressed his interest in the time complexity of my previous version, so I set out to improve it. Given the combinatorial explosion that can result from the all-paths traversal of apparently quite simple graphs, moving to an iterator rather than an accumulating generator seemed the logical route.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.