How to find all paths with a length in a certain range
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? Thanks! Birch
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
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@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
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Tue, 17 Jul 2012, J Birch 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?
You might want to use dynamic programming on the graph, traversing it in a reverse topological order. See http://stackoverflow.com/questions/2207987/cheapest-path-algorithm for information on a related problem. -- Jeremiah Willcock
participants (3)
-
J Birch -
Jeffrey Lee Hellrung, Jr. -
Jeremiah Willcock