Finding all paths on a Directed Acyclic Graph (DAG) seems like a very common task that one might want to do, yet for some reason I had trouble finding information on the topic (as of writing, Sep 2011). The best Google result I found on this topic was at Stackoverflow, but surprisingly very few posts or answers even. So I decided to roll out my own implementation, because that’s the way I roll. I bet some astute reader out there will no doubt point to me the original implementation that I duplicated.
I’ve wiped out my original post because I realised how convoluted my initial approach was. The new code is much simpler, so simple that I’m hoping it’s self explanatory enough that I won’t even have to write up a detail blog about it. But if you need some clarification post a comment below.
Some actual C++ code for the given example can be downloaded here FindAllPathsInDAG.cpp (right click and Save As)