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: J Birch (birchsport_at_[hidden])
Date: 2012-07-18 14:39:03

Thanks Jeff,

        The main point of my question was to get an indication of whether or not it was feasible to do and what the complexity level would be.  My biggest hinderance in implementation is my lack of experience with C++.  I am primarily a Java and Ruby guy.  I have walked through the C++ examples, but the use of templates throws me off since I am not that familiar with implementing my own for the DFS or BFS searches.  I was actually hoping there was already an implementation (i.e. code) out there that did this and I could modify to fit my needs, but I guess I need to stop looking and just buckle down and figure it out.  FWIW, the implementation might be used to replace our ugly home grown code for fragmenting chemical bonds to help identify cancerous molecule combinations.  What we have works, but it is slower than I would like, and very very convoluted.  The frustrating part for me is that I can provide an implementation using the Java APIs I know, but the project I am on is insistent on using C++.

        Thank you for your feedback as it gives me a god path to follow.

Birch
On Jul 18, 2012, at 2:10 PM, Jeffrey Lee Hellrung, Jr. wrote:

> 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
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost