On Tue, Jul 17, 2012 at 2:05 AM, J Birch <birchsport@gmail.com> wrote:
I am fairly new to Boost, and not the greatest at C++, but I do have a bit of experience in dealing with graphs in other languages.
We currently have some very ugly and inefficient code that effectively builds up a graph structure (DAG), and must calculate all paths with a length between a certain range, say 3-7.
I have seen the question asked a few times via Google, but I have seen no solution. I have been tinkering around with different examples, but have yet to come up with anything useful.
Would anyone be able to point me in the right direction?
I'm a little unclear what "the question" is, but I presume the problem is to find all paths in a DAG with length within a given range. My gut reaction is just a simple BFS (if by length you mean number of edges/vertices) or Dijkstra (if by length you mean sum of edge costs) until the next vertex in your queue is farther than your maximum desired distance. If one keeps track of parents of visited vertices, one already has all the desired paths implicitly in whatever visitation structure you maintain. Is there something unpalatable with that direction? - Jeff