Re: [boost] How to find all paths with a length in a certain range

Subject: Re: [boost] How to find all paths with a length in a certain range
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-07-18 14:10:40

On Tue, Jul 17, 2012 at 2:05 AM, J Birch <birchsport_at_[hidden]> 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